On the parameterized complexity of multiple-interval graph problems

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we Study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k-INDEPENDENT SET, k-DOMINATING SET, and k-CLIQUE, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k-CLIQUE is in FPT, while k-INDEPENDENT SET and k-DOMINATING SET are both W[1]-hard. We also prove that k-INDEPENDENT DOMINATING SET, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k-MULTICOLORED CLIQUE problem, a variant of k-CLIQUE. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious. (C) 2008 Elsevier B.V. All rights reserved.