Tight Lower Bounds on Graph Embedding Problems

Marek Cygan, Fedor V. Fomin, Alexander Golovnev +4

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 al…