Tight lower bounds on graph embedding problems

DOI10.1145/3051094zbMATH Open1426.68099arXiv1602.05016OpenAlexW2286480406MaRDI QIDQ4640290FDOQ4640290

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)

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.

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

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

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)

Cited In (20)

• Title not available (Why is that?)
• 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
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• On strongly almost trivial embeddings of graphs
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth
• Lower bounds for the graph homomorphism problem
• A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Title not available (Why is that?)
• FPT Algorithms for Embedding into Low-Complexity Graphic Metrics
• Subgraph isomorphism on graph classes that exclude a substructure
• The hardness of embedding grids and walls
• 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
• Graph Drawing

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)