## Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs

### Authors:

- Karolina Okrasa,
- Paweł Rzążewski

### Abstract

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$, i.e., an edge-preserving mapping from $V(G)$ to $V(H)$. As Hom($K_k$) is equivalent to $k$-Coloring, 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, J. Comb. Theory Ser. B, 48 (1990), pp. 92--110]. 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)} \cdot n^{\mathcal{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, the Hom($H$) problem cannot be solved in time $(|V(H)|-\epsilon)^{{tw}(G)} \cdot n^{\mathcal{O}(1)}$, for any $\epsilon > 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.

- Record ID
- WUT7cdcaed1f9c54bd18c9691e052cd133f
- Author
- Journal series
- SIAM Journal on Computing, ISSN 0097-5397, e-ISSN 1095-7111
- Issue year
- 2021
- Vol
- 50
- No
- 2
- Pages
- 487-508
- Keywords in Polish
- homomorfizm grafów, szerokość drzewowa, SETH
- Keywords in English
- graph homomorphism, treewidth, SETH
- ASJC Classification
- ;
- Abstract in Polish
- W pracy badamy, jak złożoność problemu znajdowania homomorfizmu w ustalony graf H zależy od szerokości drzewowej grafu wejściowego G. Dla każdego grafu H badamy stałą k, taką że: (a) problem da się rozwiązać w czasie k^tw(G) * poly(|V(G)|) (b) problemu nie da się rozwiązać w czasie (k-eps)^tw(G) * poly(|V(G)|), dla żadnego eps > 0. Pokazujemy, jak znaleźć takie stałe, przy założeniu dwóch hipotez z algebraicznej teorii grafów.
- Abstract in original language
- 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$, i.e., an edge-preserving mapping from $V(G)$ to $V(H)$. As Hom($K_k$) is equivalent to $k$-Coloring, 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, J. Comb. Theory Ser. B, 48 (1990), pp. 92--110]. 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)} \cdot n^{\mathcal{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, the Hom($H$) problem cannot be solved in time $(|V(H)|-\epsilon)^{{tw}(G)} \cdot n^{\mathcal{O}(1)}$, for any $\epsilon > 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.
- DOI
- DOI:10.1137/20m1320146 Opening in a new tab
- URL
- https://epubs.siam.org/doi/pdf/10.1137/20M1320146 Opening in a new tab
- Language
- eng (en) English
- Score (nominal)
- 200
- Score source
- journalList
- Score
- = 200.0, 01-06-2021, ArticleFromJournal
- Publication indicators
- : 2016 = 2.128; : 2019 = 1.266 (2) - 2019=1.703 (5)

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

- URN
`urn:pw-repo:WUT7cdcaed1f9c54bd18c9691e052cd133f`

* 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.