Problemas de particionamento de grafos em árvores monocromáticas

Abstract

In this work, we study the Partitioning Graphs into Monochromatic Trees (PGMT) problem. In this problem, an edge-coloured graph G with n vertices is given, and the goal is to find the smallest number of vertex disjoint monochromatic trees that cover all the vertices of G. First, we study the computational complexity of this problem, in which we show that the PGMT is NP-complete when we consider some parameters such as: color frequency, maximum degree and number of colors; or when we restrict to the class of complete bipartite graphs where the number of trees is limited. We also show a lower bound for executing exact algorithms using the Exponential Time Hypothesis (ETH). More precisely, we show that there is δ > 0 such that PGMT cannot be resolved in time O(2δn), unless a ETH is false. As positive results, we present an algorithm of complexity O(n 2 ) when G is a tree and we also present an algorithm parameterized by the number of colors r and by the treewidth t of the input graph that runs in time O(n O(1)(r · t) 2t+1).