FineGrained Complexity of the Graph Homomorphism Problem for BoundedTreewidth 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 edgepreserving 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 polynomialtime solvable if $H$ is bipartite or has a vertex with a loop, and NPcomplete otherwise [Hell and Nešetřil, J. Comb. Theory Ser. B, 48 (1990), pp. 92110]. 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 00975397, eISSN 10957111
 Issue year
 2021
 Vol
 50
 No
 2
 Pages
 487508
 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 (keps)^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 edgepreserving 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 polynomialtime solvable if $H$ is bipartite or has a vertex with a loop, and NPcomplete otherwise [Hell and Nešetřil, J. Comb. Theory Ser. B, 48 (1990), pp. 92110]. 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
 License
 File

 File: 1
 FineGrained Complexity of the Graph Homomorphism Problem for BoundedTreewidth Graphs, File WUT7cdcaed1f9c54bd18c9691e052cd133f.pdf / 706 KB
 WUT7cdcaed1f9c54bd18c9691e052cd133f.pdf
 publication date: 15042022
 FineGrained Complexity of the Graph Homomorphism Problem for BoundedTreewidth Graphs, File WUT7cdcaed1f9c54bd18c9691e052cd133f.pdf / 706 KB

 Score (nominal)
 200
 Score source
 journalList
 Score
 = 200.0, 25042022, ArticleFromJournal
 Publication indicators
 = 0; : 2016 = 2.128; : 2020 (2 years) = 1.414  2020 (5 years) =2.057
 Uniform Resource Identifier
 https://repo.pw.edu.pl/info/article/WUT7cdcaed1f9c54bd18c9691e052cd133f/
 URN
urn:pwrepo: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.