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

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Fomin, Fedor, V Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Zehavi, Meirav Univ Bergen Bergen Norway Univ Calif Santa Barbara Santa Barbara CA 93106 USA IIT Hyderabad Hyderabad India HBNI Inst Math Sci Chennai Tamil Nadu India IRL 2000 ReLaX Chennai Tamil Nadu India Ben Gurion Univ Negev Beer Sheva Israel

ISBN: (纸本)9781450369794

In the TOPOLOGICAL MINOR DELETION (TM-DELETION) problem, the input consists of an undirected graph G, a family of undirected graphs F and an integer k. The task is to determine whether G contains a set of vertices S of size at most k, such that the graph G \ S obtained from G by removing the vertices of S, contains no graph from F as a topological minor. We give an algorithm for TM-DELETION with running time f (h*, k) . |V(G)|(4). Here h* is the maximum size of a graph in F and f is a computable function of h* and k. This is the first fixed parameter tractable algorithm (FPT) for the problem. In fact, even for the restricted case of planar inputs the first FPT algorithm was found only recently by Golovach et al. [SODA 2020]. For this case we improve upon the algorithm of Golovach et al. [SODA 2020] by designing an FPT algorithm with explicit dependence on k and h*.

关键词： Topological Minor Deletion Topological Minor Containment parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the complexity of BROADCAST DOMINATION and MULTIPACKING in Digraphs 31st

On the Complexity of BROADCAST DOMINATION and MULTIPACKING i...

引用

31st International Workshop on Combinatorial Algorithms (IWOCA)

作者： Foucaud, Florent Gras, Benjamin Perez, Anthony Sikora, Florian Univ Bordeaux Bordeaux INP CNRS LaBRIUMR5800 F-33400 Talence France Univ Orleans INSA Ctr Val de Loire LIFO EA 4022 F-45067 Orleans France Univ Trier Informat Wissensch Fachbereich 4 D-54296 Trier Germany Univ Paris 09 PSL Univ LAMSADE CNRS F-75016 Paris France

ISBN: (纸本)9783030489656;9783030489663

We study the complexity of the two dual covering and packing distance-based problems BROADCAST DOMINATION and MULTIPACKING in digraphs. A dominating broadcast of a digraph D is a function f : V (D) -> N such that for each vertex v of D, there exists a vertex t with f(t) > 0 having a directed path to v of length at most f(t). The cost of f is the sum of f(v) over all vertices v. A multipacking is a set S of vertices of D such that for each vertex v of D and for every integer d, there are at most d vertices from S within directed distance at most d from v. The maximum size of a multipacking of D is a lower bound to the minimum cost of a dominating broadcast of D. Let BROADCAST DOMINATION denote the problem of deciding whether a given digraph D has a dominating broadcast of cost at most k, and MULTIPACKING the problem of deciding whether D has a multipacking of size at least k. It is known that BROADCAST DOMINATION is polynomial-time solvable for the class of all undirected graphs (that is, symmetric digraphs), while polynomial-time algorithms for MULTIPACKING are known only for a few classes of undirected graphs. We prove that BROADCAST DOMINATION and MULTIPACKING are both NP-complete for digraphs, even for planar layered acyclic digraphs of small maximum degree. Moreover, when parameterized by the solution cost/solution size, we show that the problems are respectively W[2]-hard and W[1]-hard. We also show that BROADCAST DOMINATION is FPT on acyclic digraphs, and that it does not admit a polynomial kernel for such inputs, unless the polynomial hierarchy collapses to its third level. In addition, we show that both problems are FPT when parameterized by the solution cost/solution size together with the maximum out-degree. Finally, we give for both problems polynomial-time algorithms for some subclasses of acyclic digraphs.

关键词： Broadcast domination Dominating set Multipacking Directed graphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

An Exponential Time parameterized Algorithm for Planar Disjoint Paths 2020

An Exponential Time Parameterized Algorithm for Planar Disjo...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Lokshtanov, Daniel Misra, Pranabendu Pilipczuk, Michal Saurabh, Saket Zehavi, Meirav Univ Calif Santa Barbara Santa Barbara CA 93106 USA Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Univ Warsaw Inst Informat Warsaw Poland HBNI Inst Math Sci Chennai Tamil Nadu India Ben Gurion Univ Negev Beer Sheva Israel Univ Bergen Bergen Norway IRL 2000 ReLaX Bergen Norway

ISBN: (纸本)9781450369794

In the Disjoint Paths problem, the input is an undirected graph G on n vertices and a set of k vertex pairs, {s(i), t(i)}(i=1)(k), and the task is to find k pairwise vertex-disjoint paths such that the i'th path connects s(i) to t(i). In this paper, we give a parameterized algorithm with running time 2(O(k2))n(O(1)) for Planar Disjoint Paths, the variant of the problem where the input graph is required to be planar. Our algorithm is based on the unique linkage/treewidth reduction theorem for planar graphs by Adler et al. [JCTB 2017], the algebraic co-homology based technique developed by Schrijver [SICOMP 1994] for Disjoint Paths on directed planar graphs, and one of the key combinatorial insights developed by Cygan et al. [FOCS 2013] in their algorithm for Disjoint Paths on directed planar graphs. To the best of our knowledge our algorithm is the first parameterized algorithm to exploit that the treewidth of the input graph is small in a way completely different from the use of dynamic programming.

关键词： disjoint paths planar graphs parameterized complexity network flow homology

来源：评论

学校读者我要写书评

暂无评论

On structural parameterizations of the selective coloring problem ⁎

引用

Procedia Computer Science 2021年 195卷 77-85页

作者： Guilherme C.M. Gomes Vinicius F. dos Santos Departamento de Ciência da Computação Universidade Federal de Minas Gerais Belo Horizonte Brazil

In the Selective Coloring problem, we are given an integer k, a graph G, and a partition of V(G) into p parts, and the goal is to decide whether or not we can pick exactly one vertex of each part and obtain a k-colorable induced subgraph of G. This generalization of Vertex Coloring has only recently begun to be studied by Demange et al. [Theoretical Computer Science, 2014], motivated by scheduling problems on distributed systems, with Guo et al. [TAMC, 2020] discussing the first results on the parameterized complexity of the problem. In this work, we study multiple structural parameterizations for Selective Coloring. We begin by revisiting the many hardness results of Demange et al. and show how they may be used to provide intractability proofs for widely used parameters such as pathwidth, distance to co-cluster, and max leaf number. Afterwards, we present fixed parameter tractable algorithms when parameterizing by distance to cluster, or under the joint parameterizations treewidth and number of parts, and co-treewidth and number of colors. Our main contribution is a proof that, for every fixed k > 1, Selective Coloring does not admit a polynomial kernel when jointly parameterized by the vertex cover number and the number of parts, which implies that Multicolored Independent Set does not admit a polynomial kernel under the same parameterization.

关键词： parameterized complexity kernelization distance to cluster cross-composition vertex cover selective coloring multicolored independent set

来源：评论

学校读者我要写书评

暂无评论

Algorithms for deletion problems on split graphs

引用

INFORMATION PROCESSING LETTERS 2021年 167卷 106066-106066页

作者： Tsur, Dekel Ben Gurion Univ Negev Beer Sheva Israel

In the SPLIT TO BLOCK VERTEX DELETION and SPLIT TO THRESHOLD VERTEX DELETION problems the input is a split graph G and an integer k, and the goal is to decide whether there is a set S of vertices of size at most k such that G - S is a block graph and G - S is a threshold graph, respectively. In this paper we give algorithms for these problems whose running times are O*(2.076(k)) and O*(1.619(k)), respectively. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized complexity Split graphs

来源：评论

学校读者我要写书评

暂无评论

Occupancy Number Restricted Boolean Petri Net Synthesis: A Fixed-Parameter Algorithm 17th

Occupancy Number Restricted Boolean Petri Net Synthesis: A F...

引用

17th International Colloquium on Theoretical Aspects of Computing (ICTAC)

作者： Erofeev, Evgeny Tredup, Ronny Carl von Ossietzky Univ Oldenburg Dept Comp Sci D-26111 Oldenburg Germany Univ Rostock Inst Informat Theoret Informat Albert Einstein Str 22 D-18059 Rostock Germany

ISBN: (纸本)9783030642761;9783030642754

Let tau be a Boolean type of net. For a given transition system A and a natural number rho, the problem occupancy p-restricted tau-synthesis (OR tau S) is the task to decide whether there is a Boolean Petri net N of type tau whose reachability graph is isomorphic to A and, moreover, every place of N contains a token in at most rho reachable markings. In case of a positive decision, N should be constructed. In this paper, we argue that OR tau S is fixed-parameter tractable when parameterized by rho.

关键词： Synthesis parameterized complexity Boolean Petri net Fixed-parameter tractability Transition system

来源：评论

学校读者我要写书评

暂无评论

parameterized Dynamic Variants of Red-Blue Dominating Set 46th

Parameterized Dynamic Variants of Red-Blue Dominating Set

引用

46th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM)

作者： Abu-Khzam, Faisal N. Bazgan, Cristina Fernau, Henning Lebanese Amer Univ Dept Comp Sci & Math Beirut Lebanon Univ Paris 09 PSL Univ LAMSADE CNRS F-75016 Paris France Univ Trier Abt Informat Wissensch Fachber 4 D-54286 Trier Germany

ISBN: (纸本)9783030389192;9783030389185

We introduce a parameterized dynamic version of the RedBlue Dominating Set problem and its partial version. We prove the fixed-parameter tractability of the dynamic versions with respect to the (so called) edit-parameter while they remain W[2]-hard with respect to the increment-parameter. We provide a complete study of the complexity of the problem with respect to combinations of the various parameters.

关键词： Dynamic problems Reoptimization parameterized complexity Set cover Hitting set

来源：评论

学校读者我要写书评

暂无评论

Diminishable parameterized problems and strict polynomial kernelization

引用

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE 2020年第1期9卷 1-24页

作者： Fernau, Henning Fluschnik, Till Hermelin, Danny Krebs, Andreas Molter, Hendrik Niedermeier, Rolf Univ Trier Fachbereich 4 Abt Informat Wissensch Trier Germany Tech Univ Berlin Algorithm & Computat Complex Fac 4 Berlin Germany Ben Gurion Univ Negev Beer Sheva Israel Univ Tubingen Wilhelm Schickard Inst Infonnat Tubingen Germany

Kernelization - a mathematical key concept for provably effective polynomial-time preprocessing of NP-hard problems - plays a central role in parameterized complexity and has triggered an extensive line of research. This is in part due to a lower bounds framework that allows to exclude polynomial-size kernels under the assumption of NP not subset of coNP/poly. In this paper we consider a restricted yet natural variant of kernelization, namely strict kernelization, where one is not allowed to increase the parameter of the reduced instance (the kernel) by more than an additive constant. Building on earlier work of Chen, Flum, and Muller [CiE 2009, Theory Comput. Syst. 2011], we underline the applicability of their framework by showing that a variety of fixed-parameter tractable problems, including graph problems and Turing machine computation problems, does not admit strict polynomial kernels under the assumption of P not equal NP, an assumption being weaker than the assumption of NP not subset of coNP/poly. Finally, we study an adaption of the framework to a relaxation of the notion of strict kernels, where in the latter one is not allowed to increase the parameter of the reduced instance by more than a constant times the input parameter.

关键词： NP-hard problems parameterized complexity kernelization lower bounds polynomial-time data reduction Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

Kernelization results for Equitable Coloring ⁎

引用

Procedia Computer Science 2021年 195卷 59-67页

作者： Guilherme C.M. Gomes Vinicius F. dos Santos Departamento de Ciência da Computação. Universidade Federal de Minas Gerais. Belo Horizonte Brazil

An n-vertex graph is equitably k-colorable if there is a proper coloring of its vertices such that each color is used either [n/k] or [n/k] times. While classic Vertex Coloring is fixed parameter tractable under well established parameters such as pathwidth and feedback vertex set, equitable coloring is W[1]-hard. Little is known, however, about kernelization aspects of Equitable Coloring. In this work, we begin this investigation by first presenting a linear kernel for the parameter distance to clique, which contrasts with the quadratic kernel for Vertex Coloring under the same parameterization. Our main technical contribution is an OR-cross-composition from Multicolored Clique to Number List Coloring parameterized by vertex cover and number of colors which, along with two simple PPT reductions, implies that Equitable Coloring has no polynomial kernel under the same parameterization unless NP ⊆ coNP/poly.

关键词： equitable coloring parameterized complexity kernelization distance to clique vertex cover cross-composition

来源：评论

学校读者我要写书评

暂无评论

On Covering Segments with Unit Intervals 37

On Covering Segments with Unit Intervals

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Bergren, Dan Eiben, Eduard Ganian, Robert Kanj, Iyad DePaul Univ Sch Comp Chicago IL 60604 USA Royal Holloway Univ London Dept Comp Sci Egham Surrey England Vienna Univ Technol Algorithms & Complex Grp Vienna Austria

ISBN: (纸本)9783959771405

We study the problem of covering a set of segments on a line with the minimum number of unit-length intervals, where an interval covers a segment if at least one of the two endpoints of the segment falls in the unit interval. We also study several variants of this problem. We show that the restrictions of the aforementioned problems to the set of instances in which all the segments have the same length are NP-hard. This result implies several NP-hardness results in the literature for variants and generalizations of the problems under consideration. We then study the parameterized complexity of the aforementioned problems. We provide tight results for most of them by showing that they are fixed-parameter tractable for the restrictions in which all the segments have the same length, and are W[1]-complete otherwise.

关键词： Segment covering unit intervals NP-completeness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：