×

Strong intractability results for generalized convex recoloring problems. (English) Zbl 1440.05094

Summary: A coloring of the vertices of a connected graph is \(r\)-convex if each color class induces a subgraph with at most \(r\) components. We address the \(r\)-convex recoloring problem defined as follows. Given a graph \(G\) and a coloring of its vertices, recolor a minimum number of vertices of \(G\) so that the resulting coloring is \(r\)-convex. This problem, known to be NP-hard even on paths, was firstly investigated on trees and for \(r = 1\), motivated by applications on perfect phylogenies. The more general concept of \(r\)-convexity, for \(r \geq 2\), was proposed later, and it is also of interest in the study of protein-protein interaction networks and phylogenetic networks. In this work, we show that, for each \(r \in \mathbb{N} \), the \(r\)-convex recoloring problem on \(n\)-vertex bipartite graphs cannot be approximated within a factor of \(n^{1 - \varepsilon}\) for any \(\varepsilon > 0\), unless P =NP. We also provide strong hardness results for weighted and parameterized versions of the problem.

MSC:

05C15 Coloring of graphs and hypergraphs
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bar-Yehuda, R.; Kutiel, G.; Rawitz, D., 1.5-approximation algorithm for the 2-convex recoloring problem, Discrete Appl. Math., 246, 2-11 (2018) · Zbl 1390.05061
[2] Bodlaender, H. L.; Fellows, M. R.; Langston, M. A.; Ragan, M. A.; Rosamond, F. A.; Weyer, M., Quadratic kernelization for convex recoloring of trees, Algorithmica, 61, 2, 362-388 (2011) · Zbl 1234.68146
[3] Campêlo, M.; Freire, A. S.; Lima, K. R.; Moura, P. F.S.; Wakabayashi, Y., The convex recoloring problem: polyhedra, facets and computational experiments, Math. Program., 156, 1, 303-330 (2016) · Zbl 1346.90609
[4] Campêlo, M. B.; Huiban, C. G.; Sampaio, R. M.; Wakabayashi, Y., Hardness and inapproximability of convex recoloring problems, Theoret. Comput. Sci., 533, 15-25 (2014) · Zbl 1331.05203
[5] Campêlo, M.; Lima, K. R.; Moura, P. F.S.; Wakabayashi, Y., Polyhedral studies on the convex recoloring problem, (Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium. Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2013. Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium. Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2013, Electronic Notes in Discrete Mathematics, vol. 44 (2013)), 233-238
[6] Chopra, S.; Filipecki, B.; Lee, K.; Ryu, M.; Shim, S.; Van Vyve, M., An extended formulation of the convex recoloring problem on a tree, Math. Program., 165, 2, 529-548 (2017) · Zbl 1379.92034
[7] Chor, B.; Fellows, M.; Ragan, M. A.; Razgon, I.; Rosamond, F.; Snir, S., Connected coloring completion for general graphs: Algorithms and complexity, (Lin, G., Computing and Combinatorics. Proceedings of the International Computing and Combinatorics Conference. Computing and Combinatorics. Proceedings of the International Computing and Combinatorics Conference, COCOON 2007. Computing and Combinatorics. Proceedings of the International Computing and Combinatorics Conference. Computing and Combinatorics. Proceedings of the International Computing and Combinatorics Conference, COCOON 2007, Lecture Notes in Computer Science, vol. 4598 (2007)), 75-85 · Zbl 1206.05040
[8] Dantchev, S.; Martin, B.; Szeider, S., Parameterized proof complexity, Comput. Complexity, 20, 1, 51-85 (2011) · Zbl 1252.68151
[9] Kammer, F.; Tholey, T., The complexity of minimum convex coloring, Discrete Appl. Math., 160, 810-833 (2012) · Zbl 1238.05091
[10] Kanj, I. A.; Kratsch, D., Convex recoloring revisited: Complexity and exact algorithms, (Ngo, H. Q., Computing and Combinatorics. Proceedings of the International Computing and Combinatorics Conference. Computing and Combinatorics. Proceedings of the International Computing and Combinatorics Conference, COCOON 2009. Computing and Combinatorics. Proceedings of the International Computing and Combinatorics Conference. Computing and Combinatorics. Proceedings of the International Computing and Combinatorics Conference, COCOON 2009, Lecture Notes in Computer Science, vol. 5609 (2009)), 388-397 · Zbl 1248.05201
[11] Lima, K. R.; Wakabayashi, Y., Convex recoloring of paths, Discrete Appl. Math., 164, part 2, 450-459 (2014) · Zbl 1288.05095
[12] Moran, S.; Snir, S., Efficient approximation of convex recolorings, J. Comput. System Sci., 73, 7, 1078-1089 (2007) · Zbl 1123.68095
[13] Moran, S.; Snir, S., Convex recolorings of strings and trees: Definitions, hardness results and algorithms, J. Comput. System Sci., 74, 5, 850-869 (2008) · Zbl 1160.68025
[14] Moran, S.; Snir, S.; Sung, W.-K., Partial convex recolorings of trees and galled networks: Tight upper and lower bounds, ACM Trans. Algorithms, 7, 4, 42:1-42:20 (2011) · Zbl 1295.05236
[15] Moura, P. F.S.; Wakabayashi, Y., Strong intractability of generalized convex recoloring problems, (Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium. Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2017. Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium. Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2017, Electronic Notes in Discrete Mathematics, vol. 62 (2017)), 93-98 · Zbl 1383.05114
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.