Abstract
The graph homomorphism problem (HOM) asks whether the vertices of a given n-vertex graph G can be mapped to the vertices of a given h-vertex graph H such that each edge of G is mapped to an edge of H. The problem generalizes the graph coloring problem and at the same time can be viewed as a special case of the 2-CSP problem. In this paper, we prove several lower bounds for HOM under the Exponential Time Hypothesis (ETH) assumption. The main result is a lower bound \(2^{\Omega \left( \frac{n \log h}{\log \log h}\right) }\). This rules out the existence of a single-exponential algorithm and shows that the trivial upper bound \(2^{\mathcal {O}(n\log {h})}\) is almost asymptotically tight.
We also investigate what properties of graphs G and H make it difficult to solve HOM(G, H). An easy observation is that an \(\mathcal {O}(h^n)\) upper bound can be improved to \(\mathcal {O}(h^{{\text {vc}}(G)})\) where \({\text {vc}}(G)\) is the minimum size of a vertex cover of G. The second lower bound \(h^{\Omega ({\text {vc}}(G))}\) shows that the upper bound is asymptotically tight. As to the properties of the “right-hand side” graph H, it is known that HOM(G, H) can be solved in time \((f(\Delta (H)))^n\) and \((f({\text {tw}}(H)))^n\) where \(\Delta (H)\) is the maximum degree of H and \({\text {tw}}(H)\) is the treewidth of H. This gives single-exponential algorithms for graphs of bounded maximum degree or bounded treewidth. Since the chromatic number \(\chi (H)\) does not exceed \({\text {tw}}(H)\) and \(\Delta (H)+1\), it is natural to ask whether similar upper bounds with respect to \(\chi (H)\) can be obtained. We provide a negative answer by establishing a lower bound \((f(\chi (H)))^n\) for every function f. We also observe that similar lower bounds can be obtained for locally injective homomorphisms.
The full version of the paper is available at http://arxiv.org/abs/1502.05447
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Austrin, P.: Towards sharp inapproximability for any 2-CSP. SIAM J. Comput. 39(6), 2430–2463 (2010)
Barto, L., Kozik, M., Niven, T.: Graphs, polymorphisms and the complexity of homomorphism problems. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 789–796 (2008)
Björklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Computing 39(2), 546–563 (2009)
Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Computer and System Sciences 72(8), 1346–1367 (2006)
Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science 411(40–42), 3736–3756 (2010)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)
Diaz, J., Serna, M., Thilikos, D.M.: Counting \(H\)-colorings of partial \(k\)-trees. Theoretical Computer Science 281, 291–309 (2002)
Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput. 28(1), 57–104 (1998)
Fiala, J., Golovach, P.A., Kratochvíl, J.: Computational complexity of the distance constrained labeling problem for trees (extended abstract). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 294–305. Springer, Heidelberg (2008)
Fiala, J., Kratochvíl, J.: Locally constrained graph homomorphisms - structure, complexity, and applications. Computer Science Review 2(2), 97–111 (2008)
Fomin, F.V., Heggernes, P., Kratsch, D.: Exact algorithms for graph homomorphisms. Theory of Computing Systems 41(2), 381–393 (2007)
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer (2010)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)
Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5(4), 586–595 (1992)
Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1) (2007)
Havet, F., Klazar, M., Kratochvíl, J., Kratsch, D., Liedloff, M.: Exact algorithms for L(2, 1)-labeling of graphs. Algorithmica 59(2), 169–194 (2011)
Hell, P., Nešetřil, J.: On the complexity of \(H\)-coloring. J. Combinatorial Theory Ser. B 48(1), 92–110 (1990)
Hell, P., Nešetřil, J.: Graphs and homomorphisms. Oxford Lecture Series in Mathematics and its Applications, vol. 28. Oxford University Press, Oxford (2004)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Computer and System Sciences 63(4), 512–530 (2001)
Junosza-Szaniawski, K., Kratochvíl, J., Liedloff, M., Rossmanith, P., Rzazewski, P.: Fast exact algorithm for l(2, 1)-labeling of graphs. Theor. Comput. Sci. 505, 42–54 (2013)
Lawler, E.L.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5(3), 66–67 (1976)
Lokshtanov, D.: Private communication (2014)
Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 760–776. SIAM (2011)
Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bulletin of EATCS 3(105) (2013)
Lovász, L.: Large networks and graph limits, vol. 60. American Mathematical Soc. (2012)
Marx, D.: Can you beat treewidth? Theory of Computing 6(1), 85–112 (2010)
Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 245–254 (2008)
Rzażewski, P.: Exact algorithm for graph homomorphism and locally injective graph homomorphism. Inf. Process. Lett. 114(7), 387–391 (2014)
Sipser, M.: Introduction to the Theory of Computation. Cengage Learning (2005)
Traxler, P.: The time complexity of constraint satisfaction. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 190–201. Springer, Heidelberg (2008)
Wahlström, M.: Problem 5.21. time complexity of graph homomorphism. In: Thore Husfeldt, Dieter Kratsch, R.P., Sorkin, G. (eds.) Exact Complexity of NP-Hard Problems. Dagstuhl Seminar 10441 Final Report. Dagstuhl (2010)
Wahlström, M.: New plain-exponential time classes for graph homomorphism. Theory of Computing Systems 49(2), 273–282 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fomin, F.V., Golovnev, A., Kulikov, A.S., Mihajlin, I. (2015). Lower Bounds for the Graph Homomorphism Problem. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_39
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_39
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)