[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Dual Parameterization of Weighted Coloring

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Given a graph G, a properk-coloring of G is a partition \(c = (S_i)_{i\in [1,k]}\) of V(G) into k stable sets \(S_1,\ldots , S_{k}\). Given a weight function \(w: V(G) \rightarrow {\mathbb {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 coloringc as \(w(c) = \sum _{i=1}^{k}w(i)\). Guan and Zhu (Inf Process Lett 61(2):77–81, 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) \le \sum _{v \in V(G)} w(v) - k\)? This parameterization has been recently considered by Escoffier (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50–61, 2016), who provided an FPT algorithm running in time \(2^{{\mathcal {O}}(k \log k)} \cdot n^{{\mathcal {O}}(1)}\), and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time \(9^k \cdot n^{{\mathcal {O}}(1)}\), and prove that no algorithm in time \(2^{o(k)} \cdot n^{{\mathcal {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 \(\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}\), even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. The ETH states that 3-SAT cannot be solved in subexponential time; see [31, 32] for more details.

References

  1. Araújo, J., Baste, J., Sau, I.: Ruling out FPT algorithms for weighted coloring on forests. Theor. Comput. Sci. 729, 11–19 (2018)

    Article  MathSciNet  Google Scholar 

  2. Araújo, J., Nisse, N., Pérennes, S.: Weighted coloring in trees. SIAM J. Discrete Math. 28(4), 2029–2041 (2014)

    Article  MathSciNet  Google Scholar 

  3. Basavaraju, M., Francis, M.C., Ramanujan, M.S., Saurabh, S.: Partially polynomial kernels for set cover and test cover. SIAM J. Discrete Math. 30(3), 1401–1423 (2016)

    Article  MathSciNet  Google Scholar 

  4. Björklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion–exclusion. SIAM J. Comput. 39(2), 546–563 (2009)

    Article  MathSciNet  Google Scholar 

  5. Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)

    Article  MathSciNet  Google Scholar 

  6. Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277–305 (2014)

    Article  MathSciNet  Google Scholar 

  7. Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)

    Article  MathSciNet  Google Scholar 

  8. Bonnet, É., Paschos, V.T.: Dual parameterization and parameterized approximability of subset graph problems. RAIRO Oper. Res. 51(1), 261–266 (2017)

    Article  MathSciNet  Google Scholar 

  9. Chor, B., Fellows, M., Juedes, D.W.: Linear kernels in linear time, or how to save \(k\) colors in \(O(n^2)\) steps. In: Procedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 3353 of LNCS, pp. 257–269 (2004)

  10. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)

    Book  Google Scholar 

  11. de Werra, D., Demange, M., Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring on planar, bipartite and split graphs: complexity and approximation. Discrete Appl. Math. 157(4), 819–832 (2009)

    Article  MathSciNet  Google Scholar 

  12. Demange, M., de Werra, D., Monnot, J., Paschos, V.T.: Weighted node coloring: when stable sets are expensive. In: Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 2573 of LNCS, pp. 114–125. Springer (2002)

  13. Demange, M., Grisoni, P., Paschos, V.T.: Approximation results for the minimum graph coloring problem. Inf. Process. Lett. 50(1), 19–23 (1994)

    Article  MathSciNet  Google Scholar 

  14. Diestel, R.: Graph Theory, vol. 173, 4th edn. Springer, Berlin (2010)

    Book  Google Scholar 

  15. Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDs. ACM Trans. Algorithms 11(2), 13:1–13:20 (2014)

    Article  MathSciNet  Google Scholar 

  16. Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)

    Book  Google Scholar 

  17. Duh, R., Fürer, M.: Approximation of \(k\)-set cover by semi-local optimization. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC), pp. 256–264 (1997)

  18. Escoffier, B.: Saving colors and max coloring: some fixed-parameter tractability results. In: Proceedings of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG). LNCS, vol. 9941, pp. 50–61 (2016)

  19. Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring: further complexity and approximability results. Inf. Process. Lett. 97(3), 98–103 (2006)

    Article  MathSciNet  Google Scholar 

  20. Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2010)

    Google Scholar 

  21. Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91–106 (2011)

    Article  MathSciNet  Google Scholar 

  22. Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835–855 (1965)

    Article  MathSciNet  Google Scholar 

  23. Gilmore, P., Hoffman, A.: A characterization of comparability graphs and of interval graphs. Can. J. Math. 16, 539–548 (1964)

    Article  MathSciNet  Google Scholar 

  24. Guan, D.J., Zhu, X.: A coloring problem for weighted graphs. Inf. Process. Lett. 61(2), 77–81 (1997)

    Article  MathSciNet  Google Scholar 

  25. Gutin, G.Z., Jones, M., Yeo, A.: Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems. Theor. Comput. Sci. 412(41), 5744–5751 (2011)

    Article  MathSciNet  Google Scholar 

  26. Halldórsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 160–169 (1995)

  27. Halldórsson, M.M.: Approximating \(k\)-set cover and complementary graph coloring. In: Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization (IPCO). LNCS, vol. 1084, pp. 118–131 (1996)

  28. Hassin, R., Lahav, S.: Maximizing the number of unused colors in the vertex coloring problem. Inf. Process. Lett. 52(2), 87–90 (1994)

    Article  MathSciNet  Google Scholar 

  29. Havet, F., Sampaio, L.: On the grundy and \(b\)-chromatic numbers of a graph. Algorithmica 65(4), 885–899 (2013)

    Article  MathSciNet  Google Scholar 

  30. Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower bounds for kernelization. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 104–113 (2012)

  31. Impagliazzo, R., Paturi, R.: On the complexity of \(k\)-SAT. J. Comput. Syst. Sci. 62(2), 367–375 (2001)

    Article  MathSciNet  Google Scholar 

  32. Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)

    Article  MathSciNet  Google Scholar 

  33. Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85–103. Plenum Press, New York (1972)

  34. Kavitha, T., Mestre, J.: Max-coloring paths: tight bounds and extensions. J. Comb. Optim. 24(1), 1–14 (2012)

    Article  MathSciNet  Google Scholar 

  35. Lawler, E.L.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5(3), 66–67 (1976)

    Article  MathSciNet  Google Scholar 

  36. Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.: Normal helly circular-arc graphs and its subclasses. Discrete Appl. Math. 161(7–8), 1037–1059 (2013)

    Article  MathSciNet  Google Scholar 

  37. Lin, M.C., Szwarcfiter, J.L.: Characterizations and recognition of circular-arc graphs and subclasses: a survey. Discrete Math. 309(18), 5618–5635 (2009)

    Article  MathSciNet  Google Scholar 

  38. Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41–72 (2011)

    MathSciNet  MATH  Google Scholar 

  39. Pemmaraju, S.V., Penumatcha, S., Raman, R.: Approximating interval coloring and max-coloring in chordal graphs. ACM J. Exp. Algorithmics 10, 2–8 (2005)

    MathSciNet  MATH  Google Scholar 

  40. Tucker, A.: Matrix characterizations of circular-arc graphs. Pac. J. Math. 39(2), 535–545 (1971)

    Article  MathSciNet  Google Scholar 

  41. Yap, C.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287–300 (1983)

    Article  Google Scholar 

Download references

Acknowledgements

We would like to thank the anonymous reviewers for carefully reading the conference version of this article [IPEC 2018], in particular for spotting a flaw in the proof of Claim 5, which we rewrote completely in a simpler way. We also thank Mikko Koivisto for pointing us to reference [4].

Funding

Work supported by French Projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010), and by Brazilian Projects CNPq 306262/2014-2, CNPq 311013/2015-5, CNPq Universal 421660/2016-3, CNPq Universal 401519/2016-3, FAPEMIG, Funcap PNE-0112-00061.01.00/16, and Coordenação de Aperfeiçoamento de Pessoal de Nível Superior—Brasil (CAPES)—Finance Code 001.

Author information

Authors and Affiliations

  1. Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil

    Júlio Araújo & Ana Silva

  2. Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brazil

    Victor A. Campos

  3. Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

    Carlos Vinícius G. C. Lima & Vinícius Fernandes dos Santos

  4. LIRMM, Université de Montpellier, CNRS, Montpellier, France

    Ignasi Sau

Authors
  1. Júlio Araújo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Victor A. Campos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Carlos Vinícius G. C. Lima
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Vinícius Fernandes dos Santos
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ignasi Sau
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Ana Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ignasi Sau.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is permanently available at [arXiv:1805.06699]. A conference version appeared in the Proc. of the 13th International Symposium on Parameterized and Exact Computation (IPEC), volume 115 of LIPIcs, pages 12:1–12:14, Helsinki, Finland, August 2018.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Araújo, J., Campos, V.A., Lima, C.V.G.C. et al. Dual Parameterization of Weighted Coloring. Algorithmica 82, 2316–2336 (2020). https://doi.org/10.1007/s00453-020-00686-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-020-00686-7

Keywords

ACM Subject Classification (2012)

Search

Navigation