Tight Bounds for Graph Homomorphism and Subgraph Isomorphism

DOI10.1137/1.9781611974331.CH112zbMATH Open1409.68209arXiv1507.03738OpenAlexW4254708154MaRDI QIDQ4575696FDOQ4575696

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)

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.

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

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

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)

Cited In (15)

• Title not available (Why is that?)
• 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)