×

Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization. (English) Zbl 1487.68125

Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 27, 15 p. (2018).
Summary: 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)\rightarrow 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 by LHom(H). We consider the reflexive version of the problem, where we assume that every vertex in \(H\) has a self-loop. It is known that reflexive LHom(H) is polynomial-time solvable if \(H\) is an interval graph and it is NP-complete otherwise [T. Feder and P. Hell, J. Comb. Theory, Ser. B 72, No. 2, 236–250 (1998; Zbl 0904.05078)].
We explore the complexity of the problem parameterized by the treewidth \(\mathrm{tw}(G)\) of the input graph \(G\). If a tree decomposition of \(G\) of width \(\mathrm{tw}(G)\) is given in the input, then the problem can be solved in time \(|V(H)|^{\mathrm{tw}(G)}\cdot 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 certain 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 non-interval reflexive graph \(H\) that
If a tree decomposition of width \(\mathrm{tw}(G)\) is given in the input, then the problem can be solved in time \(i^*(H)^{\mathrm{tw}(G)}\cdot n^{O(1)}\).
Assuming the Strong Exponential-Time Hypothesis (SETH), the problem cannot be solved in time \((i^*(H)-\epsilon)^{\mathrm{tw}(G)}\cdot 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.
For the entire collection see [Zbl 1381.68010].

MSC:

68Q25 Analysis of algorithms and problem complexity
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 0904.05078
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] 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, {\it Proceedings} {\it of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA,} {\it June 11-13, 2007}, pages 67-74. ACM, 2007. doi:10.1145/1250790.1250801. · Zbl 1232.68188
[3] 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, {\it Parameterized and Exact Computation - 8th International Symposium, IPEC} {\it 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers}, volume 8246 of {\it Lecture Notes in Computer Science}, pages 41-53. Springer, 2013. doi:10.1007/ 978-3-319-03898-8_5. · Zbl 1406.68067
[4] Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. {\it Comput. J.}, 51(3):255-269, 2008. doi:10.1093/comjnl/bxm037.
[5] Andrei A. Bulatov. H-coloring dichotomy revisited. {\it Theor. Comput. Sci.}, 349(1):31-39, 2005. doi:10.1016/j.tcs.2005.09.028. · Zbl 1086.68052
[6] 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, {\it Mathematical Foundations of Computer Science 2014 - 39th In-} {\it ternational Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings,} {\it Part II}, volume 8635 of {\it Lecture Notes in Computer Science}, pages 189-200. Springer, 2014. doi:10.1007/978-3-662-44465-8_17. · Zbl 1426.68118
[7] 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, {\it IEEE 52nd Annual Symposium on} {\it Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25,} {\it 2011}, pages 150-159. IEEE Computer Society, 2011. doi:10.1109/FOCS.2011.23. · Zbl 1292.68122
[8] 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 {\it 30th Annual} {\it ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July} {\it 6-10, 2015}, pages 487-498. IEEE Computer Society, 2015. doi:10.1109/LICS.2015.52. · Zbl 1401.68104
[9] László Egri, Pavol Hell, Benoit Larose, and Arash Rafiey. Space complexity of list {\it H }colouring: a dichotomy.In Chandra Chekuri, editor, {\it Proceedings of the Twenty-Fifth}
[10] Tomás Feder and Pavol Hell. List homomorphisms to reflexive graphs. {\it J. Comb. Theory,} {\it Ser. B}, 72(2):236-250, 1998. doi:10.1006/jctb.1997.1812. · Zbl 0904.05078
[11] Tomás Feder, Pavol Hell, and Jing Huang. List homomorphisms and circular arc graphs. {\it Combinatorica}, 19(4):487-505, 1999. doi:10.1007/s004939970003. · Zbl 0985.05048
[12] Tomás Feder, Pavol Hell, and Jing Huang. Bi-arc graphs and the complexity of list homomorphisms. {\it Journal of Graph Theory}, 42(1):61-80, 2003. doi:10.1002/jgt.10073. · Zbl 1057.05033
[13] Tomás Feder, Pavol Hell, and Jing Huang. List homomorphisms of graphs with bounded degrees. {\it Discrete Mathematics}, 307(3-5):386-392, 2007. doi:10.1016/j.disc.2005.09. 030. · Zbl 1111.05035
[14] Tomás Feder, Pavol Hell, Jing Huang, and Arash Rafiey. Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms. {\it Discrete Applied Mathematics}, 160(6):697-707, 2012. doi:10.1016/j.dam.2011.04.016. · Zbl 1236.05092
[15] Tomás Feder, Pavol Hell, Sulamita Klein, and Rajeev Motwani. List partitions. {\it SIAM} {\it J. Discrete Math.}, 16(3):449-478, 2003.URL: http://epubs.siam.org/sam-bin/dbq/ article/38405. · Zbl 1029.05143
[16] Tomás Feder, Pavol Hell, David G. Schell, and Juraj Stacho. Dichotomy for tree-structured trigraph list homomorphism problems. {\it Discrete Applied Mathematics}, 159(12):1217-1224, 2011. doi:10.1016/j.dam.2011.04.005. · Zbl 1223.05095
[17] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In Chandra Chekuri, editor, {\it Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Al-} {\it gorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014}, pages 142-151. SIAM, 2014. doi:10.1137/1.9781611973402.10. · Zbl 1421.68077
[18] Pavol Hell and Jaroslav Nesetril. On the complexity of {\it H }-coloring. {\it J. Comb. Theory, Ser.} {\it B}, 48(1):92-110, 1990. doi:10.1016/0095-8956(90)90132-J. · Zbl 0639.05023
[19] Gábor Kun and Mario Szegedy. A new line of attack on the dichotomy conjecture. {\it Eur. J.} {\it Comb.}, 52:338-367, 2016. doi:10.1016/j.ejc.2015.07.011. · Zbl 1327.05183
[20] C. Lekkeikerker and J. Boland. Representation of a finite graph by a set of intervals on the real line. {\it Fundamenta Mathematicae}, 51(1):45-64, 1962. URL: http://eudml.org/doc/ 213681. · Zbl 0105.17501
[21] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs on bounded treewidth are probably optimal.In Dana Randall, editor, {\it Proceedings of the} {\it Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San} {\it Francisco, California, USA, January 23-25, 2011}, pages 777-789. SIAM, 2011. doi:10. 1137/1.9781611973082.61. · Zbl 1373.68242
[22] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. In Dana Randall, editor, {\it Proceedings of the Twenty-Second Annual ACM-} {\it SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA,} {\it January 23-25, 2011}, pages 760-776. SIAM, 2011. doi:10.1137/1.9781611973082.60. · Zbl 1373.68273
[23] Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In Filip Murlak and Piotr Sankowski, editors, {\it Mathematical Found-} {\it ations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw,} {\it Poland, August 22-26, 2011. Proceedings}, volume 6907 of {\it Lecture Notes in Computer Sci-} {\it ence}, pages 520-531. Springer, 2011. doi:10.1007/978-3-642-22993-0_47. · Zbl 1343.68120
[24] Mark H. Siggers. A New Proof of the H-Coloring Dichotomy. {\it SIAM Journal on Discrete} {\it Mathematics}, 23(4):2204-2210, 2010. doi:10.1137/080736697. · Zbl 1207.05065
[25] Zsolt Tuza. Graph colorings with local constraints - a survey. {\it Discussiones Mathematicae} {\it Graph Theory}, 17(2):161-228, 1997. doi:10.7151/dmgt.1049. · Zbl 0923.05027
[26] 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, {\it Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen,} {\it Denmark, September 7-9, 2009. Proceedings}, volume 5757 of {\it Lecture Notes in Computer} {\it Science}, pages 566-577. Springer, 2009. doi:10.1007/978-3-642-04128-0_51. · Zbl 1256.68157
[27] :15
[28] :14
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.