Document Open Access Logo

Finding Large H-Colorable Subgraphs in Hereditary Graph Classes

Authors Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski , Sophie Spirkl

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.35.pdf
  • Filesize: 0.92 MB
  • 17 pages

Document Identifiers

Author Details

Maria Chudnovsky
  • Princeton University, NJ, USA
Jason King
  • Princeton University, NJ, USA
Michał Pilipczuk
  • Institute of Informatics, University of Warsaw, Poland
Paweł Rzążewski
  • Warsaw University of Technology, Faculty of Mathematics and Information Science, Poland
  • University of Warsaw, Institute of Informatics, Poland
Sophie Spirkl
  • Princeton University, NJ, USA

Funding

  • Chudnovsky, Maria: This material is based upon work supported in part by the U. S. Army Research Office under grant number W911NF-16-1-0404, and by NSF grant DMS-1763817.
  • Pilipczuk, Michał: This work is a part of project TOTAL that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 677651).
  • Rzążewski, Paweł: Supported by Polish National Science Centre grant no. 2018/31/D/ST6/00062.
  • Spirkl, Sophie: This material is based upon work supported by the National Science Foundation under Award No. DMS1802201.

Acknowledgements

We acknowledge the welcoming and productive atmosphere at Dagstuhl Seminar 19271 "Graph Colouring: from Structure to Algorithms", where this work has been initiated.

Cite As Get BibTex

Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, and Sophie Spirkl. Finding Large H-Colorable Subgraphs in Hereditary Graph Classes. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.35

Abstract

We study the Max Partial H-Coloring problem: given a graph G, find the largest induced subgraph of G that admits a homomorphism into H, where H is a fixed pattern graph without loops. Note that when H is a complete graph on k vertices, the problem reduces to finding the largest induced k-colorable subgraph, which for k = 2 is equivalent (by complementation) to Odd Cycle Transversal.
We prove that for every fixed pattern graph H without loops, Max Partial H-Coloring can be solved:  
- in {P₅,F}-free graphs in polynomial time, whenever F is a threshold graph; 
- in {P₅,bull}-free graphs in polynomial time; 
- in P₅-free graphs in time n^𝒪(ω(G)); 
- in {P₆,1-subdivided claw}-free graphs in time n^𝒪(ω(G)³).  Here, n is the number of vertices of the input graph G and ω(G) is the maximum size of a clique in G. Furthermore, by combining the mentioned algorithms for P₅-free and for {P₆,1-subdivided claw}-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for Max Partial H-Coloring in these classes of graphs.
Finally, we show that even a restricted variant of Max Partial H-Coloring is NP-hard in the considered subclasses of P₅-free graphs, if we allow loops on H.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • homomorphisms
  • hereditary graph classes
  • odd cycle transversal

Metrics

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

Related Versions

References

  1. Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, and Paul Seymour. Induced subgraphs of bounded treewidth and the container method. CoRR, abs/2003.05185, 2020. URL: http://arxiv.org/abs/2003.05185.
  2. Vladimir E. Alekseev. The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-algebraic methods in applied mathematics, pages 3-13, 1982. (in Russian). Google Scholar
  3. Vladimir E. Alekseev. Polynomial algorithm for finding the largest independent sets in graphs without forks. Discret. Appl. Math., 135(1-3):3-16, 2004. URL: https://doi.org/10.1016/S0166-218X(02)00290-1.
  4. Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, and Erik Jan van Leeuwen. Subexponential-time algorithms for Maximum Independent Set in P_t-free and broom-free graphs. Algorithmica, 81(2):421-438, 2019. URL: https://doi.org/10.1007/s00453-018-0479-5.
  5. Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Oliver Schaudt, Maya Stein, and Mingxian Zhong. Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Combinatorica, 38(4):779-801, 2018. URL: https://doi.org/10.1007/s00493-017-3553-8.
  6. Christoph Brause. A subexponential-time algorithm for the Maximum Independent Set problem in P_t-free graphs. Discret. Appl. Math., 231:113-118, 2017. URL: https://doi.org/10.1016/j.dam.2016.06.016.
  7. Nick Brettell, Jake Horsfield, and Daniël Paulusma. Colouring sP₁+P₅-free graphs: a mim-width perspective. CoRR, abs/2004.05022, 2020. URL: http://arxiv.org/abs/2004.05022.
  8. Maria Chudnovsky, Jason King, Michal Pilipczuk, Paweł Rzążewski, and Sophie Spirkl. Finding large H-colorable subgraphs in hereditary graph classes. CoRR, abs/2004.09425, 2020. URL: http://arxiv.org/abs/2004.09425.
  9. Maria Chudnovsky, Daniël Paulusma, and Oliver Schaudt. Graph colouring: from structure to algorithms (dagstuhl seminar 19271). Dagstuhl Reports, 9(6):125-142, 2019. URL: https://doi.org/10.4230/DagRep.9.6.125.
  10. Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set problem in H-free graphs. In Proceedings of the 31^st ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 2260-2278. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.139.
  11. Maria Chudnovsky and Shmuel Safra. The Erdős-Hajnal conjecture for bull-free graphs. J. Comb. Theory, Ser. B, 98(6):1301-1310, 2008. URL: https://doi.org/10.1016/j.jctb.2008.02.005.
  12. Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl, Maya Stein, and Mingxian Zhong. Approximately coloring graphs without long induced paths. Algorithmica, 81(8):3186-3199, 2019. URL: https://doi.org/10.1007/s00453-019-00577-6.
  13. Maria Chudnovsky and Vaidy Sivaraman. Odd holes in bull-free graphs. SIAM J. Discrete Math., 32(2):951-955, 2018. URL: https://doi.org/10.1137/17M1131301.
  14. Maria Chudnovsky, Sophie Spirkl, and Mingxian Zhong. Four-coloring P₆-free graphs. In Proceedings of the 30^th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 1239-1256. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.76.
  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: https://doi.org/10.1007/s002249910009.
  16. Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski. On cycle transversals and their connected variants in the absence of a small linear forest. CoRR, abs/1908.00491, 2019. Accepted to Algorithmica. URL: http://arxiv.org/abs/1908.00491.
  17. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM J. Comput., 44(1):54-87, 2015. URL: https://doi.org/10.1137/140964801.
  18. Petr A. Golovach, Daniël Paulusma, and Jian Song. Closing complexity gaps for coloring problems on H-free graphs. Inf. Comput., 237:204-214, 2014. URL: https://doi.org/10.1016/j.ic.2014.02.004.
  19. Carla Groenland, Karolina Okrasa, Paweł Rzążewski, Alex D. Scott, Paul D. Seymour, and Sophie Spirkl. H-colouring P_t-free graphs in subexponential time. Discret. Appl. Math., 267:184-189, 2019. URL: https://doi.org/10.1016/j.dam.2019.04.010.
  20. Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, and Michał Pilipczuk. Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs. In Proceedings of the 30^th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 1257-1271. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.77.
  21. Gregory Z. Gutin, Pavol Hell, Arash Rafiey, and Anders Yeo. A dichotomy for minimum cost graph homomorphisms. Eur. J. Comb., 29(4):900-911, 2008. URL: https://doi.org/10.1016/j.ejc.2007.11.012.
  22. Chính T Hoàng, Marcin Kamiński, Vadim Lozin, Joe Sawada, and Xiao Shu. Deciding k-colorability of P₅-free graphs in polynomial time. Algorithmica, 57(1):74-81, 2010. Google Scholar
  23. Shenwei Huang. Improved complexity results on k-coloring P_t-free graphs. Eur. J. Comb., 51:336-346, 2016. URL: https://doi.org/10.1016/j.ejc.2015.06.005.
  24. Daniel Lokshtanov, Martin Vatshelle, and Yngve Villanger. Independent set in P₅-free graphs in polynomial time. In Proceedings of the 25^th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 570-581. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.43.
  25. Vadim V. Lozin and Martin Milanič. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discrete Algorithms, 6(4):595-604, 2008. URL: https://doi.org/10.1016/j.jda.2008.04.001.
  26. George J. Minty. On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory, Ser. B, 28(3):284-304, 1980. URL: https://doi.org/10.1016/0095-8956(80)90074-X.
  27. Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, and Bartosz Walczak. Subexponential-time algorithms for finding large induced sparse subgraphs. In Proceedings of the 14^th International Symposium on Parameterized and Exact Computation, IPEC 2019, volume 148 of LIPIcs, pages 23:1-23:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.23.
  28. Karolina Okrasa and Paweł Rzążewski. Subexponential algorithms for variants of the homomorphism problem in string graphs. J. Comput. Syst. Sci., 109:126-144, 2020. URL: https://doi.org/10.1016/j.jcss.2019.12.004.
  29. Najiba Sbihi. Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile. Discrete Mathematics, 29(1):53-76, 1980. (in French). 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact