DOI

  • Marek Cygan
  • Fedor V. Fomin
  • Alexander Golovnev
  • Alexander S. Kulikov
  • Ivan Mihajlin
  • Jakub Pachocki
  • Arkadiusz Socała

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.

Язык оригиналаанглийский
Номер статьи18
ЖурналJournal of the ACM
Том64
Номер выпуска3
DOI
СостояниеОпубликовано - июн 2017

    Предметные области Scopus

  • Программный продукт
  • Системотехника
  • Информационные системы
  • Аппаратное обеспечение и архитектура ЭВМ
  • Искусственный интеллект

ID: 49820784