×

The complexity of minimum convex coloring. (English) Zbl 1238.05091

Summary: 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 \(\mathcal{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+\varepsilon )\)-approximation algorithm for these two variants and a polynomial-time algorithm for the third variant. Our results also show that, unless \(\mathcal{NP} \subseteq DTIME(n^{O(\log \log n)})\), there is no polynomial-time approximation algorithm with a ratio of size \((1 - o(1))\log\log N\) 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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Moshkovitz, D.; Safra, S., Algorithmic construction of sets for \(k\)-restrictions, ACM Trans. Algorithms, 2, 153-177 (2006) · Zbl 1321.68445
[2] M. Andrews, L. Zhang, Hardness of the undirected edge-disjoint paths problem, in: Proc. 37th Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 276-283.; M. Andrews, L. Zhang, Hardness of the undirected edge-disjoint paths problem, in: Proc. 37th Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 276-283. · Zbl 1192.68309
[3] Bar-Yehuda, R.; Feldman, I.; Rawitz, D., Improved approximation algorithm for convex recoloring of trees, (Workshop on Approximation and Online Algorithms. Workshop on Approximation and Online Algorithms, WAOA’05. Workshop on Approximation and Online Algorithms. Workshop on Approximation and Online Algorithms, WAOA’05, LNCS, vol. 3879 (2006), Springer: Springer Berlin), 55-68 · Zbl 1125.68427
[4] Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 1305-1317 (1996) · Zbl 0864.68074
[5] Bodlaender, H. L., A partial \(k\)-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-45 (1998) · Zbl 0912.68148
[6] Bodlaender, H. L.; Kloks, T., Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J. Algorithms, 21, 358-402 (1996) · Zbl 0861.68036
[7] Chen, X.; Hu, X.; Shuai, T., Inapproximability and approximability of maximal tree routing and coloring, J. Comb. Optim., 11, 219-229 (2006) · Zbl 1130.90037
[8] Chor, B.; Fellows, M.; Ragan, M. A.; Razgon, I.; Rosamond, F.; Snir, S., Connected coloring completion for general graphs: algorithms and complexity, (Proc. 13th Annual International Computing and Combinatorics Conference. Proc. 13th Annual International Computing and Combinatorics Conference, COCOON’07. Proc. 13th Annual International Computing and Combinatorics Conference. Proc. 13th Annual International Computing and Combinatorics Conference, COCOON’07, LNCS, vol. 4598 (2007), Springer: Springer Berlin), 75-85 · Zbl 1206.05040
[9] Feige, U., A threshold of \(\ln n\) for approximating set cover, J. ACM, 45, 634-652 (1998) · Zbl 1065.68573
[10] Kammer, F.; Tholey, T., The complexity of minimum convex coloring, (Proc. 19th Annual International Symposium on Algorithms and Computation. Proc. 19th Annual International Symposium on Algorithms and Computation, ISAAC 2008. Proc. 19th Annual International Symposium on Algorithms and Computation. Proc. 19th Annual International Symposium on Algorithms and Computation, ISAAC 2008, Lecture Notes in Computer Science Series, vol. 5369 (2008), Springer: Springer Berlin), 16-27 · Zbl 1183.68745
[11] Kanj, I. A.; Kratsch, D., Convex recoloring revisited: complexity and exact algorithms, (Proc. 15th Annual International Computing and Combinatorics Conference. Proc. 15th Annual International Computing and Combinatorics Conference, COCOON’09. Proc. 15th Annual International Computing and Combinatorics Conference. Proc. 15th Annual International Computing and Combinatorics Conference, COCOON’09, LNCS, vol. 5609 (2009), Springer: Springer Berlin), 388-397 · Zbl 1248.05201
[12] Karp, R. M., On the computational complexity of combinatorial problems, Networks, 5, 45-68 (1975) · Zbl 0324.05003
[13] Lynch, J. F., The equivalence of theorem proving and the interconnection problem, (ACM) SIGDA Newsl., 5, 31-36 (1975)
[14] Moran, S.; Snir, S., Efficient approximation of convex recoloring, J. Comput. System Sci., 73, 1078-1089 (2007) · Zbl 1123.68095
[15] Moran, S.; Snir, S., Convex recolorings of strings and trees: definitions, hardness results and algorithms, J. Comput. System Sci., 74, 850-869 (2008) · Zbl 1160.68025
[16] Moran, S.; Snir, S.; Sung, W.-K., Partial convex recolorings of trees and galled networks: tight upper and lower bounds, ACM Trans. Algorithms, 7 (2011), Article No. 42 · Zbl 1295.05236
[17] O. Ponta, F. Hüffner, R. Niedermeier, Speeding up dynamic programming for some NP-hard graph recoloring problems, in: TAMC 2008, pp. 490-501.; O. Ponta, F. Hüffner, R. Niedermeier, Speeding up dynamic programming for some NP-hard graph recoloring problems, in: TAMC 2008, pp. 490-501. · Zbl 1139.68394
[18] Robertson, N.; Seymour, P. D., Graph minors. I. Excluding a forest, J. Combin. Theory Ser. B, 35, 39-61 (1983) · Zbl 0521.05062
[19] Robertson, N.; Seymour, P. D., Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63, 39-61 (1995) · Zbl 0823.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.