Tight Bounds for Subgraph Isomorphism and Graph Homomorphism

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ł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.

10 pages

References in corpus (1)

• The Hardness of Subgraph Isomorphism