Tight lower bounds on graph embedding problems

DOI10.1145/3051094MaRDI QIDQ4640290zbMATH OpenOpenAlexFDO

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

Publication date 17 May 2018

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsgraph homomorphismexponential time hypothesisgraph embeddingsubgraph isomorphism

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)

Abstract: We prove that unless the 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)|)}$. We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of $|V(H){|}^{o(|V(H)|)}$-time algorithm deciding if graph $G$ is a subgraph of $H$. 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. Moreover, as a consequence of our reductions conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem.

Recommendations

• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Lower bounds for the graph homomorphism problem
• Improved lower bounds for graph embedding problems
• Subexponential time algorithms for embedding \(H\)-minor free graphs
• Subexponential algorithms for variants of the homomorphism problem in string graphs

Cited in

(20)

• Graph Drawing
• scientific article; zbMATH DE number 1670673 (Why is no real title available?)
• Pattern matching in doubling spaces
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• Embedding the diamond graph in L_p and dimension reduction in L₁
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• On strongly almost trivial embeddings of graphs
• Lower bounds for the graph homomorphism problem
• Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth
• A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• scientific article; zbMATH DE number 7651213 (Why is no real title available?)
• FPT Algorithms for Embedding into Low-Complexity Graphic Metrics
• The hardness of embedding grids and walls
• Subgraph isomorphism on graph classes that exclude a substructure
• Improved lower bounds for graph embedding problems
• A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Tight lower bounds for list edge coloring

This page was built for publication: Tight lower bounds on graph embedding problems

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