Daniel Lokshtanov
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.
- Hans L. Bodlaender. 1996. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 6 (1996), 1305--1317. Google Scholar
Digital Library
- Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. 2013. An -approximation algorithm for treewidth. In FOCS. 499--508. Google ScholarDigital Library
- Yixin Cao, Jianer Chen, and Yang Liu. 2015. On feedback vertex set: New measure and new structures. Algorithmica 73, 1 (2015), 63--86. Google ScholarDigital Library
- Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. 2008. Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74, 7 (2008), 1188--1198. Google ScholarDigital Library
- Jianer Chen, Yang Liu, and Songjian Lu. 2009. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica 55, 1 (2009), 1--13. Google ScholarDigital Library
- Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon. 2008. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55, 5 (2008). Google ScholarDigital Library
- Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx. 2015. Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans. Algor. 11, 4 (2015), 28:1--28:28. Google ScholarDigital Library
- Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. to appear in 2014. Parameterized Algorithms. Springer-Verlag, Berlin.Google Scholar
- Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. 2011. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS. 150--159. Google ScholarDigital Library
- Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. 2013. Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discrete Math. 27, 1 (2013), 290--309.Google ScholarDigital Library
- Reinhard Diestel. 2010. Graph Theory (4th ed.). Springer-Verlag, Heidelberg.Google Scholar
- Frederic Dorn. 2010. Planar subgraph isomorphism revisited. In STACS. 263--274.Google Scholar
- Guy Even, Joseph Naor, Baruch Schieber, and Leonid Zosin. 2000b. Approximating minimum subset feedback sets in undirected graphs with applications. SIAM J. Discrete Math. 13, 2 (2000), 255--267. Google ScholarDigital Library
- Guy Even, Joseph Naor, and Leonid Zosin. 2000a. An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput. 30, 4 (2000), 1231--1252. Google ScholarDigital Library
- L. R. Ford, Jr. and D. R. Fulkerson. 1956. Maximal flow through a network. Canad. J. Math. 8 (1956), 399--404.Google ScholarCross Ref
- Martin Grohe, Ken-ichi Kawarabayashi, and Bruce A. Reed. 2013. A simple algorithm for the graph minor decomposition - Logic meets structural graph theory. In SODA. 414--431. Google ScholarDigital Library
- Carsten Gutwenger and Petra Mutzel. 2000. A linear time implementation of SPQR-trees. In GD. 77--90. Google ScholarDigital Library
- John E. Hopcroft and Robert Endre Tarjan. 1973a. Dividing a graph into triconnected components. SIAM J. Comput. 2, 3 (1973), 135--158.Google ScholarDigital Library
- John E. Hopcroft and Robert Endre Tarjan. 1973b. Efficient algorithms for graph manipulation {H} (algorithm 447). Commun. ACM 16, 6 (1973), 372--378. Google ScholarDigital Library
- Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity?J. Comput. Syst. Sci. 63, 4 (2001), 512--530. Google ScholarDigital Library
- Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. 2014. Linear-time FPT algorithms via network flow. In SODA. 1749--1761. Google ScholarDigital Library
- Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida. 2016. Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput. 45, 4 (2016), 1377--1411.Google ScholarCross Ref
- Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. 2014. A near-optimal planarization algorithm. In SODA. 1802--1811. Google ScholarDigital Library
- Naonori Kakimura, Ken-ichi Kawarabayashi, and Yusuke Kobayashi. 2012. Erdös-Pósa property and its algorithmic applications: Parity constraints, subset feedback set, and subset packing. In SODA. 1726--1736. Google ScholarDigital Library
- Naonori Kakimura, Ken-ichi Kawarabayashi, and Dániel Marx. 2011. Packing cycles through prescribed vertices. J. Comb. Theor. Ser. B 101, 5 (2011), 378--381. Google ScholarDigital Library
- Ken-ichi Kawarabayashi. 2009. Planarity allowing few error vertices in linear time. In FOCS. 639--648. Google ScholarDigital Library
- Ken-ichi Kawarabayashi and Yusuke Kobayashi. 2012. Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem. J. Comb. Theor. Ser. B 102, 4 (2012), 1020--1034. Google ScholarDigital Library
- Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce A. Reed. 2012. The disjoint paths problem in quadratic time. J. Comb. Theor. Ser. B 102, 2 (2012), 424--435. Google ScholarDigital Library
- Ken-ichi Kawarabayashi and Bojan Mohar. 2008. Graph and map isomorphism and all polyhedral embeddings in linear time. In STOC. 471--480. Google ScholarDigital Library
- Ken-ichi Kawarabayashi, Bojan Mohar, and Bruce A. Reed. 2008. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In FOCS. 771--780. Google ScholarDigital Library
- Ken-ichi Kawarabayashi and Bruce A. Reed. 2009. A nearly linear time algorithm for the half integral parity disjoint paths packing problem. In SODA. 1183--1192. Google ScholarDigital Library
- Ken-ichi Kawarabayashi and Bruce A. Reed. 2010. An (almost) linear time algorithm for odd cycles transversal. In SODA. 365--378. Google ScholarDigital Library
- Tomasz Kociumaka and Marcin Pilipczuk. 2014. Faster deterministic feedback vertex set. Inf. Process. Lett. 114, 10 (2014), 556--560. Google ScholarDigital Library
- Daniel Lokshtanov and M. S. Ramanujan. 2012. Parameterized tractability of multiway cut with parity constraints. In ICALP(1). 750--761. Google ScholarDigital Library
- Dániel Marx. 2006. Parameterized graph separation problems. Theoret. Comput. Sci. 351, 3 (2006), 394--406. Google ScholarDigital Library
- Dániel Marx and Igor Razgon. 2014. Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM J. Comput. 43, 2 (2014), 355--388.Google ScholarCross Ref
- Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. Google ScholarDigital Library
- Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford.Google Scholar
- M. Pontecorvi and Paul Wollan. 2012. Disjoint cycles intersecting a set of vertices. J. Comb. Theor. Ser. B 102, 5 (2012), 1134--1141. Google ScholarDigital Library
- Venkatesh Raman, Saket Saurabh, and C. R. Subramanian. 2006. Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Trans. Algor. 2, 3 (2006), 403--415. Google ScholarDigital Library
- M. S. Ramanujan and Saket Saurabh. 2017. Linear-time parameterized algorithms via skew-symmetric multicuts. ACM Trans. Algor. 13, 4, Article 46 (Sept. 2017), 25 pages. Google ScholarDigital Library
- Igor Razgon and Barry O’Sullivan. 2009. Almost 2-SAT is fixed-parameter tractable.J. Comput. Syst. Sci. 75, 8 (2009), 435--450. Google ScholarDigital Library
- Neil Robertson and Paul D. Seymour. 1995. Graph minors .XIII. The disjoint paths problem. J. Comb. Theor. Ser. B 63, 1 (1995), 65--110. Google ScholarDigital Library
- Magnus Wahlström. 2014. Half-integrality, LP-branching and FPT algorithms. In SODA. 1762--1781. Google ScholarDigital Library
Index Terms
- Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
Recommendations
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
Given a graph G and an integer k, the Feedback Vertex Set (FVS) problem asks if there is a vertex set T of size at most k that hits all cycles in the graph. The first fixed-parameter algorithm for FVS in undirected graphs appeared in a monograph of ...
Simultaneous Feedback Vertex Set: A Parameterized Perspective
For a family F of graphs, a graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex ...
Structural Parameterizations of Undirected Feedback Vertex Set: FPT Algorithms and Kernelization
A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure in the ...
Comments