Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy

DOI10.1016/J.TCS.2012.01.025MaRDI QIDQ690460zbMATH OpenOpenAlexFDO

Authors Yong Zhang, Minghui Jiang

Publication date 27 November 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.0187

zbMATH Keywords

partitioncompletenessdominationhardnessparameterized complexityseparation\(d\)-distance \(k\)-dominating set\(k\)-dominating setirredundant setmultiple-interval graphsseparating vertices

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We show that the problem k-Dominating Set and its several variants including k-Connected Dominating Set, k-Independent Dominating Set, and k-Dominating Clique, when parameterized by the solution size k, are W[1]-hard in either multiple-interval graphs or their complements or both. On the other hand, we show that these problems belong to W[1] when restricted to multiple-interval graphs and their complements. This answers an open question of Fellows et al. In sharp contrast, we show that d-Distance k-Dominating Set for d >= 2 is W[2]-complete in multiple-interval graphs and their complements. We also show that k-Perfect Code and d-Distance k-Perfect Code for d >= 2 are W[1]-complete even in unit 2-track interval graphs. In addition, we present various new results on the parameterized complexities of k-Vertex Clique Partition and k-Separating Vertices in multiple-interval graphs and their complements, and present a very simple alternative proof of the W[1]-hardness of k-Irredundant Set in general graphs.

Recommendations

• Parameterized complexity in multiple-interval graphs: domination
• Parameterized complexity in multiple-interval graphs: partition, separation, irredundancy
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• On the parameterized complexity of some optimization problems related to multiple-interval graphs

Cites work

• scientific article; zbMATH DE number 91051 (Why is no real title available?)
• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 921905 (Why is no real title available?)
• Data reduction and exact algorithms for clique cover
• Dominating set is fixed parameter tractable in claw-free graphs
• Extremal values of the interval number of a graph, II
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On recovering syntenic blocks from comparative maps
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of short computation and factorization
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Optimization problems in multiple-interval graphs
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Parameterized and Exact Computation
• Parameterized complexity in multiple-interval graphs: domination
• Parameterized complexity in multiple-interval graphs: partition, separation, irredundancy
• Perfect Code is \(W[1]\)-complete
• Scheduling Split Intervals
• Some simplified NP-complete graph problems
• The Complexity of Coloring Circular Arcs and Chords
• The complexity of irredundant sets parameterized by size

Cited in

(11)

• The complexity of dominating set in geometric intersection graphs
• The dominating set problem in geometric intersection graphs
• Parameterized complexity in multiple-interval graphs: domination
• \(k\)-gap interval graphs
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• On the parameterized complexity of multiple-interval graph problems
• The parameterized complexity of domination-type problems and application to linear codes
• The maximum clique problem in multiple interval graphs
• Parameterized complexity in multiple-interval graphs: partition, separation, irredundancy
• Parameterized Problems on Coincidence Graphs

This page was built for publication: Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690460)