Document Open Access Logo

Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization

Authors László Egri, Dániel Marx, Pawel Rzazewski

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.27.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

László Egri
Dániel Marx
Pawel Rzazewski

Cite As Get BibTex

László Egri, Dániel Marx, and Pawel Rzazewski. Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.27

Abstract

In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v) \subseteq V(H) for every vertex v \in V(G). The task is to find a homomorphism phi:V(G) -> V(H) respecting the lists, that is, we have that phi(v) \in L(v) for every v \in V(H) and if u and v are adjacent in G, then phi(u) and phi(v) are adjacent in H. If H is a fixed graph, then the problem is denoted LHom(H). We consider the reflexive version of the problem, where we assume that every vertex
in H has a self-loop. If is known that reflexive LHom(H) is polynomial-time solvable if H is an interval graph and it is NP-complete otherwise [Feder and Hell, JCTB 1998].

We explore the complexity of the problem parameterized by the treewidth tw(G) of the input graph G. If a tree decomposition of G of width tw(G) is given in the input, then the problem can be solved in time |V(H)|^{tw(G)} n^{O(1)} by naive dynamic programming. Our main result completely reveals when and by exactly how much this naive algorithm can be improved. We introduce a simple combinatorial invariant i^*(H), which is based on the existence of decompositions and incomparable sets, and show that this number should appear as the base of the exponent in the best possible running time. Specifically, we prove for every fixed non-interval graph H that
* If a tree decomposition of width tw(G) is given in the input, then the problem can be solved in time i^*(H)^{tw(G)} n^{O(1)}.
* Assuming the Strong Exponential-Time Hypothesis (SETH), the probem cannot be solved in time (i^*(H)-epsilon)^{tw(G)} n^{O(1)} for any epsilon>0.
Thus by matching upper and lower bounds, our result exactly characterizes for every fixed H the complexity of reflexive LHom(H) parameterized by treewidth.

Subject Classification

Keywords
  • graph homomorphism
  • list homomorphism
  • reflexive graph
  • treewidth

Metrics

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

References

  1. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets möbius: fast subset convolution. In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 67-74. ACM, 2007. URL: http://dx.doi.org/10.1145/1250790.1250801.
  2. Hans L. Bodlaender, Paul S. Bonsma, and Daniel Lokshtanov. The fine details of fast dynamic programming over tree decompositions. 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 41-53. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03898-8_5.
  3. 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.
  4. Andrei A. Bulatov. H-coloring dichotomy revisited. Theor. Comput. Sci., 349(1):31-39, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.028.
  5. Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. Hitting forbidden subgraphs in graphs of bounded treewidth. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, volume 8635 of Lecture Notes in Computer Science, pages 189-200. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_17.
  6. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 150-159. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  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: http://dx.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: http://dx.doi.org/10.1137/1.9781611973402.26.
  9. Tomás Feder and Pavol Hell. List homomorphisms to reflexive graphs. J. Comb. Theory, Ser. B, 72(2):236-250, 1998. URL: http://dx.doi.org/10.1006/jctb.1997.1812.
  10. Tomás Feder, Pavol Hell, and Jing Huang. List homomorphisms and circular arc graphs. Combinatorica, 19(4):487-505, 1999. URL: http://dx.doi.org/10.1007/s004939970003.
  11. 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: http://dx.doi.org/10.1002/jgt.10073.
  12. Tomás Feder, Pavol Hell, and Jing Huang. List homomorphisms of graphs with bounded degrees. Discrete Mathematics, 307(3-5):386-392, 2007. URL: http://dx.doi.org/10.1016/j.disc.2005.09.030.
  13. Tomás Feder, Pavol Hell, Jing Huang, and Arash Rafiey. Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms. Discrete Applied Mathematics, 160(6):697-707, 2012. URL: http://dx.doi.org/10.1016/j.dam.2011.04.016.
  14. 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.
  15. 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: http://dx.doi.org/10.1016/j.dam.2011.04.005.
  16. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. 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 142-151. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.10.
  17. Pavol Hell and Jaroslav Nesetril. On the complexity of H-coloring. J. Comb. Theory, Ser. B, 48(1):92-110, 1990. URL: http://dx.doi.org/10.1016/0095-8956(90)90132-J.
  18. Gábor Kun and Mario Szegedy. A new line of attack on the dichotomy conjecture. Eur. J. Comb., 52:338-367, 2016. URL: http://dx.doi.org/10.1016/j.ejc.2015.07.011.
  19. C. Lekkeikerker and J. Boland. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae, 51(1):45-64, 1962. URL: http://eudml.org/doc/213681.
  20. 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.
  21. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. 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 760-776. SIAM, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.60.
  22. Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In Filip Murlak and Piotr Sankowski, editors, Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings, volume 6907 of Lecture Notes in Computer Science, pages 520-531. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22993-0_47.
  23. Mark H. Siggers. A New Proof of the H-Coloring Dichotomy. SIAM Journal on Discrete Mathematics, 23(4):2204-2210, 2010. URL: http://dx.doi.org/10.1137/080736697.
  24. Zsolt Tuza. Graph colorings with local constraints - a survey. Discussiones Mathematicae Graph Theory, 17(2):161-228, 1997. URL: http://dx.doi.org/10.7151/dmgt.1049.
  25. 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: http://dx.doi.org/10.1007/978-3-642-04128-0_51.
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