检索结果-内蒙古大学图书馆

FRACTALS FOR KERNELIZATION LOWER BOUNDS

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第1期32卷 656-681页

作者： Fluschnik, Till Hermelin, Danny Nichterlein, Andre Niedermeier, Rolf TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel

The composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems. We present a new technique exploiting triangle based fractal structures for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. In particular, answering an open question of Golovach and Thilikos [Discrete Optim., 8 (2011), pp. 77-86], we show that, unless NP subset of coNP / poly, the NP-hard LENGTH-BOUNDED EDGE-CUT (LBEC) problem (delete at most k edges such that the resulting graph has no s-t path of length shorter than l) parameterized by the combination of k and l has no polynomial-size problem kernel. Our framework applies to planar as well as directed variants of the basic problems and also applies to both edge and vertex-deletion problems. Along the way, we show that LBEC remains NP-hard on planar graphs, a result which we believe is interesting in its own right.

关键词： parameterized complexity polynomial-time data reduction lower bounds cross-compositions graph modification problems interdiction problems

来源：评论

学校读者我要写书评

暂无评论

Bivariate complexity analysis of ALMOST FOREST DELETION

引用

THEORETICAL COMPUTER SCIENCE 2018年 708卷 18-33页

作者： Rai, Ashutosh Saurabh, Saket HBNI Inst Math Sci Madras Tamil Nadu India Univ Bergen Bergen Norway

In this paper we study a generalization of classic FEEDBACK VERTEX SET problem in the realm of multivariate complexity analysis. We say that a graph F is an l-forest if we can delete at most l edges from F to get a forest. That is, F is at most l edges away from being a forest. In this paper we introduce the ALMOST FOREST DELETION problem, where given a graph G and integers k and 1, the question is whether there exists a subset of at most k vertices such that its deletion leaves us an l-forest. We show that this problem admits an algorithm with running time 2(O(k+1))n(O(1)) and a kernel of size O(kl(k + l)). We also show that the problem admits a 2(O(tw))n(O(1)) algorithm on bounded treewidth graphs, using which we design a subexponential algorithm for the problem on planar graphs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Bivariate Analysis Almost Forest Deletion parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Polynomial Kernels for Vertex Cover parameterized by Small Degree Modulators

引用

THEORY OF COMPUTING SYSTEMS 2018年第8期62卷 1910-1951页

作者： Majumdar, Diptapriyo Raman, Venkatesh Saurabh, Saket HBNI Inst Math Sci Madras Tamil Nadu India

VERTEX COVER is one of the most well studied problems in the realm of parameterized algorithms. It admits a kernel with O( 2) edges and 2 vertices where denotes the size of the vertex cover we are seeking for. A natural question is whether VERTEX COVER is fixed- parameter tractable or admits a polynomial kernel with respect to a parameter k, that is, provably smaller than the size of the vertex cover. Jansen and Bodlaender [ STACS 2011, TOCS 2013] raised this question and gave a kernel for VERTEX COVER of size O(f 3), where f is the size of a feedback vertex set of the input graph. We continue this line of work and study VERTEX COVER with respect to a parameter that is always smaller than the solution size and incomparable to the size of the feedback vertex set of the input graph. Our parameter is the number of vertices whose removal results in a graph of maximum degree two. While vertex cover with this parameterization can easily be shown to be fixed- parameter tractable (FPT), we show that it has a polynomial kernel. The input to our problem consists of an undirected graph G, S. V (G) such that | S| = k and G[ V (G) \ S] has maximum degree at most two and a positive integer . Given (G, S, ), in polynomial time we output an instance (G , S , ) such that | V (G )| is O(k5), | E(G )| is O(k6) and G has a vertex cover of size at most if and only if G has a vertex cover of size at most . When G[ V (G) \ S] has maximum degree at most one, we improve the known kernel bound from O(k3) vertices to O(k2) vertices (and O(k3) edges). More generally, given (G, S, ) where every connected component of G\ S is a clique of at most d vertices (for constant d), in polynomial time, we output an equivalent instance (G , S , ) for the same problem where | V (G )| is O(kd). We also show that for this problem, when d = 3, a kernel with O(kd- e) bits cannot exist for any e > 0 unless NP. coNP/ poly.

关键词： parameterized complexity Kernelization Expansion lemma Vertex cover Structural parameterization

来源：评论

学校读者我要写书评

暂无评论

Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels

引用

THEORY OF COMPUTING SYSTEMS 2018年第8期62卷 1690-1714页

作者： Krithika, R. Majumdar, Diptapriyo Raman, Venkatesh HBNI Inst Math Sci Madras Tamil Nadu India

The CONNECTED VERTEX COVER problem asks for a vertex cover in a graph that induces a connected subgraph. The problem is known to be fixedparameter tractable ( FPT), and is unlikely to have a polynomial sized kernel ( under complexity theoretic assumptions) when parameterized by the solution size. In a recent paper, Lokshtanov et al. [ STOC 2017], have shown an a- approximate kernel for the problem for every a > 1, in the framework of approximate or lossy kernelization. In this work, we exhibit lossy kernels and FPT algorithms for CONNECTED VERTEX COVER for parameters that are more natural and functions of the input, and in some cases, smaller than the solution size. Our first result is a lossy kernel for CONNECTED VERTEX COVER parameterized by the size of a split deletion set. Let n denote the number of vertices in the input graph. We show that CONNECTED VERTEX COVER parameterized by the size k of a split deletion set admits an a- approximate kernel with O( k + ( 2k + 2a- 1 a- 1 ) 2a- 1 a- 1 ) vertices and an algorithm with O( 3kn O( 1)) running time. For the special case when the split deletion set is a clique deletion set, the algorithm runs in O( 2kn O( 1)) time and the lossy kernel has O( k + 2a- 1 a- 1 ) *** the best of our knowledge, this (approximate) kernel is one of the few lossy kernels for problems parameterized by a structural parameter (that is not solution size). We extend this lossy kernelization to CONNECTED VERTEX COVER parameterized by an incomparable parameter, and that is the size of a clique cover. We show that CONNECTED VERTEX COVER parameterized by the size k of a clique cover is W[ 1]-hard but admits an a-approximate kernel with O(k 2a-1 a-1 ) vertices for every a > 1. This is one of the few problems that are not FPT but admit a lossy kernel. Finally, we consider the size of a cluster deletion set as parameter. We show that CONNECTED VERTEX COVER parameterized by the size k of a cluster deletion set is FPT via an algorithm with runnin

关键词： parameterized complexity Connected vertex cover Lossy kernelization Structural parameterization W-hardness

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms for stable matching with ties and incomplete lists

引用

THEORETICAL COMPUTER SCIENCE 2018年 723卷 1-10页

作者： Adil, Deeksha Gupta, Sushmita Roy, Sanjukta Saurabh, Saket Zehavi, Meirav Indian Inst Sci Educ & Res Pune Maharashtra India Univ Bergen Bergen Norway HBNI Inst Math Sci Madras Tamil Nadu India Ben Gurion Univ Negev Beer Sheva Israel

We study the parameterized complexity of NP-hard optimization versions of STABLE MATCHING and STABLE ROOMMATES in the presence of ties and incomplete lists. These problems model many real-life situations where solutions have to satisfy certain predefined criterion of suitability and compatibility. Specifically, our objective is to maximize/minimize the size of the stable matching. Our main theorems state that STABLE MATCHING and STABLE ROOMMATES admit small kernels. Consequently, we also conclude that STABLE MATCHING is fixed-parameter tractable (FPT) with respect to solution size, and that STABLE ROOMMATES is FPT with respect to a structural parameter. Finally, we analyze the special case where the input graph is planar. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Stable matching parameterized complexity Preference list

来源：评论

学校读者我要写书评

暂无评论

complexity of Secure Sets

引用

ALGORITHMICA 2018年第10期80卷 2909-2940页

作者： Bliem, Bernhard Woltran, Stefan TU Wien Inst Informat Syst 184 2 Favoritenstr 9-11 A-1040 Vienna Austria

A secure set S in a graph is defined as a set of vertices such that for any the majority of vertices in the neighborhood of X belongs to S. It is known that deciding whether a set S is secure in a graph is -complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph G and integer k, a non-empty secure set for G of size at most k exists. In this work, we pinpoint the complexity of this problem by showing that it is -complete. Furthermore, the problem has so far not been subject to a parameterized complexity analysis that considers structural parameters. In the present work, we prove that the problem is -hard when parameterized by treewidth. This is surprising since the problem is known to be FPT when parameterized by solution size and "subset problems" that satisfy this property usually tend to be FPT for bounded treewidth as well. Finally, we give an upper bound by showing membership in , and we provide a positive result in the form of an FPT algorithm for checking whether a given set is secure on graphs of bounded treewidth.

关键词： Secure set complexity analysis parameterized complexity Treewidth parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

How hard is it to control a group?

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2018年第5期32卷 672-692页

作者： Yang, Yongjie Dimitrov, Dinko Saarland Univ Chair Econ Theory Saarbrucken Germany

We consider group identification models in which the aggregation of individual opinions concerning who is qualified in a given society determines the set of socially qualified persons. In this setting, we study the extent to which social qualification can be changed when societies expand, shrink, or partition themselves. The answers we provide are with respect to the computational complexity of the corresponding control problems and fully cover the class of consent aggregation rules introduced by Samet and Schmeidler (J Econ Theory, 110(2):213-233, 2003) as well as procedural rules for group identification. We obtain both polynomial-time solvability results and NP-hardness results. In addition, we also study these problems from the parameterized complexity perspective, and obtain some fixed-parameter tractability results.

关键词： Group identification Consent rules Procedural rules Computational complexity parameterized complexity Control

来源：评论

学校读者我要写书评

暂无评论

Putting it together: the computational complexity of designing robot controllers and environments for distributed construction

引用

SWARM INTELLIGENCE 2018年第2期12卷 111-128页

作者： Wareham, Todd Vardy, Andrew Mem Univ Newfoundland Dept Comp Sci St John NF A1B 3X5 Canada Mem Univ Newfoundland Dept Elect & Comp Engn St John NF A1B 3X5 Canada

Creating target structures through the coordinated efforts of teams of autonomous robots (possibly aided by specific features in their environments) is a very important problem in distributed robotics. Many specific instances of distributed robotic construction teams have been developed manually. An important issue is whether automated controller design algorithms can both quickly produce robot controllers and guarantee that teams using these controllers will build arbitrary requested target structures correctly;this task may also involve specifying features in the environment that can aid the construction process. In this paper, we give the first computational and parameterized complexity analyses of several problems associated with the design of robot controllers and environments for creating target structures. These problems use a simple finite-state robot controller model that moves in a non-continuous deterministic manner in a grid-based environment. Our goal is to establish whether algorithms exist that are both fast and correct for all inputs and if not, under which restrictions such algorithms are possible. We prove that none of these problems are efficiently solvable in general and remain so under a number of plausible restrictions on controllers, environments, and target structures. We also give the first restrictions relative to which these problems are efficiently solvable and discuss what theoretical solvability and unsolvability results derived relative to the problems examined here mean for real-world construction using robot teams.

关键词： Autonomous robots Construction Computational complexity parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

A RANDOMIZED POLYNOMIAL KERNELIZATION FOR VERTEX COVER WITH A SMALLER PARAMETER

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第3期32卷 1806-1839页

作者： Kratsch, Stefan Univ Bonn Inst Informat D-53113 Bonn Germany

In the vertex cover problem we are given a graph G = (V,E) and an integer k and have to determine whether there is a set X subset of V of size at most k such that each edge in E has at least one endpoint in X. The problem can be easily solved in time O*(2(k)), making it fixed-parameter tractable (FPT) with respect to k. While the fastest known algorithm takes only time O*(1.2738(k)), much stronger improvements have been obtained by studying parameters that are smaller than k. Apart from treewidth-related results, the arguably best algorithm for vertex cover runs in time O*(2.3146(p)), where p = k - LP (G) is only the excess of the solution size k over the best fractional vertex cover [Lokshtanov et al. ACM Trans. Algorithms, 11 (2014), pp. 15:1-15:31]. Since p <= k but k cannot be bounded in terms of p alone, this strictly increases the range of tractable instances. Recently, [Garg and Philip, Proceedings of the Symposium on Discrete Algorithms, 2016, pp. 1152-1166] greatly contributed to understanding the parameterized complexity of the vertex cover problem. They prove that 2 LP(G) - MM(G) is a lower bound for the vertex cover size of G, where MM (G) is the size of a largest matching of G, and proceed to study parameter l = k - (2LP(G) - MM(G)). They give an algorithm of running time O*(3(l)), proving that vertex cover is FPT in l. It can be easily observed that l <= p whereas p cannot be bounded in terms of l alone. We complement the work of Garg and Philip by proving that vertex cover admits a randomized polynomial kernelization in terms of l, i.e., an efficient preprocessing to size polynomial in l. This improves over parameter p = k - LP (G) for which this was previously known

关键词： vertex cover parameterized complexity polynomial kernelization

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal and Practical Algorithms for Graph Scan Statistics with Connectivity Constraints

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2019年第2期13卷 20-20页

作者： Cadena, Jose Chen, Feng Vullikanti, Anil Virginia Tech Dept Comp Sci Blacksburg VA 24061 USA Virginia Tech Biocomplex Inst Blacksburg VA 24061 USA SUNY Albany Dept Comp Sci Albany NY 12222 USA 7000 East Ave Livermore CA 94550 USA UAB 426 1215 Western Ave Albany NY 12222 USA 85 Engineers Way Charlottesville VA 22904 USA

One fundamental task in network analysis is detecting "hotspots" or "anomalies" in the network;that is, detecting subgraphs where there is significantly more activity than one would expect given historical data or some baseline process. Scan statistics is one popular approach used for anomalous subgraph detection. This methodology involves maximizing a score function over all connected subgraphs, which is a challenging computational problem. A number of heuristics have been proposed for these problems, but they do not provide any quality guarantees. Here, we propose a framework for designing algorithms for optimizing a large class of scan statistics for networks, subject to connectivity constraints. Our algorithms run in time that scales linearly on the size of the graph and depends on a parameter we call the "effective solution size," while providing rigorous approximation guarantees. In contrast, most prior methods have super-linear running times in terms of graph size. Extensive empirical evidence demonstrates the effectiveness and efficiency of our proposed algorithms in comparison with state-of-the-art methods. Our approach improves on the performance relative to all prior methods, giving up to over 25% increase in the score. Further, our algorithms scale to networks with up to a million nodes, which is 1-2 orders of magnitude larger than all prior applications.

关键词： Scan statistics anomalous subgraph detection graph anomaly detection parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：