On the parameterized complexity of multiple-interval graph problems Academic Article uri icon

abstract

  • 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 …

publication date

  • January 28, 2009