Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

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

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:35:48Z
dc.abstract.en<p>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)|<sup>tw(</sup>G<sup>)</sup> · n<sup>O</sup><sup>(1)</sup>, 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)| − ε)<sup>tw(</sup>G<sup>)</sup> · n<sup>O</sup><sup>(1)</sup>, 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.</p>
dc.abstract.plW 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryStany Zjednoczone
dc.conference.datefinish2020-01-08
dc.conference.datestart2020-01-05
dc.conference.placeSalt Lake City
dc.conference.seriesACM/SIAM Symposium on Discrete Algorithms
dc.conference.seriesACM/SIAM Symposium on Discrete Algorithms
dc.conference.seriesshortcutSODA
dc.conference.shortcutSODA 2020
dc.conference.weblinkhttps://www.siam.org/conferences/cm/conference/soda20
dc.contributor.authorRzążewski, Paweł
dc.contributor.authorOkrasa, Karolina
dc.date.accessioned2024-01-25T00:40:55Z
dc.date.available2024-01-25T00:40:55Z
dc.date.issued2020
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.1137/1.9781611975994.97
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/107163
dc.identifier.weblinkhttps://epubs.siam.org/doi/pdf/10.1137/1.9781611975994.97
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages1578-1590
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enfine-grained complexity
dc.subject.engraph homomorphism
dc.subject.pldrobnoziarnista złożoność
dc.subject.plhomomorfizm grafów
dc.titleFine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
dc.typeJournalArticle
dspace.entity.typePublication