Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952167 | Theoretical Computer Science | 2017 | 10 Pages |
Abstract
In this paper we provide further insight into the complexity landscape of the problem by showing a complexity dichotomy result with respect to the parameters pathwidth and maximum degree of the input graph. More precisely, first, we prove that the problem is NP-complete even on trees of pathwidth at most three for any bâ¥1. Then we show that the problem turns out to be fixed parameter-tractable with respect to the combined parameter “pathwidth” and “maximum degree” of the input graph. Finally, we show that the problem remains NP-complete on very dense graphs, namely co-bipartite graphs, but is fixed-parameter tractable with respect to the parameter “cluster vertex deletion”.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Janka ChlebÃková, Morgan Chopin,