Tight Lower Bounds on Graph Embedding Problems

DOI10.1145/3051094zbMath1426.68099arXiv1602.05016OpenAlexW2286480406MaRDI QIDQ4640290

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

Publication date: 17 May 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.05016

zbMATH Keywords

graph homomorphismlower boundsgraph embeddingsubgraph isomorphismexponential time hypothesis

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Pattern matching in doubling spaces ⋮ Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Tight Lower Bounds for List Edge Coloring ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs