Dual Parameterization of Weighted Coloring

Authors Júlio Araújo , Victor A. Campos, Carlos Vinícius G. C. Lima , Vinícius Fernandes dos Santos , Ignasi Sau , Ana Silva



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.12.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Júlio Araújo
  • Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil
Victor A. Campos
  • Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brazil
Carlos Vinícius G. C. Lima
  • Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
Vinícius Fernandes dos Santos
  • Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
Ignasi Sau
  • LIRMM, CNRS, Université de Montpellier, Montpellier, France
Ana Silva
  • Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil

Cite AsGet BibTex

Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Ana Silva. Dual Parameterization of Weighted Coloring. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.IPEC.2018.12

Abstract

Given a graph G, a proper k-coloring of G is a partition c = (S_i)_{i in [1,k]} of V(G) into k stable sets S_1,..., S_k. Given a weight function w: V(G) -> R^+, the weight of a color S_i is defined as w(i) = max_{v in S_i} w(v) and the weight of a coloring c as w(c) = sum_{i=1}^{k} w(i). Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair (G,w), denoted by sigma(G,w), as the minimum weight of a proper coloring of G. The problem of determining sigma(G,w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time n^{o(log n)} unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G,w) and an integer k, is sigma(G,w) <= sum_{v in V(G)} w(v) - k? This parameterization has been recently considered by Escoffier [WG, 2016], who provided an FPT algorithm running in time 2^{O(k log k)} * n^{O(1)}, and asked which kernel size can be achieved for the problem. We provide an FPT algorithm running in time 9^k * n^{O(1)}, and prove that no algorithm in time 2^{o(k)} * n^{O(1)} exists under the ETH. On the other hand, we present a kernel with at most (2^{k-1}+1) (k-1) vertices, and rule out the existence of polynomial kernels unless NP subseteq coNP/poly, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • weighted coloring
  • max coloring
  • parameterized complexity
  • dual parameterization
  • FPT algorithms
  • polynomial kernels
  • split graphs
  • interval graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Júlio Araújo, Julien Baste, and Ignasi Sau. Ruling out FPT algorithms for Weighted Coloring on forests. Theoretical Computer Science, 729:11-19, 2018. Google Scholar
  2. Júlio Araújo, Nicolas Nisse, and Stéphane Pérennes. Weighted Coloring in Trees. SIAM Journal on Discrete Mathematics, 28(4):2029-2041, 2014. Google Scholar
  3. Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, and Saket Saurabh. Partially Polynomial Kernels for Set Cover and Test Cover. SIAM Journal on Discrete Mathematics, 30(3):1401-1423, 2016. URL: http://dx.doi.org/10.1137/15M1039584.
  4. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set Partitioning via Inclusion-Exclusion. SIAM Journal on Computing, 39(2):546-563, 2009. Google Scholar
  5. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. Journal of Computer and System Sciences, 75(8):423-434, 2009. Google Scholar
  6. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. SIAM Journal on Discrete Mathematics, 28(1):277-305, 2014. Google Scholar
  7. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theoretical Computer Science, 412(35):4570-4578, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.04.039.
  8. Édouard Bonnet and Vangelis Th. Paschos. Dual parameterization and parameterized approximability of subset graph problems. RAIRO - Operations Research, 51(1):261-266, 2017. URL: http://dx.doi.org/10.1051/ro/2016018.
  9. Benny Chor, Mike Fellows, and David W. Juedes. Linear Kernels in Linear Time, or How to Save k Colors in O(n²) Steps. In Proc. of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 3353 of LNCS, pages 257-269, 2004. URL: http://dx.doi.org/10.1007/978-3-540-30559-0_22.
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  11. Dominique de Werra, Marc Demange, Bruno Escoffier, Jérôme Monnot, and Vangelis Th. Paschos. Weighted coloring on planar, bipartite and split graphs: Complexity and approximation. Discrete Applied Mathematics, 157(4):819-832, 2009. Google Scholar
  12. Marc Demange, Dominique de Werra, Jérôme Monnot, and Vangelis Th. Paschos. Weighted Node Coloring: When Stable Sets Are Expensive. In Proc. of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 2573 of LNCS, pages 114-125. Springer, 2002. Google Scholar
  13. Marc Demange, Pascal Grisoni, and Vangelis Th. Paschos. Approximation Results for the Minimum Graph Coloring Problem. Information Processing Letters, 50(1):19-23, 1994. URL: http://dx.doi.org/10.1016/0020-0190(94)90039-6.
  14. Reinhard Diestel. Graph Theory, volume 173. Springer-Verlag, 4th edition, 2010. Google Scholar
  15. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization Lower Bounds Through Colors and IDs. ACM Transactions on Algorithms, 11(2):13:1-13:20, 2014. URL: http://dx.doi.org/10.1145/2650261.
  16. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  17. Rong-chii Duh and Martin Fürer. Approximation of k-Set Cover by Semi-Local Optimization. In Proc. of the 29th Annual ACM Symposium on the Theory of Computing (STOC), pages 256-264, 1997. URL: http://dx.doi.org/10.1145/258533.258599.
  18. Bruno Escoffier. Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results. In Proc. of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 9941 of LNCS, pages 50-61, 2016. Google Scholar
  19. Bruno Escoffier, Jérôme Monnot, and Vangelis Th. Paschos. Weighted Coloring: further complexity and approximability results. Information Processing Letters, 97(3):98-103, 2006. Google Scholar
  20. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010. Google Scholar
  21. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences, 77(1):91-106, 2011. Google Scholar
  22. Delbert Fulkerson and Oliver Gross. Incidence matrices and interval graphs. Pacific journal of mathematics, 15(3):835-855, 1965. Google Scholar
  23. P. Gilmore and A. Hoffman. A characterization of comparability graphs and of interval graphs. Canadian Journal of Mathematics, 16:539-548, 1964. Google Scholar
  24. D. J. Guan and Xuding Zhu. A Coloring Problem for Weighted Graphs. Information Processing Letters, 61(2):77-81, 1997. Google Scholar
  25. Gregory Z. Gutin, Mark Jones, and Anders Yeo. Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems. Theoretical Computer Science, 412(41):5744-5751, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.06.018.
  26. Magnús M. Halldórsson. Approximating Discrete Collections via Local Improvements. In Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 160-169, 1995. URL: http://dl.acm.org/citation.cfm?id=313651.313687.
  27. Magnús M. Halldórsson. Approximating k-Set Cover and Complementary Graph Coloring. In Proc. of the 5th International Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 1084 of LNCS, pages 118-131, 1996. URL: http://dx.doi.org/10.1007/3-540-61310-2_10.
  28. Refael Hassin and Shlomo Lahav. Maximizing the Number of Unused Colors in the Vertex Coloring Problem. Information Processing Letters, 52(2):87-90, 1994. URL: http://dx.doi.org/10.1016/0020-0190(94)00113-8.
  29. Frédéric Havet and Leonardo Sampaio. On the Grundy and b-Chromatic Numbers of a Graph. Algorithmica, 65(4):885-899, 2013. Google Scholar
  30. Danny Hermelin and Xi Wu. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proc. of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 104-113, 2012. Google Scholar
  31. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  32. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  33. Richard M. Karp. Reducibility Among Combinatorial Problems. In Proc. of a symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  34. Telikepalli Kavitha and Julián Mestre. Max-coloring paths: tight bounds and extensions. Journal of Combinatorial Optimization, 24(1):1-14, 2012. Google Scholar
  35. E. L. Lawler. A note on the complexity of the chromatic number problem. Information Processing Letters, 5(3):66-67, 1976. URL: http://dx.doi.org/10.1016/0020-0190(76)90065-X.
  36. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 105:41-72, 2011. URL: http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96.
  37. Sriram V. Pemmaraju, Sriram Penumatcha, and Rajiv Raman. Approximating interval coloring and max-coloring in chordal graphs. ACM Journal of Experimental Algorithmics, 10, 2005. Google Scholar
  38. Chee-Keng Yap. Some Consequences of Non-Uniform Conditions on Uniform Classes. Theoretical Computer Science, 26:287-300, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail