Abstract
A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours, and a graph is colourful if all its connected components are colourful. Given a vertex-coloured graph, the Colourful Components problem asks whether there exist at most p edges whose removal makes the graph colourful, and the Colourful Partition problem asks whether there exists a partition of the vertex set with at most p parts such that each part induces a colourful component. We study the problems on k-caterpillars (caterpillars with hairs of length at most k) and explore the boundary between polynomial and NP-complete cases. It is known that the problems are NP-complete on 2-caterpillars with unbounded maximum degree. We prove that both problems remain NP-complete on binary 4-caterpillars and on ternary 3-caterpillars. This answers an open question regarding the complexity of the problems on trees with maximum degree at most 5. On the positive side, we give a linear time algorithm for 1-caterpillars with unbounded degree, even if the backbone is a cycle, which outperforms the previous best complexity for paths and widens the class of graphs. Finally, we answer an open question regarding the complexity of Colourful Components on graphs with maximum degree at most 5. We show that the problem is NP-complete on 5-coloured planar graphs with maximum degree 4, and on 12-coloured planar graphs with maximum degree 3. Since the problem can be solved in polynomial-time on graphs with maximum degree 2, the results are the best possible with regard to the maximum degree.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adamaszek, A., Popa, A.: Algorithmic and hardness results for the colorful components problems. Algorithmica 73(2), 371–388 (2015)
Avidor, A., Langberg, M.: The multi-multiway cut problem. Theoret. Comput. Sci. 377(1–3), 35–42 (2007)
Bousquet, N., Daligault, J., Thomassé, S.: Multicut is FPT. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 459–468. ACM (2011)
Bruckner, S., Hüffner, F., Komusiewicz, C., Niedermeier, R., Thiel, S., Uhlmann, J.: Partitioning into colorful components by minimum edge deletions. In: Kärkkäinen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol. 7354, pp. 56–69. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31265-6_5
Bulteau, L., Dabrowski, K.K., Fertin, G., Johnson, M., Paulusma, D., Vialette, S.: Finding a small number of colourful components. arXiv preprint arXiv:1808.03561 (2018)
Dondi, R., Sikora, F.: Parameterized complexity and approximation issues for the colorful components problems. Theoret. Comput. Sci. 739, 1–12 (2018). https://doi.org/10.1016/j.tcs.2018.04.044
Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Upper and lower bounds for finding connected motifs in vertex-colored graphs. J. Comput. Syst. Sci. 77(4), 799–811 (2011)
He, G., Liu, J., Zhao, C.: Approximation algorithms for some graph partitioning problems. In: Graph Algorithms and Applications, vol. 2, pp. 21–31. World Scientific (2004)
Hsu, W.L., Tsai, K.H.: Linear time algorithms on circular-arc graphs. Inf. Process. Lett. 40(3), 123–129 (1991)
Hung, L.T.Q., Sysło, M.M., Weaver, M.L., West, D.B.: Bandwidth and density for block graphs. Discret. Math. 189(1–3), 163–176 (1998)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)
Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM J. Comput. 43(2), 355–388 (2014)
Misra, N.: On the parameterized complexity of colorful components and related problems. In: Iliopoulos, C., Leong, H.W., Sung, W.-K. (eds.) IWOCA 2018. LNCS, vol. 10979, pp. 237–249. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94667-2_20
Tovey, C.A.: A simplified NP-complete satisfiability problem. Discret. Appl. Math. 8(1), 85–89 (1984)
Zheng, C., Swenson, K., Lyons, E., Sankoff, D.: OMG! orthologs in multiple genomes – competing graph-theoretical formulations. In: Przytycka, T.M., Sagot, M.-F. (eds.) WABI 2011. LNCS, vol. 6833, pp. 364–375. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23038-7_30
Acknowledgements
The authors wish to thank Marthe Bonamy for suggesting these problems, and Paul Ouvrard for our valuable discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Chlebíková, J., Dallard, C. (2019). Towards a Complexity Dichotomy for Colourful Components Problems on k-caterpillars and Small-Degree Planar Graphs. In: Colbourn, C., Grossi, R., Pisanti, N. (eds) Combinatorial Algorithms. IWOCA 2019. Lecture Notes in Computer Science(), vol 11638. Springer, Cham. https://doi.org/10.1007/978-3-030-25005-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-25005-8_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-25004-1
Online ISBN: 978-3-030-25005-8
eBook Packages: Computer ScienceComputer Science (R0)