101. The complexity of minimum convex coloring
- Author
-
Torsten Tholey and Frank Kammer
- Subjects
Discrete mathematics ,Applied Mathematics ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Complete coloring ,1-planar graph ,Combinatorics ,Greedy coloring ,Edge coloring ,Graph power ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Discrete Mathematics and Combinatorics ,Graph coloring ,Fractional coloring ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics ,List coloring - Abstract
A coloring of the vertices of a graph is called convex if each subgraph induced by all vertices of the same color is connected. We consider three variants of recoloring a colored graph with minimal cost such that the resulting coloring is convex. Two variants of the problem are shown to be NP-hard on trees even if in the initial coloring each color is used to color only a bounded number of vertices. For graphs of bounded treewidth, we present a polynomial-time (2+@e)-approximation algorithm for these two variants and a polynomial-time algorithm for the third variant. Our results also show that, unless NP@?DTIME(n^O^(^l^o^g^l^o^g^n^)), there is no polynomial-time approximation algorithm with a ratio of size (1-o(1))lnlnN for the following problem: given pairs of vertices in an undirected N-vertex graph of bounded treewidth, determine the minimal possible number l for which all except l pairs can be connected by disjoint paths.
- Published
- 2018