A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected components are colourful. ...Given a vertex-coloured graph G and an integer p, the Colourful Components problem asks whether there exist at most p edges whose removal makes G colourful and the Colourful Partition problem asks whether there exists a partition of G into at most p colourful components. In order to refine our understanding of the complexity of the problems on trees, we study both problems on k-caterpillars, which are trees with a central path P such that every vertex not in P is within distance k from a vertex in P. We prove that Colourful Components and Colourful Partition are NP-complete on 4-caterpillars with maximum degree 3, 3-caterpillars with maximum degree 4 and 2-caterpillars with maximum degree 5. On the other hand, we show that the problems are linear-time solvable on 1-caterpillars. Hence, our results imply two complexity dichotomies on trees: Colourful Components and Colourful Partition are linear-time solvable on trees with maximum degree d if d≤2 (that is, on paths), and NP-complete otherwise; Colourful Components and Colourful Partition are linear-time solvable on k-caterpillars if k≤1, and NP-complete otherwise. We leave three open cases which, if solved, would provide a complexity dichotomy for both problems on k-caterpillars, for every non-negative integer k, with respect to the maximum degree. We also show that Colourful Components is NP-complete on 5-coloured planar graphs with maximum degree 4 and on 12-coloured planar graphs with maximum degree 3. Our results answer two open questions of Bulteau et al. mentioned in Bulteau et al. (2019) 6.
The NP-hard Colorful Components problem is, given a vertex-colored graph, to delete a minimum number of edges such that no connected component contains two vertices of the same color. It has ...applications in multiple sequence alignment and in multiple network alignment where the colors correspond to species. We initiate a systematic complexity-theoretic study of Colorful Components by presenting NP-hardness as well as fixed-parameter tractability results for different variants of Colorful Components. We also perform experiments with our algorithms and additionally develop an efficient and very accurate heuristic algorithm clearly outperforming a previous min-cut-based heuristic on multiple sequence alignment data.
The quest for colorful components (connected components where each color is associated with at most one vertex) inside a vertex-colored graph has been widely considered in the last ten years. Here we ...consider two variants, Minimum Colorful Components (MCC) and Maximum Edges in transitive Closure (MEC), introduced in 2011 in the context of orthology gene identification in bioinformatics. The input of both MCC and MEC is a vertex-colored graph. MCC asks for the removal of a subset of edges, so that the resulting graph is partitioned in the minimum number of colorful connected components; MEC asks for the removal of a subset of edges, so that the resulting graph is partitioned in colorful connected components and the number of edges in the transitive closure of such a graph is maximized. We study the parameterized and approximation complexity of MCC and MEC, for general and restricted instances.
For MCC on trees we show that the problem is basically equivalent to Minimum Cut on Trees, thus MCC is not approximable within factor 1.36−ε, it is fixed-parameter tractable and it admits a poly-kernel (when the parameter is the number of colorful components). Moreover, we show that MCC, while it is polynomial time solvable on paths, it is NP-hard even for graphs with constant distance to disjoint paths number. Then we consider the parameterized complexity of MEC when parameterized by the number k of edges in the transitive closure of a solution (the graph obtained by removing edges so that it is partitioned in colorful connected components). We give a fixed-parameter algorithm for MEC parameterized by k and, when the input graph is a tree, we give a poly-kernel.
In this paper we investigate the
colorful components
framework, motivated by applications emerging from comparative genomics. The general goal is to remove a collection of edges from an undirected ...vertex-colored graph
G
such that in the resulting graph
G
′
all the connected components are
colorful
(i.e., any two vertices of the same color belong to different connected components). We want
G
′
to optimize an objective function, the selection of this function being specific to each problem in the framework. We analyze three objective functions, and thus, three different problems, which are believed to be relevant for the biological applications: minimizing the number of singleton vertices, maximizing the number of edges in the transitive closure, and minimizing the number of connected components. Our main result is a polynomial-time algorithm for the first problem. This result disproves the conjecture of Zheng et al. that the problem is
N
P
-hard (assuming
P
≠
N
P
). Then, we show that the second problem is
A
P
X
-hard, thus proving and strengthening the conjecture of Zheng et al. that the problem is
N
P
-hard. Finally, we show that the third problem does not admit polynomial-time approximation within a factor of
|
V
|
1
/
14
-
ϵ
for any
ϵ
>
0
, assuming
P
≠
N
P
(or within a factor of
|
V
|
1
/
2
-
ϵ
, assuming
Z
P
P
≠
N
P
).
PDF
