Tight Bounds for Graph Homomorphism and Subgraph Isomorphism

DOI10.1137/1.9781611974331.CH112MaRDI QIDQ4575696zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Ivan Mihajlin, Jakub W. Pachocki, Arkadiusz Socała, Alexander S. Kulikov

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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)

Abstract: We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph $G$ to graph $H$ cannot be done in time $|V(H){|}^{o(|V(G)|)}$. Combined with the reduction of Cygan, Pachocki, and Soca{l}a, our result rules out (subject to ETH) a possibility of $|V(G){|}^{o(|V(G)|)}$-time algorithm deciding if graph $H$ is a subgraph of $G$. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems.

Recommendations

• Lower bounds for subgraph isomorphism
• Lower bounds for the graph homomorphism problem
• A Bound for Non-subgraph Isomorphism
• Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism
• A convex relaxation bound for subgraph isomorphism
• Efficient Suboptimal Graph Isomorphism
• Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
• The complexity of restricted graph homomorphisms

Cited in

(15)

• scientific article; zbMATH DE number 7559154 (Why is no real title available?)
• Star colouring of bounded degree graphs and regular graphs
• Tight lower bounds for the complexity of multicoloring
• Proper colorability of segment intersection graphs
• Fast exact algorithms for survivable network design with uniform requirements
• Tight lower bounds on graph embedding problems
• Basic Terminology, Notation and Results
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• Lower bounds for the graph homomorphism problem
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• Tree-Depth and the Formula Complexity of Subgraph Isomorphism
• Improved lower bounds for graph embedding problems
• On the fine-grained complexity of rainbow coloring
• Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
• Fine-grained complexity of rainbow coloring and its variants

This page was built for publication: Tight Bounds for Graph Homomorphism and Subgraph Isomorphism

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