License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2019.20
URN: urn:nbn:de:0030-drops-104914
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10491/
Bulteau, Laurent ;
Dabrowski, Konrad K. ;
Fertin, Guillaume ;
Johnson, Matthew ;
Paulusma, Daniël ;
Vialette, Stéphane
Finding a Small Number of Colourful Components
Abstract
A partition (V_1,...,V_k) of the vertex set of a graph G with a (not necessarily proper) colouring c is colourful if no two vertices in any V_i have the same colour and every set V_i induces a connected graph. The Colourful Partition problem, introduced by Adamaszek and Popa, is to decide whether a coloured graph (G,c) has a colourful partition of size at most k. This problem is related to the Colourful Components problem, introduced by He, Liu and Zhao, which is to decide whether a graph can be modified into a graph whose connected components form a colourful partition by deleting at most p edges.
Despite the similarities in their definitions, we show that Colourful Partition and Colourful Components may have different complexities for restricted instances. We tighten known NP-hardness results for both problems by closing a number of complexity gaps. In addition, we prove new hardness and tractability results for Colourful Partition. In particular, we prove that deciding whether a coloured graph (G,c) has a colourful partition of size 2 is NP-complete for coloured planar bipartite graphs of maximum degree 3 and path-width 3, but polynomial-time solvable for coloured graphs of treewidth 2.
Rather than performing an ad hoc study, we use our classical complexity results to guide us in undertaking a thorough parameterized study of Colourful Partition. We show that this leads to suitable parameters for obtaining FPT results and moreover prove that Colourful Components and Colourful Partition may have different parameterized complexities, depending on the chosen parameter.
BibTeX - Entry
@InProceedings{bulteau_et_al:LIPIcs:2019:10491,
author = {Laurent Bulteau and Konrad K. Dabrowski and Guillaume Fertin and Matthew Johnson and Dani{\"e}l Paulusma and St{\'e}phane Vialette},
title = {{Finding a Small Number of Colourful Components}},
booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
pages = {20:1--20:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-103-0},
ISSN = {1868-8969},
year = {2019},
volume = {128},
editor = {Nadia Pisanti and Solon P. Pissis},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10491},
URN = {urn:nbn:de:0030-drops-104914},
doi = {10.4230/LIPIcs.CPM.2019.20},
annote = {Keywords: Colourful component, colourful partition, tree, treewidth, vertex cover}
}
|
Keywords: |
|
Colourful component, colourful partition, tree, treewidth, vertex cover |
|
Collection: |
|
30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.06.2019 |
