## Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs

### Authors:

- Karolina Okrasa,
- Paweł Rzążewski

### Abstract

For graphs G and H, a homomorphism from G to H is an edge-preserving mapping from the vertex set of G to the vertex set of H. For a fixed graph H, by Hom(H) we denote the computational problem which asks whether a given graph G admits a homomorphism to H. If H is a complete graph with k vertices, then Hom(H) is equivalent to the k-Coloring problem, so graph homomorphisms can be seen as generalizations of colorings. It is known that Hom(H) is polynomial-time solvable if H is bipartite or has a vertex with a loop, and NP-complete otherwise [Hell and Nešetřil, JCTB 1990]. In this paper we are interested in the complexity of the problem, parameterized by the treewidth of the input graph G. If G has n vertices and is given along with its tree decomposition of width tw(G), then the problem can be solved in time |V (H)|^{tw(}G^{)} · n^{O}^{(1)}, using a straightforward dynamic programming. We explore whether this bound can be improved. We show that if H is a projective core, then the existence of such a faster algorithm is unlikely: assuming the Strong Exponential Time Hypothesis (SETH), the Hom(H) problem cannot be solved in time (|V (H)| − ε)^{tw(}G^{)} · n^{O}^{(1)}, for any ε > 0. This result provides a full complexity characterization for a large class of graphs H, as almost all graphs are projective cores. We also notice that the naive algorithm can be improved for some graphs H, and show a complexity classification for all graphs H, assuming two conjectures from algebraic graph theory. In particular, there are no known graphs H which are not covered by our result. In order to prove our results, we bring together some tools and techniques from algebra and from fine-grained complexity.

- Record ID
- WUT9eca4d94a2164cb185ca96b3bb48845a
- Author
- Pages
- 1578-1590
- Publication size in sheets
- 0.60
- Book
- Chawla Shuchi Shuchi Chawla (eds.): Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020, Society for Industrial and Applied Mathematics, ISBN 978-1-61197-599-4. DOI:10.1137/1.9781611975994 Opening in a new tab
- Keywords in Polish
- drobnoziarnista złożoność, homomorfizm grafów
- Keywords in English
- fine-grained complexity, graph homomorphism
- Abstract in Polish
- W pracy analizujemy złożoność problemu znajdowania homomorfizmu w ustalony graf H, parametryzowaną przez szerokość drzewową grafu G. Pokazujemy nieoczekiwany związek tego problemu z pewnymi zagadnieniami z algebraicznej teorii grafów.
- DOI
- DOI:10.1137/1.9781611975994.97 Opening in a new tab
- URL
- https://epubs.siam.org/doi/pdf/10.1137/1.9781611975994.97 Opening in a new tab
- Language
- eng (en) English
- Score (nominal)
- 200
- Score source
- conferenceList
- Score
- = 200.0, 05-05-2022, ChapterFromConference
- Publication indicators
- = 3

- Uniform Resource Identifier
- https://repo.pw.edu.pl/info/article/WUT9eca4d94a2164cb185ca96b3bb48845a/

- URN
`urn:pw-repo:WUT9eca4d94a2164cb185ca96b3bb48845a`

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.