Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Tight Lower Bounds on Graph Embedding Problems

Uproszczony widok
dc.abstract.enWe 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.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorFomin, Fedor V.
dc.contributor.authorKulikov, Alexander S.
dc.contributor.authorSocała, Arkadiusz
dc.contributor.authorGolovnev, Alexander
dc.contributor.authorPachocki, Jakub
dc.contributor.authorMihajlin, Ivan
dc.contributor.authorCygan, Marek
dc.date.accessioned2024-01-26T10:53:19Z
dc.date.available2024-01-26T10:53:19Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.description.number3
dc.description.volume64
dc.identifier.doi10.1145/3051094
dc.identifier.issn0004-5411
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/123414
dc.identifier.weblinkhttps://dl.acm.org/doi/10.1145/3051094
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofJournal of the ACM
dc.relation.pages1-22
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleTight Lower Bounds on Graph Embedding Problems
dc.typeJournalArticle
dspace.entity.typePublication