Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3051094 | Journal of the ACM (JACM) |
Keywords | DocType | Volume |
Lower bounds,graph homomorphism,subgraph isomorphism,graph embedding,exponential time hypothesis | Journal | 64 |
Issue | ISSN | Citations |
3 | 0004-5411 | 1 |
PageRank | References | Authors |
0.37 | 36 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marek Cygan | 1 | 556 | 40.52 |
| Fedor V. Fomin | 2 | 3139 | 192.21 |
| Alexander Golovnev | 3 | 52 | 12.44 |
| Alexander S. Kulikov | 4 | 280 | 25.63 |
| Ivan Mihajlin | 5 | 23 | 6.47 |
| Jakub W. Pachocki | 6 | 25 | 2.63 |
| Arkadiusz Socala | 7 | 11 | 4.37 |