An Improved FPT Algorithm for Independent Feedback Vertex Set

Theory of Computing Systems - 2020
Shaohua Li1, Marcin Pilipczuk1
1Institute of Informatics, University of Warsaw, Warsaw, Poland

Tóm tắt

AbstractWe study the Independent Feedback Vertex Set problem — a variant of the classic Feedback Vertex Set problem where, given a graph G and an integer k, the problem is to decide whether there exists a vertex set $S\subseteq V(G)$ S ⊆ V ( G ) such that G ∖ S is a forest and S is an independent set of size at most k. We present an $\mathcal {O}^{\ast }((1+\varphi ^{2})^{k})$ O ∗ ( ( 1 + φ 2 ) k ) -time FPT algorithm for this problem, where φ < 1.619 is the golden ratio, improving the previous fastest $\mathcal {O}^{\ast }(4.1481^{k})$ O ∗ ( 4.148 1 k ) -time algorithm given by Agrawal et al. (2016). The exponential factor in our time complexity bound matches the fastest deterministic FPT algorithm for the classic Feedback Vertex Set problem. On the technical side, the main novelty is a refined measure of an input instance in a branching process, that allows for a simpler and more concise description and analysis of the algorithm.

Từ khóa


Tài liệu tham khảo

Encyclopedia of optimization, Second Edition Springer (2009)

Agrawal, A., Gupta, S., Saurabh, S., Sharma, R.: Improved algorithms and combinatorial bounds for independent feedback vertex set. In: Guo, J., Hermelin, D. (eds.) 11th international symposium on parameterized and exact computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, LIPIcs, vol. 63, pp. 2:1–2:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2016.2 (2016)

Agrawal, A., Lokshtanov, D., Mouawad, A. E., Saurabh, S.: Simultaneous Feedback Vertex Set: A parameterized perspective. TOCT 10(4), 18:1–18:25 (2018). https://doi.org/10.1145/3265027

Bodlaender, H. L.: On disjoint cycles. Int. J. Found. Comput. Sci. 5(1), 59–68 (1994). https://doi.org/10.1142/S0129054194000049

Cao, Y., Chen, J., Liu, Y.: On feedback vertex set: New measure and new structures. Algorithmica 73(1), 63–86 (2015). https://doi.org/10.1007/s00453-014-9904-6

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). https://doi.org/10.1016/j.jcss.2008.05.002

Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms. Springer, Berlin. https://doi.org/10.1007/978-3-319-21275-3 (2015)

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. In: IEEE 52nd annual symposium on foundations of computer science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pp. 150–159. IEEE Computer Society. https://doi.org/10.1109/FOCS.2011.23 (2011)

Cygan, M., Pilipczuk, M., Pilipczuk, M.: On group Feedback Vertex Set parameterized by the size of the cutset. Algorithmica 74(2), 630–642 (2016). https://doi.org/10.1007/s00453-014-9966-5

Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J. O.: Subset Feedback Vertex Set is fixed-parameter tractable. SIAM J. Discrete Math. 27(1), 290–309 (2013). https://doi.org/10.1137/110843071

Downey, R. G., Fellows, M. R.: Fixed parameter tractability and completeness. In: Complexity theory: Current research, Dagstuhl Workshop, February 2-8, 1992, pp. 191–225. Cambridge University Press (1992)

Downey, R. G., Fellows, M. R.: Parameterized complexity. Monographs in computer science. Springer. https://doi.org/10.1007/978-1-4612-0515-9 (1999)

Guillemot, S.: FPT algorithms for path-transversal and cycle-transversal problems. Discret. Optim. 8(1), 61–71 (2011). https://doi.org/10.1016/j.disopt.2010.05.003

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). https://doi.org/10.1016/j.jcss.2006.02.001

Iwata, Y.: Linear-time kernelization for Feedback Vertex Set. In: 44th international colloquium on automata, languages, and programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, LIPIcs, vol. 80, pp. 68:1–68:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2017.68(2017)

Iwata, Y., Wahlström, M., Yoshida, Y.: Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput. 45(4), 1377–1411 (2016). https://doi.org/10.1137/140962838

Kanj, I. A., Pelsmajer, M. J., Schaefer, M.: Parameterized algorithms for Feedback Vertex Set. In: Parameterized and exact computation, 1st international workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings, Lecture Notes in Computer Science, vol. 3162, pp. 235–247. Springer. https://doi.org/10.1007/978-3-540-28639-4_21 (2004)

Kociumaka, T., Pilipczuk, M.: Faster deterministic Feedback Vertex Set. Inf. Process. Lett. 114(10), 556–560 (2014). https://doi.org/10.1016/j.ipl.2014.05.001

Kratsch, S., Wahlstrȯm, M.: Representative sets and irrelevant vertices: New tools for kernelization. In: 53rd Annual IEEE symposium on foundations of computer science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pp. 450–459. IEEE Computer Society. https://doi.org/10.1109/FOCS.2012.46 (2012)

Li, S., Pilipczuk, M.: An improved FPT algorithm for Independent Feedback Vertex Set. In: Brandstȧdt, A., Kȯhler, E., Meer, K. (eds.) Graph-theoretic concepts in computer science - 44th international workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, Lecture Notes in Computer Science, vol. 11159, pp. 344–355. Springer. https://doi.org/10.1007/978-3-030-00256-5_28 (2018)

Lokshtanov, D., Ramanujan, M. S., Saurabh, S.: Linear time parameterized algorithms for Subset Feedback Vertex Set. ACM Trans. Algorithms 14(1), 7:1–7:37 (2018). https://doi.org/10.1145/3155299

Misra, N., Philip, G., Raman, V., Saurabh, S.: On parameterized Independent Feedback Vertex Set. Theor. Comput. Sci. 461, 65–75 (2012). https://doi.org/10.1016/j.tcs.2012.02.012

Misra, N., Philip, G., Raman, V., Saurabh, S., Sikdar, S.: FPT algorithms for Connected Feedback Vertex Set. J. Comb. Optim. 24(2), 131–146 (2012). https://doi.org/10.1007/s10878-011-9394-2

Thomassė, S.: A 4k2, kernel for Feedback Vertex Set. ACM Trans. Algorithms 6(2), 32:1–32:8 (2010). https://doi.org/10.1145/1721837.1721848

Thông tin
Thông tin xuất bản

Theory of Computing Systems

Thông tin tác giả