The Library
Linear time parameterized algorithms for subset feedback vertex set
Tools
Tools
Tools
Lokshtanov, Daniel, Ramanujan, Maadapuzhi Sridharan and Saurabh, Saket (2018) Linear time parameterized algorithms for subset feedback vertex set. ACM Transactions on Algorithms, 14 (1). 7. doi:10.1145/3155299 ISSN 1549-6333.
|
PDF
WRAP-linear-time-parameterized-algorithms-Lokshtanov-2018.pdf - Accepted Version - Requires a PDF viewer. Download (912Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/3155299
Abstract
In the Subset Feedback Vertex Set (Subset FVS) problem, the input is a graph G on n vertices and m edges, a subset of vertices T, referred to as terminals, and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every cycle that contains a terminal. The study of parameterized algorithms for this generalization of the Feedback Vertex Set problem has received significant attention over the past few years. In fact, the parameterized complexity of this problem was open until 2011, when two groups independently showed that the problem is fixed parameter tractable. Using tools from graph minors,, Kawarabayashi and Kobayashi obtained an algorithm for Subset FVS running in time O(f(k)ċ n2 m) [SODA 2012, JCTB 2012]. Independently, Cygan et al. [ICALP 2011, SIDMA 2013] designed an algorithm for Subset FVS running in time 2O(k log k)ċ nO(1). More recently, Wahlström obtained the first single exponential time algorithm for Subset FVS, running in time 4kċ nO(1) [SODA 2014]. While the 2O(k) dependence on the parameter k is optimal under the Exponential Time Hypothesis, the dependence of this algorithm as well as those preceding it, on the input size is at least quadratic. In this article, we design the first linear time parameterized algorithms for Subset FVS. More precisely, we obtain the following new algorithms for Subset FVS.
— A randomized algorithm for Subset FVS running in time O(25.6kċ (n + m)).
— A deterministic algorithm for Subset FVS running in time 2O(k log k) ċ (n + m).
Since it is known that assuming the Exponential Time Hypothesis, Subset FVS cannot have an algorithm running in time 2o(k)nO(1), our first algorithm obtains the best possible asymptotic dependence on both the parameter as well as the input size. Both of our algorithms are based on “cut centrality,” in the sense that solution vertices are likely to show up in minimum size cuts between vertices sampled from carefully chosen distributions.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Algorithms, Set theory | ||||||
| Journal or Publication Title: | ACM Transactions on Algorithms | ||||||
| Publisher: | Association for Computing Machinery, Inc. | ||||||
| ISSN: | 1549-6333 | ||||||
| Official Date: | January 2018 | ||||||
| Dates: |
|
||||||
| Volume: | 14 | ||||||
| Number: | 1 | ||||||
| Number of Pages: | 36 | ||||||
| Article Number: | 7 | ||||||
| DOI: | 10.1145/3155299 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 17 May 2018 | ||||||
| Date of first compliant Open Access: | 17 May 2018 | ||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
