Computer Science – Computational Complexity
Scientific paper
2011-10-02
Computer Science
Computational Complexity
A preliminary version of this article appeared in two parts in COCOON 2011 and IPEC 2011
Scientific paper
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.
Jiang Minghui
Zhang Yong
No associations
LandOfFree
Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-284378