Standard

Tight lower bounds on graph embedding problems. / Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz.

в: Journal of the ACM, Том 64, № 3, 18, 06.2017.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Cygan, M, Fomin, FV, Golovnev, A, Kulikov, AS, Mihajlin, I, Pachocki, J & Socała, A 2017, 'Tight lower bounds on graph embedding problems', Journal of the ACM, Том. 64, № 3, 18. https://doi.org/10.1145/3051094

APA

Cygan, M., Fomin, F. V., Golovnev, A., Kulikov, A. S., Mihajlin, I., Pachocki, J., & Socała, A. (2017). Tight lower bounds on graph embedding problems. Journal of the ACM, 64(3), [18]. https://doi.org/10.1145/3051094

Vancouver

Cygan M, Fomin FV, Golovnev A, Kulikov AS, Mihajlin I, Pachocki J и пр. Tight lower bounds on graph embedding problems. Journal of the ACM. 2017 Июнь;64(3). 18. https://doi.org/10.1145/3051094

Author

Cygan, Marek ; Fomin, Fedor V. ; Golovnev, Alexander ; Kulikov, Alexander S. ; Mihajlin, Ivan ; Pachocki, Jakub ; Socała, Arkadiusz. / Tight lower bounds on graph embedding problems. в: Journal of the ACM. 2017 ; Том 64, № 3.

BibTeX

@article{16eb1102bcbd4fae9cf6a106a4ae61d8,
title = "Tight lower bounds on graph embedding problems",
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.",
keywords = "Exponential time hypothesis, Graph embedding, Graph homomorphism, Lower bounds, Subgraph isomorphism",
author = "Marek Cygan and Fomin, {Fedor V.} and Alexander Golovnev and Kulikov, {Alexander S.} and Ivan Mihajlin and Jakub Pachocki and Arkadiusz Soca{\l}a",
year = "2017",
month = jun,
doi = "10.1145/3051094",
language = "English",
volume = "64",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery",
number = "3",

}

RIS

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