Finding a Small Number of Colourful Components

Authors Laurent Bulteau , Konrad K. Dabrowski , Guillaume Fertin , Matthew Johnson , Daniël Paulusma , Stéphane Vialette



PDF
Thumbnail PDF

File

LIPIcs.CPM.2019.20.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Laurent Bulteau
  • Université Paris-Est, LIGM (UMR 8049), CNRS, ENPC, UPEM, ESIEE Paris, France
Konrad K. Dabrowski
  • Department of Computer Science, Durham University, Durham, UK
Guillaume Fertin
  • Université de Nantes, LS2N (UMR 6004), CNRS, Nantes, France
Matthew Johnson
  • Department of Computer Science, Durham University, Durham, UK
Daniël Paulusma
  • Department of Computer Science, Durham University, Durham, UK
Stéphane Vialette
  • Université Paris-Est, LIGM (UMR 8049), CNRS, ENPC, UPEM, ESIEE Paris, France

Cite AsGet BibTex

Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, and Stéphane Vialette. Finding a Small Number of Colourful Components. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.CPM.2019.20

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • Colourful component
  • colourful partition
  • tree
  • treewidth
  • vertex cover

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Anna Adamaszek and Alexandru Popa. Algorithmic and Hardness Results for the Colorful Components Problems. Algorithmica, 73(2):371-388, 2015. Google Scholar
  2. Sharon Bruckner, Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier, Sven Thiel, and Johannes Uhlmann. Partitioning into Colorful Components by Minimum Edge Deletions. Proc. CPM 2012, LNCS, 7354:56-69, 2012. Google Scholar
  3. Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, and Stéphane Vialette. Finding a Small Number of Colourful Components. Manuscript, 2018. URL: http://arxiv.org/abs/1808.03561.
  4. Laurent Bulteau, Guillaume Fertin, and Irena Rusu. Maximal strip recovery problem with gaps: Hardness and approximation algorithms. Journal of Discrete Algorithms, 19:1-22, 2013. Google Scholar
  5. Janka Chlebikova and Clément Dallard. A Complexity Dichotomy for Colourful Components Problems on k-caterpillars and Small-Degree Planar Graphs. Manuscript, 2019. URL: http://arxiv.org/abs/1902.11191.
  6. Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. The Complexity of Multiterminal Cuts. SIAM Journal on Computing, 23(4):864-894, 1994. Google Scholar
  7. Riccardo Dondi and Florian Sikora. Parameterized complexity and approximation issues for the colorful components problems. Theoretical Computer Science, 739:1-12, 2018. Google Scholar
  8. George He, Jiping Liu, and Cheng Zhao. Approximation Algorithms for Some Graph Partitioning Problems. Journal of Graph Algorithms and Applications, 4(2):1-11, 2000. Google Scholar
  9. John E. Hopcroft and Richard M. Karp. An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal on Computing, 2(4):225-231, 1973. Google Scholar
  10. Neeldhara Misra. On the Parameterized Complexity of Colorful Components and Related Problems. Proc. IWOCA 2018, LNCS, 10979:237-249, 2018. Google Scholar
  11. Neil Robertson and Paul D. Seymour. Graph Minors. XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. Google Scholar
  12. Thomas J. Schaefer. The Complexity of Satisfiability Problems. Proc. STOC 1978, pages 216-226, 1978. Google Scholar
  13. Joseph A. Wald and Charles J. Colbourn. Steiner trees, partial 2–trees, and minimum IFI networks. Networks, 13(2):159-167, 1983. Google Scholar
  14. Chunfang Zheng, Krister M. Swenson, Eric Lyons, and David Sankoff. OMG! Orthologs in multiple genomes - competing graph-theoretical formulations. Proc WABI 2011, LNBI, 6833:364-375, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail