Partitioning Graphs into Monochromatic Trees Problems

  • Diego Rangel Piranga Costa UFMG
  • Vinicius Fernandes dos Santos UFMG
  • Phablo F. S. Moura UFMG
DOI: https://doi.org/10.5753/etc.2022.223189

Abstract


Graph partition problems is an important class of graph problems that are able to model real-world tasks such as Concurrent Processor Allocation and Very Large-Scale Integration (VLSI) systems. Even though such problems are NP-hard, there is a lot of effort in developing methods to deal with such problems. In this work, we present results from the point of view of computational complexity for the problem of Partitioning Graphs into Monochromatic Trees as know as PGMT, proving the NP-hardness even for restricted versions of this problem. In addition, we present a lower bound for the execution time of algorithms based on the Exponential Time Hypothesis (ETH) and we also present two algorithms, the first based on dynamic programming when considering that the input graph is a tree and a second algorithm parameterized by the treewidth and the number of colors.

Keywords: Algorithms, Monochromatic Trees, Parameterized Complexity, Graphs

References

Bodlaender, H. L., Cygan, M., Kratsch, S., and Nederlof, J. (2013). Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86–111.

Jin, Z., Kano, M., Li, X., and Wei, B. (2006). Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycle, paths and trees. Journal of Combinatorial Optimization, 11(4):445–454.

Jin, Z. and Li, X. (2004). The complexity for partitioning graphs by monochromaic trees, cycles and paths. International Journal of Computer Mathematics, 81(11):1357–1362.

Jin, Z. and Li, X. (2008). Vertex partitions of r-edge-colored graphs. Applied Mathematics-A Journal of Chinese Universities, 23(1):120–126.
Published
2022-07-31
How to Cite

Select a Format
COSTA, Diego Rangel Piranga; SANTOS, Vinicius Fernandes dos; MOURA, Phablo F. S.. Partitioning Graphs into Monochromatic Trees Problems. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 113-116. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.223189.