Document Open Access Logo

Complexity of the List Homomorphism Problem in Hereditary Graph Classes

Authors Karolina Okrasa , Paweł Rzążewski

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2021.54.pdf
  • Filesize: 0.85 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Graph algorithms analysis
Keywords
  • list homomorphism
  • fine-grained complexity
  • hereditary graph classes

Metrics

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

Abstract

A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). For a fixed graph H, in the list homomorphism problem, denoted by LHom(H), we are given a graph G, whose every vertex v is equipped with a list L(v) ⊆ V(H). We ask if there exists a homomorphism f from G to H, in which f(v) ∈ L(v) for every v ∈ V(G). Feder, Hell, and Huang [JGT 2003] proved that LHom(H) is polynomial time-solvable if H is a so-called bi-arc-graph, and NP-complete otherwise.
We are interested in the complexity of the LHom(H) problem in F-free graphs, i.e., graphs excluding a copy of some fixed graph F as an induced subgraph. It is known that if F is connected and is not a path nor a subdivided claw, then for every non-bi-arc graph the LHom(H) problem is NP-complete and cannot be solved in subexponential time, unless the ETH fails. We consider the remaining cases for connected graphs F.
If F is a path, we exhibit a full dichotomy. We define a class called predacious graphs and show that if H is not predacious, then for every fixed t the LHom(H) problem can be solved in quasi-polynomial time in P_t-free graphs. On the other hand, if H is predacious, then there exists t, such that the existence of a subexponential-time algorithm for LHom(H) in P_t-free graphs would violate the ETH.
If F is a subdivided claw, we show a full dichotomy in two important cases: for H being irreflexive (i.e., with no loops), and for H being reflexive (i.e., where every vertex has a loop). Unless the ETH fails, for irreflexive H the LHom(H) problem can be solved in subexponential time in graphs excluding a fixed subdivided claw if and only if H is non-predacious and triangle-free. On the other hand, if H is reflexive, then LHom(H) cannot be solved in subexponential time whenever H is not a bi-arc graph.

Cite As Get BibTex

Karolina Okrasa and Paweł Rzążewski. Complexity of the List Homomorphism Problem in Hereditary Graph Classes. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.STACS.2021.54

Author Details

Karolina Okrasa
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
  • Institute of Informatics, University of Warsaw, Poland
Paweł Rzążewski
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
  • Institute of Informatics, University of Warsaw, Poland

Funding

  • Okrasa, Karolina: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement no. 714704.
  • Rzążewski, Paweł: Supported by Polish National Science Centre grant no. 2018/31/D/ST6/00062.

References

  1. 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.
  2. Andrei A. Bulatov. H-Coloring dichotomy revisited. Theor. Comput. Sci., 349(1):31-39, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.028.
  3. Maria Chudnovsky, Shenwei Huang, Pawel Rzążewski, Sophie Spirkl, and Mingxian Zhong. Complexity of C_k-coloring in hereditary classes of graphs. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 31:1-31:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.31.
  4. Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, and Sophie Spirkl. Finding large H-colorable subgraphs in hereditary graph classes. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 35:1-35:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.35.
  5. Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, and Stéphan Thomassé. Quasi-polynomial time approximation schemes for the maximum weight independent set problem in H-free graphs. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2260-2278. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.139.
  6. Maria Chudnovsky and Paul D. Seymour. The three-in-a-tree problem. Combinatorica, 30(4):387-417, 2010. URL: https://doi.org/10.1007/s00493-010-2334-4.
  7. Víctor Dalmau, László Egri, Pavol Hell, Benoit Larose, and Arash Rafiey. Descriptive complexity of list H-coloring problems in logspace: A refined dichotomy. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pages 487-498. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/LICS.2015.52.
  8. László Egri, Pavol Hell, Benoit Larose, and Arash Rafiey. Space complexity of list H-colouring: a dichotomy. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 349-365. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.26.
  9. László Egri, Dániel Marx, and Paweł Rzążewski. Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 27:1-27:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.27.
  10. Thomas Emden-Weinert, Stefan Hougardy, and Bernd Kreuter. Uniquely colourable graphs and the hardness of colouring graphs of large girth. Comb. Probab. Comput., 7(4):375-386, 1998. URL: http://journals.cambridge.org/action/displayAbstract?aid=46667.
  11. Tomás Feder and Pavol Hell. List homomorphisms to reflexive graphs. Journal of Combinatorial Theory, Series B, 72(2):236-250, 1998. URL: https://doi.org/10.1006/jctb.1997.1812.
  12. Tomás Feder, Pavol Hell, and Jing Huang. List homomorphisms and circular arc graphs. Combinatorica, 19(4):487-505, 1999. URL: https://doi.org/10.1007/s004939970003.
  13. Tomás Feder, Pavol Hell, and Jing Huang. Bi-arc graphs and the complexity of list homomorphisms. Journal of Graph Theory, 42(1):61-80, 2003. URL: https://doi.org/10.1002/jgt.10073.
  14. Tomás Feder, Pavol Hell, and Jing Huang. List homomorphisms of graphs with bounded degrees. Discrete Mathematics, 307(3-5):386-392, 2007. URL: https://doi.org/10.1016/j.disc.2005.09.030.
  15. Tomás Feder, Pavol Hell, Sulamita Klein, and Rajeev Motwani. List partitions. SIAM J. Discrete Math., 16(3):449-478, 2003. URL: http://epubs.siam.org/sam-bin/dbq/article/38405.
  16. Tomás Feder, Pavol Hell, David G. Schell, and Juraj Stacho. Dichotomy for tree-structured trigraph list homomorphism problems. Discrete Applied Mathematics, 159(12):1217-1224, 2011. URL: https://doi.org/10.1016/j.dam.2011.04.005.
  17. Peter Gartland and Daniel Lokshtanov. Independent set on P_k-free graphs in quasi-polynomial time. CoRR, abs/2005.00690, 2020. To appear in FOCS 2020 Proc. URL: http://arxiv.org/abs/2005.00690.
  18. Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computational complexity of coloring graphs with forbidden subgraphs. Journal of Graph Theory, 84(4):331-363, 2017. URL: https://doi.org/10.1002/jgt.22028.
  19. 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.
  20. Carla Groenland, Karolina Okrasa, Paweł Rzążewski, Alex Scott, Paul Seymour, and Sophie Spirkl. H-colouring P_t-free graphs in subexponential time. Discrete Applied Mathematics, 267:184-189, 2019. Google Scholar
  21. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. J. Comb. Theory, Ser. B, 48(1):92-110, 1990. URL: https://doi.org/10.1016/0095-8956(90)90132-J.
  22. Chính T. Hoàng, Marcin Kaminski, Vadim V. Lozin, Joe Sawada, and Xiao Shu. Deciding k-colorability of P_5-free graphs in polynomial time. Algorithmica, 57(1):74-81, 2010. URL: https://doi.org/10.1007/s00453-008-9197-8.
  23. Ian Holyer. The NP-completeness of edge-coloring. SIAM J. Comput., 10(4):718-720, 1981. URL: https://doi.org/10.1137/0210055.
  24. 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.
  25. Marcin Kamiński and Anna Pstrucha. Certifying coloring algorithms for graphs without long induced paths. Discret. Appl. Math., 261:258-267, 2019. URL: https://doi.org/10.1016/j.dam.2018.09.031.
  26. Gábor Kun and Mario Szegedy. A new line of attack on the dichotomy conjecture. Eur. J. Comb., 52:338-367, 2016. URL: https://doi.org/10.1016/j.ejc.2015.07.011.
  27. Daniel Leven and Zvi Galil. NP-completeness of finding the chromatic index of regular graphs. J. Algorithms, 4(1):35-44, 1983. URL: https://doi.org/10.1016/0196-6774(83)90032-9.
  28. Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Full complexity classification of the list homomorphism problem for bounded-treewidth graphs. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 74:1-74:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.74.
  29. Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Full complexity classification of the list homomorphism problem for bounded-treewidth graphs. CoRR, abs/2006.11155, 2020. URL: http://arxiv.org/abs/2006.11155.
  30. Karolina Okrasa and Paweł Rzążewski. Complexity of the list homomorphism problem in hereditary graph classes. CoRR, abs/2010.03393, 2020. URL: http://arxiv.org/abs/2010.03393.
  31. 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.
  32. Marta Piecyk and Paweł Rzążewski. Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth. CoRR, abs/2009.11642, 2020. Extended abstract available in STACS 2021 Proc. URL: http://arxiv.org/abs/2009.11642.
  33. Michał Pilipczuk, Marcin Pilipczuk, and Paweł Rzążewski. Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths. In Valerie King and Hung Viet Le, editors, Proceedings of the Fourth SIAM Symposium on Simplicity in Algorithms (SOSA), Alexandria, Virginia, USA, January 11-12, 2021 (Virtual conference), pages 204-209. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976496.23.
  34. Sophie Spirkl, Maria Chudnovsky, and Mingxian Zhong. Four-coloring P₆-free graphs. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1239-1256. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.76.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact