Lower Bounds for the Graph Homomorphism Problem

DOI10.1007/978-3-662-47672-7_39zbMATH Open1440.68102DBLPconf/icalp/FominGKM15arXiv1502.05447OpenAlexW2169633784WikidataQ60488393 ScholiaQ60488393MaRDI QIDQ3448809FDOQ3448809

Alexander S. Kulikov, Alexander Golovnev, Ivan Mihajlin, Fedor V. Fomin

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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 bound for HOM under the Exponential Time Hypothesis (ETH) assumption. The main result is a lower bound $2^{Omegaleft(fracnloghlogloghight)}$. This rules out the existence of a single-exponential algorithm and shows that the trivial upper bound $2^{mathcalO(nlogh)}$ 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 $mathcalO(h^n)$ upper bound can be improved to $mathcalO(h^{operatornamevc(G)})$ where $operatornamevc(G)$ is the minimum size of a vertex cover of $G$. The second lower bound $h^{Omega(operatornamevc(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(operatornametw(H)){)}^n$ where $Delta(H)$ is the maximum degree of $H$ and $operatornametw(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 $operatornametw(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 to this question by establishing a lower bound $(f(chi(H)){)}^n$ for any function $f$. We also observe that similar lower bounds can be obtained for locally injective homomorphisms.

Full work available at URL: https://arxiv.org/abs/1502.05447

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Exact exponential algorithms.
• On the complexity of H-coloring
• Which problems have strongly exponential complexity?
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Parameterized Algorithms
• Labelling Graphs with a Condition at Distance 2
• Improved upper bounds for vertex cover
• Exact algorithms for graph homomorphisms
• The Time Complexity of Constraint Satisfaction
• Set Partitioning via Inclusion-Exclusion
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• Strong computational lower bounds via parameterized complexity
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• A note on the complexity of the chromatic number problem
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Towards Sharp Inapproximability for Any 2-CSP
• Counting \(H-\)colorings of partial \(k-\)trees
• New plain-exponential time classes for graph homomorphism
• Exact algorithm for graph homomorphism and locally injective graph homomorphism

Cited In (4)

• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Lower bounds on the differential of a graph
• Testing the Complexity of a Valued CSP Language
• Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs

This page was built for publication: Lower Bounds for the Graph Homomorphism Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448809)