Tight Bounds for Graph Homomorphism and Subgraph Isomorphism

DOI10.1137/1.9781611974331.ch112zbMath1409.68209arXiv1507.03738OpenAlexW4254708154MaRDI QIDQ4575696

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

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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 (9)

Star colouring of bounded degree graphs and regular graphs ⋮ Tree-Depth and the Formula Complexity of Subgraph Isomorphism ⋮ On the Fine-Grained Complexity of Rainbow Coloring ⋮ Tight Lower Bounds for the Complexity of Multicoloring ⋮ Unnamed Item ⋮ Fast exact algorithms for survivable network design with uniform requirements ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ Fine-Grained Complexity of Rainbow Coloring and its Variants. ⋮ Basic Terminology, Notation and Results

This page was built for publication: Tight Bounds for Graph Homomorphism and Subgraph Isomorphism