Parameterized (Approximate) Defective Coloring

Authors Rémy Belmonte, Michael Lampis, Valia Mitsou



PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.10.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Rémy Belmonte
Michael Lampis
Valia Mitsou

Cite AsGet BibTex

Rémy Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (Approximate) Defective Coloring. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.STACS.2018.10

Abstract

In Defective Coloring we are given a graph G=(V,E) and two integers chi_d,Delta^* and are asked if we can partition V into chi_d color classes, so that each class induces a graph of maximum degree Delta^*. We investigate the complexity of this generalization of Coloring with respect to several well-studied graph parameters, and show that the problem is W-hard parameterized by treewidth, pathwidth, tree-depth, or feedback vertex set, if chi_d=2. As expected, this hardness can be extended to larger values of chi_d for most of these parameters, with one surprising exception: we show that the problem is FPT parameterized by feedback vertex set for any chi_d != 2, and hence 2-coloring is the only hard case for this parameter. In addition to the above, we give an ETH-based lower bound for treewidth and pathwidth, showing that no algorithm can solve the problem in n^{o(pw)}, essentially matching the complexity of an algorithm obtained with standard techniques. We complement these results by considering the problem's approximability and show that, with respect to Delta^*, the problem admits an algorithm which for any epsilon>0 runs in time (tw/epsilon)^{O(tw)} and returns a solution with exactly the desired number of colors that approximates the optimal Delta^* within (1+epsilon). We also give a (tw)^{O(tw)} algorithm which achieves the desired Delta^* exactly while 2-approximating the minimum value of chi_d. We show that this is close to optimal, by establishing that no FPT algorithm can (under standard assumptions) achieve a better than 3/2-approximation to chi_d, even when an extra constant additive error is also allowed.
Keywords
  • Treewidth
  • Parameterized Complexity
  • Approximation
  • Coloring

Metrics

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

References

  1. Nirmala Achuthan, N. R. Achuthan, and M. Simanihuruk. On minimal triangle-free graphs with prescribed k-defective chromatic number. Discrete Mathematics, 311(13):1119-1127, 2011. URL: http://dx.doi.org/10.1016/j.disc.2010.08.013.
  2. James A Andrews and Michael S Jacobson. On a generalization of chromatic number. Congressus Numerantium, 47:33-48, 1985. Google Scholar
  3. Eric Angel, Evripidis Bampis, Bruno Escoffier, and Michael Lampis. Parameterized power vertex cover. In Pinar Heggernes, editor, Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, volume 9941 of Lecture Notes in Computer Science, pages 97-108, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53536-3_9.
  4. Patrizio Angelini, Michael A. Bekos, Felice De Luca, Walter Didimo, Michael Kaufmann, Stephen G. Kobourov, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Vincenzo Roselli, and Antonios Symvonis. Vertex-coloring with defects. J. Graph Algorithms Appl., 21(3):313-340, 2017. URL: http://dx.doi.org/10.7155/jgaa.00418.
  5. Júlio Araújo, Jean-Claude Bermond, Frédéric Giroire, Frédéric Havet, Dorian Mazauric, and Remigiusz Modrzejewski. Weighted improper colouring. J. Discrete Algorithms, 16:53-66, 2012. URL: http://dx.doi.org/10.1016/j.jda.2012.07.001.
  6. Dan Archdeacon. A note on defective colorings of graphs in surfaces. Journal of Graph Theory, 11(4):517-519, 1987. URL: http://dx.doi.org/10.1002/jgt.3190110408.
  7. Claudia Archetti, Nicola Bianchessi, Alain Hertz, Adrien Colombet, and François Gagnon. Directed weighted improper coloring for cellular channel allocation. Discrete Applied Mathematics, 182:46-60, 2015. URL: http://dx.doi.org/10.1016/j.dam.2013.11.018.
  8. Jørgen Bang-Jensen and Magnús M. Halldórsson. Vertex coloring edge-weighted digraphs. Inf. Process. Lett., 115(10):791-796, 2015. URL: http://dx.doi.org/10.1016/j.ipl.2015.05.007.
  9. Rémy Belmonte, Michael Lampis, and Valia Mitsou. Defective coloring on classes of perfect graphs. CoRR, abs/1702.08903, 2017. URL: http://arxiv.org/abs/1702.08903.
  10. Jean-Claude Bermond, Frédéric Havet, Florian Huc, and Cláudia Linhares Sales. Improper coloring of weighted grid and hexagonal graphs. Discrete Math., Alg. and Appl., 2(3):395-412, 2010. URL: http://dx.doi.org/10.1142/S1793830910000747.
  11. Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput., 27(6):1725-1746, 1998. URL: http://dx.doi.org/10.1137/S0097539795289859.
  12. Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. Comput. J., 51(3):255-269, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm037.
  13. Oleg V. Borodin, Alexandr V. Kostochka, and Matthew P. Yancey. On 11-improper 22-coloring of sparse graphs. Discrete Mathematics, 313(22):2638-2649, 2013. URL: http://dx.doi.org/10.1016/j.disc.2013.07.014.
  14. I. Choi and L. Esperet. Improper coloring of graphs on surfaces. ArXiv e-prints, 2016. URL: http://arxiv.org/abs/1603.02841.
  15. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. URL: http://dx.doi.org/10.1007/s002249910009.
  16. Lenore Cowen, Wayne Goddard, and C. Esther Jesurum. Defective coloring revisited. Journal of Graph Theory, 24(3):205-219, 1997. URL: http://dx.doi.org/10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T.
  17. Lenore J. Cowen, Robert Cowen, and Douglas R. Woodall. Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency. Journal of Graph Theory, 10(2):187-195, 1986. URL: http://dx.doi.org/10.1002/jgt.3190100207.
  18. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  19. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  20. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth. Inf. Comput., 209(2):143-153, 2011. URL: http://dx.doi.org/10.1016/j.ic.2010.11.026.
  21. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: http://dx.doi.org/10.1007/3-540-29953-X.
  22. Marietjie Frick. A survey of (m, k)-colorings. Annals of Discrete Mathematics, 55:45-57, 1993. Google Scholar
  23. Marietjie Frick and Michael A. Henning. Extremal results on defective colorings of graphs. Discrete Mathematics, 126(1-3):151-158, 1994. URL: http://dx.doi.org/10.1016/0012-365X(94)90260-7.
  24. Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak. Parameterized algorithms for modular-width. In Gregory Gutin and Stefan Szeider, editors, Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, volume 8246 of Lecture Notes in Computer Science, pages 163-176. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03898-8_15.
  25. Wayne Goddard and Honghai Xu. Fractional, circular, and defective coloring of series-parallel graphs. Journal of Graph Theory, 81(2):146-153, 2016. URL: http://dx.doi.org/10.1002/jgt.21868.
  26. Bjarki Agust Gudmundsson, Tómas Ken Magnússon, and Björn Orri Sæmundsson. Bounds and fixed-parameter algorithms for weighted improper coloring. Electr. Notes Theor. Comput. Sci., 322:181-195, 2016. URL: http://dx.doi.org/10.1016/j.entcs.2016.03.013.
  27. Frédéric Havet, Ross J. Kang, and Jean-Sébastien Sereni. Improper coloring of unit disk graphs. Networks, 54(3):150-164, 2009. URL: http://dx.doi.org/10.1002/net.20318.
  28. Frédéric Havet and Jean-Sébastien Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006. URL: http://dx.doi.org/10.1002/jgt.20155.
  29. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  30. Lars Jaffke and Bart M. P. Jansen. Fine-grained parameterized complexity analysis of graph coloring problems. CoRR, abs/1701.06985, 2017. URL: http://arxiv.org/abs/1701.06985.
  31. Ross J. Kang. Improper colourings of graphs. PhD thesis, University of Oxford, UK, 2008. URL: http://ora.ox.ac.uk/objects/uuid:a93d8303-0eeb-4d01-9b77-364113b81a63.
  32. Ross J. Kang and Colin McDiarmid. The t-improper chromatic number of random graphs. Combinatorics, Probability & Computing, 19(1):87-98, 2010. URL: http://dx.doi.org/10.1017/S0963548309990216.
  33. Jaehoon Kim, Alexandr V. Kostochka, and Xuding Zhu. Improper coloring of sparse graphs with a given girth, I: (0, 1)-colorings of triangle-free graphs. Eur. J. Comb., 42:26-48, 2014. URL: http://dx.doi.org/10.1016/j.ejc.2014.05.003.
  34. Jaehoon Kim, Alexandr V. Kostochka, and Xuding Zhu. Improper coloring of sparse graphs with a given girth, II: constructions. Journal of Graph Theory, 81(4):403-413, 2016. URL: http://dx.doi.org/10.1002/jgt.21886.
  35. Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1):19-37, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9554-x.
  36. Michael Lampis. Parameterized approximation schemes using graph widths. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 775-786. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_64.
  37. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs on bounded treewidth are probably optimal. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 777-789. SIAM, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.61.
  38. Jaroslav Nesetril and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb., 27(6):1022-1041, 2006. URL: http://dx.doi.org/10.1016/j.ejc.2005.01.010.
  39. R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. OUP Oxford, 2006. URL: https://books.google.fr/books?id=mAA_OkeJxhsC.
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