Document Open Access Logo

Towards a Polynomial Kernel for Directed Feedback Vertex Set

Authors Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.36.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Benjamin Bergougnoux
Eduard Eiben
Robert Ganian
Sebastian Ordyniak
M. S. Ramanujan

Cite AsGet BibTex

Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. Towards a Polynomial Kernel for Directed Feedback Vertex Set. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.36

Abstract

In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008]; since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying undirected graph. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus.
Keywords
  • parameterized algorithms
  • kernelization
  • (directed) feedback vertex set

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math., 12(3):289-297, 1999. Google Scholar
  2. Reuven Bar-Yehuda, Dan Geiger, Joseph Naor, and Ron M. Roth. Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference. SIAM J. Comput., 27(4):942-959, 1998. Google Scholar
  3. Ann Becker and Dan Geiger. Optimization of pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell., 83(1):167-188, 1996. Google Scholar
  4. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (meta) kernelization. J. ACM, 63(5):44:1-44:69, 2016. Google Scholar
  5. Hans L. Bodlaender and Thomas C. van Dijk. A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst., 46(3):566-597, 2010. Google Scholar
  6. Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set new measure and new structures. In Haim Kaplan, editor, Algorithm Theory - SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings, volume 6139 of Lecture Notes in Computer Science, pages 93-104. Springer, 2010. Google Scholar
  7. Chandra Chekuri and Vivek Madan. Constant factor approximation for subset feedback set problems via a new LP relaxation. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 808-820. SIAM, 2016. Google Scholar
  8. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci., 74(7):1188-1198, 2008. URL: http://dx.doi.org/10.1016/j.jcss.2008.05.002.
  9. Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5), 2008. URL: http://dx.doi.org/10.1145/1411509.1411511.
  10. Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx. Directed subset feedback vertex set is fixed-parameter tractable. ACM Transactions on Algorithms, 11(4):28, 2015. Google Scholar
  11. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  12. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. On the hardness of losing width. Theory Comput. Syst., 54(1):73-82, 2014. Google Scholar
  13. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS, pages 150-159, 2011. Google Scholar
  14. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discrete Math., 27(1):290-309, 2013. URL: http://dx.doi.org/10.1137/110843071.
  15. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer Verlag, New York, 2nd edition, 2000. Google Scholar
  16. Rodney G. Downey and Michael R. Fellows. Fixed-parameter intractability. In Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22-25, 1992, pages 36-49, 1992. Google Scholar
  17. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput., 24(4):873-921, 1995. Google Scholar
  18. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  19. P Erdős and L Pósa. On independent circuits contained in a graph. Canad. J. Math, 17:347-352, 1965. Google Scholar
  20. Guy Even, Joseph Naor, Baruch Schieber, and Madhu Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151-174, 1998. Google Scholar
  21. Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci., 84:219-242, 2017. Google Scholar
  22. Jonathan L. Gross and Thomas W. Tucker. Topological Graph Theory. Wiley-Interscience, New York, NY, USA, 1987. Google Scholar
  23. Venkatesan Guruswami and Euiwoong Lee. Inapproximability of h-transversal/packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, volume 40 of LIPIcs, pages 284-304. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  24. Bart M. P. Jansen and Hans L. Bodlaender. Vertex cover kernelization revisited - upper and lower bounds for a refined parameter. Theory Comput. Syst., 53(2):263-299, 2013. Google Scholar
  25. Naonori Kakimura, Ken-ichi Kawarabayashi, and Yusuke Kobayashi. Erdös-pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1726-1736. SIAM, 2012. Google Scholar
  26. Naonori Kakimura, Ken-ichi Kawarabayashi, and Dániel Marx. Packing cycles through prescribed vertices. J. Comb. Theory, Ser. B, 101(5):378-381, 2011. Google Scholar
  27. Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York., pages 85-103, 1972. URL: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf.
  28. Ken-ichi Kawarabayashi and Yusuke Kobayashi. Fixed-parameter tractability for the subset feedback set problem and the s-cycle packing problem. J. Comb. Theory, Ser. B, 102(4):1020-1034, 2012. URL: http://dx.doi.org/10.1016/j.jctb.2011.12.001.
  29. Ken-ichi Kawarabayashi, Daniel Král', Marek Krcál, and Stephan Kreutzer. Packing directed cycles through a specified vertex set. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 365-377, 2013. Google Scholar
  30. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Inf. Process. Lett., 114(10):556-560, 2014. URL: http://dx.doi.org/10.1016/j.ipl.2014.05.001.
  31. M. Pontecorvi and Paul Wollan. Disjoint cycles intersecting a set of vertices. J. Comb. Theory, Ser. B, 102(5):1134-1141, 2012. Google Scholar
  32. Venkatesh Raman, Saket Saurabh, and C. R. Subramanian. Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Transactions on Algorithms, 2(3):403-415, 2006. URL: http://dx.doi.org/10.1145/1159892.1159898.
  33. Bruce A. Reed, Neil Robertson, Paul D. Seymour, and Robin Thomas. Packing directed circuits. Combinatorica, 16(4):535-554, 1996. Google Scholar
  34. Paul D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281-288, 1995. Google Scholar
  35. Paul D. Seymour. Packing circuits in eulerian digraphs. Combinatorica, 16(2):223-231, 1996. Google Scholar
  36. Stéphan Thomassé. A 4k^2 kernel for feedback vertex set. ACM Trans. Algorithms, 6(2):32:1-32:8, 2010. Google Scholar
  37. Magnus Wahlström. Half-integrality, LP-branching and FPT algorithms. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1762-1781. SIAM, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact