×

zbMATH — the first resource for mathematics

Subset feedback vertex set is fixed-parameter tractable. (English) Zbl 1334.68096
Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 449-461 (2011).
Summary: The classical Feedback Vertex Set problem asks, for a given undirected graph \(G\) and an integer \(k\), to find a set of at most \(k\) vertices that hits all the cycles in the graph \(G\). Feedback Vertex Set has attracted a large amount of research in the parameterized setting, and subsequent kernelization and fixed-parameter algorithms have been a rich source of ideas in the field.
In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex Set (Subset-FVS in short) where an instance comes additionally with a set \(S \subseteq V\) of vertices, and we ask for a set of at most \(k\) vertices that hits all simple cycles passing through \(S\). Because of its applications in circuit testing and genetic linkage analysis Subset-FVS was studied from the approximation algorithms perspective by G. Even et al. [SIAM J. Discrete Math. 13, No. 2, 255–267 (2000; Zbl 0941.68057); SIAM J. Comput. 30, No. 4, 1231–1252 (2000; Zbl 0973.05073)].
The question whether the Subset-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parametrized by \(|S|\). Next we present an algorithm which reduces the given instance to \(2^{k } n ^{O(1)}\) instances with the size of \(S\) bounded by \(O(k ^{3})\), using kernelization techniques such as the 2-Expansion Lemma, Menger’s theorem and Gallai’s theorem. These two facts allow us to give a \(2^{O(k \log k)} n ^{O(1)}\) time algorithm solving the Subset Feedback Vertex Set problem, proving that it is indeed fixed-parameter tractable.
For the entire collection see [Zbl 1217.68003].

MSC:
68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX Cite
Full Text: DOI
References:
[1] Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res (JAIR) 12, 219–234 (2000) · Zbl 0947.68138
[2] Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci. 5(1), 59–68 (1994) · Zbl 0803.05030
[3] Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst. 46(3), 566–597 (2010) · Zbl 1215.68170
[4] Bousquet, N., Daligault, J., Thomassé, S.: Multicut is FPT. In: Proc. of STOC 2011 (to appear, 2011) · Zbl 1288.05264
[5] Burrage, K., Estivill-Castro, V., Fellows, M.R., Langston, M.A., Mac, S., Rosamond, F.A.: The undirected feedback vertex set problem has a poly(k) kernel. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 192–202. Springer, Heidelberg (2006) · Zbl 1154.68421
[6] Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 93–104. Springer, Heidelberg (2010) · Zbl 1285.68061
[7] Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188–1198 (2008) · Zbl 1152.68055
[8] Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. In: Proc. of STOC 2008, pp. 177–186 (2008) · Zbl 1231.68149
[9] Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. CoRR abs/1103.0534 (2011) · Zbl 1292.68122
[10] Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O(2 \(^{\mbox{{o}(k)}}\) n \(^{\mbox{3}}\) ) FPT algorithm for the undirected feedback vertex set problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 859–869. Springer, Heidelberg (2005) · Zbl 1128.68400
[11] Demaine, E.D., Hajiaghayi, M.T., Marx, D.: Open problems from dagstuhl seminar 09511 (2009)
[12] Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Complexity Theory: Current Research, pp. 191–225 (1992) · Zbl 0799.68087
[13] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
[14] Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20(2), 151–174 (1998) · Zbl 0897.68078
[15] Even, G., Naor, J., Schieber, B., Zosin, L.: Approximating minimum subset feedback sets in undirected graphs with applications. SIAM J. Discrete Math. 13(2), 255–267 (2000) · Zbl 0941.68057
[16] Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput. 30(4), 1231–1252 (2000) · Zbl 0973.05073
[17] Guillemot, S.: FPT algorithms for path-transversals and cycle-transversals problems in graphs. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 129–140. Springer, Heidelberg (2008) · Zbl 1142.68599
[18] Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386–1396 (2006) · Zbl 1119.68134
[19] Kanj, I.A., Pelsmajer, M.J., Schaefer, M.: Parameterized algorithms for feedback vertex set. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 235–247. Springer, Heidelberg (2004) · Zbl 1104.68541
[20] Kawarabayashi, K., Kobayashi, Y.: Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem (2010) (manuscript) · Zbl 1245.05103
[21] Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394–406 (2006) · Zbl 1086.68104
[22] Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proc. of STOC 2011 (to appear, 2011) · Zbl 1288.05283
[23] Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for undirected feedback vertex set. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 241–248. Springer, Heidelberg (2002) · Zbl 1019.68082
[24] Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Transactions on Algorithms 2(3), 403–415 (2006) · Zbl 1321.05275
[25] Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299–301 (2004) · Zbl 1052.05061
[26] Thomassé, S.: A quadratic kernel for feedback vertex set. In: Proc. of SODA 2009, pp. 115–119 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.