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

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

Uproszczony widok
dc.abstract.enFor the vast majority of local problems on graphs of small treewidth (where, by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give ctw |V|O(1) time algorithms, where tw is the treewidth of the input graph G = (V,E) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best–known algorithms were naive dynamic programming schemes running in at least twtw time. We bridge this gap by introducing a technique we named Cut&Count that allows to produce ctw |V|O(1) time Monte-Carlo algorithms for most connectivity-type problems, including Hamiltonian Path , Steiner Tree , Feedback Vertex Set and Connected Dominating Set . These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H-minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In all these fields we are able to improve the best-known results for some problems. Also, looking from a more theoretical perspective, our results are surprising since the equivalence relation that partitions all partial solutions with respect to extendability to global solutions seems to consist of at least twtw equivalence classes for all these problems. Our results answer an open problem raised by Lokshtanov, Marx and Saurabh [SODA’11]. In contrast to the problems aimed at minimizing the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be bridged for some problems that aim to maximize the number of connected components like Cycle Packing .
dc.affiliationUniwersytet Warszawski
dc.contributor.authorCygan, Marek
dc.contributor.authorPilipczuk, Marcin
dc.contributor.authorWojtaszczyk, Jakub Onufry
dc.contributor.authorRooij, Johan M. M. Van
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorNederlof, Jesper
dc.date.accessioned2024-01-26T07:52:57Z
dc.date.available2024-01-26T07:52:57Z
dc.date.issued2022
dc.description.financePublikacja bezkosztowa
dc.description.number2
dc.description.volume18
dc.identifier.doi10.1145/3506707
dc.identifier.issn1549-6325
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/120195
dc.identifier.weblinkhttps://dl.acm.org/doi/pdf/10.1145/3506707
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofACM Transactions on Algorithms
dc.relation.pages1-31
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleSolving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
dc.typeJournalArticle
dspace.entity.typePublication