Document Open Access Logo

Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs

Authors Karolina Okrasa , Marta Piecyk, Paweł Rzążewski

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.74.pdf
  • Filesize: 0.6 MB
  • 24 pages

Document Identifiers

Author Details

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

Funding

  • Okrasa, Karolina: This research is a part of a project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement no. 714704.
  • Piecyk, Marta: Supported by Polish National Science Centre grant no. 2018/31/D/ST6/00062.
  • Rzążewski, Paweł: Supported by Polish National Science Centre grant no. 2018/31/D/ST6/00062.

Acknowledgements

We are grateful to Daniél Marx and Lászlo Egri for much advice regarding the topic and to Kamil Szpojankowski for an inspiring discussion about almost all graphs.

Cite AsGet BibTex

Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 74:1-74:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.74

Abstract

A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). Let H be a fixed graph with possible loops. In the list homomorphism problem, denoted by LHom(H), we are given a graph G, whose every vertex v is assigned with a list L(v) of vertices of H. We ask whether there exists a homomorphism h from G to H, which respects lists L, i.e., for every v ∈ V(G) it holds that h(v) ∈ L(v). The complexity dichotomy for LHom(H) was proven by Feder, Hell, and Huang [JGT 2003]. The authors showed that the problem is polynomial-time solvable if H belongs to the class called bi-arc graphs, and for all other graphs H it is NP-complete. We are interested in the complexity of the LHom(H) problem, parameterized by the treewidth of the input graph. This problem was investigated by Egri, Marx, and Rzążewski [STACS 2018], who obtained tight complexity bounds for the special case of reflexive graphs H, i.e., if every vertex has a loop. In this paper we extend and generalize their results for all relevant graphs H, i.e., those, for which the LHom(H) problem is NP-hard. For every such H we find a constant k = k(H), such that the LHom(H) problem on instances G with n vertices and treewidth t - can be solved in time k^t ⋅ n^𝒪(1), provided that G is given along with a tree decomposition of width t, - cannot be solved in time (k-ε)^t ⋅ n^𝒪(1), for any ε > 0, unless the SETH fails. For some graphs H the value of k(H) is much smaller than the trivial upper bound, i.e., |V(H)|. Obtaining matching upper and lower bounds shows that the set of algorithmic tools that we have discovered cannot be extended in order to obtain faster algorithms for LHom(H) in bounded-treewidth graphs. Furthermore, neither the algorithm, nor the proof of the lower bound, is very specific to treewidth. We believe that they can be used for other variants of the LHom(H) problem, e.g. with different parameterizations.

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
  • list homomorphisms
  • fine-grained complexity
  • SETH
  • treewidth

Metrics

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

Related Versions

References

  1. Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods, 8(2):277–284, April 1987. URL: https://doi.org/10.1137/0608024.
  2. Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics, 23(1):11-24, 1989. URL: https://doi.org/10.1016/0166-218X(89)90031-0.
  3. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM J. Comput., 39(2):546-563, 2009. URL: https://doi.org/10.1137/070683933.
  4. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. URL: https://doi.org/10.1137/S0097539793251219.
  5. Hans L. Bodlaender, Paul S. Bonsma, and Daniel Lokshtanov. The fine details of fast dynamic programming over tree decompositions. In Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, pages 41-53, 2013. URL: https://doi.org/10.1007/978-3-319-03898-8_5.
  6. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86-111, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.008.
  7. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM J. Comput., 45(2):317-378, 2016. URL: https://doi.org/10.1137/130947374.
  8. Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. Comput. J., 51(3):255-269, May 2008. URL: https://doi.org/10.1093/comjnl/bxm037.
  9. Andrei A. Bulatov. Constraint satisfaction problems: Complexity and algorithms. In Shmuel Tomi Klein, Carlos Martín-Vide, and Dana Shapira, editors, Language and Automata Theory and Applications, pages 1-25, Cham, 2018. Springer International Publishing. Google Scholar
  10. Rajesh Chitnis, László Egri, and Dániel Marx. List H-coloring a graph by removing few vertices. Algorithmica, 78(1):110-146, 2017. URL: https://doi.org/10.1007/s00453-016-0139-6.
  11. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  12. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socala. Tight lower bounds on graph embedding problems. J. ACM, 64(3):18:1-18:22, 2017. URL: https://doi.org/10.1145/3051094.
  13. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  14. László Egri, Andrei A. Krokhin, Benoît Larose, and Pascal Tesson. The complexity of the list homomorphism problem for graphs. Theory Comput. Syst., 51(2):143-178, 2012. URL: https://doi.org/10.1007/s00224-011-9333-8.
  15. 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.
  16. Tomas 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.
  17. 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.
  18. 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.
  19. Jirí Fiala and Jana Maxová. Cantor-Bernstein type theorem for locally constrained graph homomorphisms. Eur. J. Comb., 27(7):1111-1116, 2006. URL: https://doi.org/10.1016/j.ejc.2006.06.003.
  20. Jirí Fiala and Daniël Paulusma. A complete complexity classification of the role assignment problem. Theor. Comput. Sci., 349(1):67-81, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.029.
  21. Jirí Fiala, Daniël Paulusma, and Jan Arne Telle. Matrix and graph orders derived from locally constrained graph homomorphisms. In Joanna Jedrzejowicz and Andrzej Szepietowski, editors, Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005, Proceedings, volume 3618 of Lecture Notes in Computer Science, pages 340-351. Springer, 2005. URL: https://doi.org/10.1007/11549345_30.
  22. Fedor V. Fomin, Pinar Heggernes, and Dieter Kratsch. Exact algorithms for graph homomorphisms. Theory Comput. Syst., 41(2):381-393, 2007. URL: https://doi.org/10.1007/s00224-007-2007-x.
  23. Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic, 130(1-3):3-31, 2004. URL: https://doi.org/10.1016/j.apal.2004.01.007.
  24. Richard Hammack, Wilfried Imrich, and Sandi Klavžar. Handbook of product graphs. Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, second edition, 2011. With a foreword by Peter Winkler. Google Scholar
  25. Pavol Hell and Jaroslav Nešetřil. Graphs and homomorphisms. Oxford University Press, 2004. Google Scholar
  26. 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.
  27. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  28. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  29. Bart M. P. Jansen. personal communication. Google Scholar
  30. Bart M. P. Jansen and Jesper Nederlof. Computing the chromatic number using graph decompositions via matrix rank. Theor. Comput. Sci., 795:520-539, 2019. URL: https://doi.org/10.1016/j.tcs.2019.08.006.
  31. Tomasz Kociumaka and Marcin Pilipczuk. Deleting vertices to graphs of bounded genus. Algorithmica, 81(9):3655-3691, 2019. URL: https://doi.org/10.1007/s00453-019-00592-7.
  32. Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, and Peter Rossmanith. Optimality and tight results in parameterized complexity (dagstuhl seminar 14451). Dagstuhl Reports, 4(11):1-21, 2014. URL: https://doi.org/10.4230/DagRep.4.11.1.
  33. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms, 14(2):13:1-13:30, 2018. URL: https://doi.org/10.1145/3170442.
  34. 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.
  35. Karolina Okrasa and Paweł Rzążewski. Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pages 1578-1590, 2020. URL: https://doi.org/10.1137/1.9781611975994.97.
  36. 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.
  37. Michał Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In MFCS 2011, volume 6907, pages 520-531. Springer, 2011. Google Scholar
  38. Paweł Rzążewski. Exact algorithm for graph homomorphism and locally injective graph homomorphism. Inf. Process. Lett., 114(7):387-391, 2014. URL: https://doi.org/10.1016/j.ipl.2014.02.012.
  39. William T. Trotter and John I. Moore. Characterization problems for graphs, partially ordered sets, lattices, and families of sets. Discrete Mathematics, 16(4):361-381, 1976. URL: https://doi.org/10.1016/S0012-365X(76)80011-8.
  40. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 566-577. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_51.
  41. Magnus Wahlström. New plain-exponential time classes for graph homomorphism. Theory Comput. Syst., 49(2):273-282, 2011. URL: https://doi.org/10.1007/s00224-010-9261-z.
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 Imprint Privacy Contact