您的位置: 首页 > 外文期刊论文 > 详情页

On the parameterized complexity of multiple-interval graph problems

作   者:
Michael R. FellowsDanny HermelinFrances RosamondStephane Vialette
关键词:
Multiple intervalsDominating setW-hardnessMulticolored cliqueIndependent setCliqueParameterized complexity
期刊名称:
Theoretical computer science
i s s n:
0304-3975
年卷期:
2009 年 410 卷 1 期
页   码:
53-61
页   码:
摘   要:
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-CLQUE 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[l]-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[l]-hardness results which are notoriously hard to construct and technically tedious.
相关作者
载入中,请稍后...
相关机构
    载入中,请稍后...
应用推荐

意 见 箱

匿名:登录

个人用户登录

找回密码

第三方账号登录

忘记密码

个人用户注册

必须为有效邮箱
6~16位数字与字母组合
6~16位数字与字母组合
请输入正确的手机号码

信息补充