Research output: Contribution to journal › Article › peer-review
Tight lower bounds on graph embedding problems. / Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz.
In: Journal of the ACM, Vol. 64, No. 3, 18, 06.2017.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Tight lower bounds on graph embedding problems
AU - Cygan, Marek
AU - Fomin, Fedor V.
AU - Golovnev, Alexander
AU - Kulikov, Alexander S.
AU - Mihajlin, Ivan
AU - Pachocki, Jakub
AU - Socała, Arkadiusz
PY - 2017/6
Y1 - 2017/6
N2 - 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.
AB - 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.
KW - Exponential time hypothesis
KW - Graph embedding
KW - Graph homomorphism
KW - Lower bounds
KW - Subgraph isomorphism
UR - http://www.scopus.com/inward/record.url?scp=85021152171&partnerID=8YFLogxK
U2 - 10.1145/3051094
DO - 10.1145/3051094
M3 - Article
AN - SCOPUS:85021152171
VL - 64
JO - Journal of the ACM
JF - Journal of the ACM
SN - 0004-5411
IS - 3
M1 - 18
ER -
ID: 49820784