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

DOI10.1016/J.TCS.2012.01.025zbMATH Open1253.68153arXiv1110.0187OpenAlexW2139428469MaRDI QIDQ690460FDOQ690460

Authors: Yong Zhang, Minghui Jiang 

Publication date: 27 November 2012

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

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.

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

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

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)

Cites Work

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

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)