Document Open Access Logo

Kernels for Deletion to Classes of Acyclic Digraphs

Authors Akanksha Agrawal, Saket Saurabh, Roohani Sharma, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.6.pdf
  • Filesize: 0.51 MB
  • 12 pages

Document Identifiers

Author Details

Akanksha Agrawal
Saket Saurabh
Roohani Sharma
Meirav Zehavi

Cite As Get BibTex

Akanksha Agrawal, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Kernels for Deletion to Classes of Acyclic Digraphs. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.6

Abstract

In the Directed Feedback Vertex Set (DFVS) problem, we are given a digraph D on n vertices and a positive integer k and the objective is to check whether there exists a set of vertices S of size at most k such that F = D - S is a directed acyclic digraph. In a recent paper, Mnich and van Leeuwen [STACS 2016] considered the kernelization complexity of DFVS with an additional restriction on F, namely that F must be an out-forest (Out-Forest Vertex Deletion Set), an out-tree (Out-Tree Vertex Deletion Set), or a (directed) pumpkin (Pumpkin Vertex Deletion Set). Their objective was to shed some light on the kernelization complexity of the DFVS problem, a well known open problem in the area of Parameterized Complexity. In this article, we improve the kernel sizes of Out-Forest Vertex Deletion Set from O(k^3) to O(k^2) and of Pumpkin Vertex Deletion Set from O(k^18) to O(k^3). We also prove that the former kernel size is tight under certain complexity theoretic assumptions.

Subject Classification

Keywords
  • out-forest
  • pumpkin
  • parameterized complexity
  • kernelization

Metrics

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

References

  1. F. N. Abu-Khzam. A kernelization algorithm for d-Hitting Set. JCSS, 76(7):524-531, 2010. Google Scholar
  2. V. Bafna, P. Berman, and T. Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIDMA, 12(3):289-297, 1999. Google Scholar
  3. J. Bang-Jensen, A. Maddaloni, and S. Saurabh. Algorithms and kernels for feedback set problems in generalizations of tournaments. Algorithmica, pages 1-24, 2015. Google Scholar
  4. R. Bar-Yehuda, D. Geiger, J. Naor, and R. M. Roth. Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SICOMP, 27(4):942-959, 1998. Google Scholar
  5. A. Becker and D. 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
  6. Y. Cao, J. Chen, and Y. Liu. On feedback vertex set new measure and new structures. In SWAT, pages 93-104, 2010. Google Scholar
  7. C. Chekuri and V. Madan. Constant factor approximation for subset feedback problems via a new LP relaxation. In SODA, pages 808-820, 2016. Google Scholar
  8. J. Chen, F. V. Fomin, Y. Liu, S. Lu, and Y. Villanger. Improved algorithms for feedback vertex set problems. JCSS, 74(7):1188-1198, 2008. Google Scholar
  9. J. Chen, Y. Liu, S. Lu, B. O'Sullivan, and I. Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5), 2008. Google Scholar
  10. R. H. Chitnis, M. Cygan, M. T. Hajiaghayi, and D. Marx. Directed subset feedback vertex set is fixed-parameter tractable. TALG, 11(4):28, 2015. Google Scholar
  11. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  12. M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. Rooij, and J. O. Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS, pages 150-159, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  13. M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. Subset feedback vertex set is fixed-parameter tractable. SIDMA, 27(1):290-309, 2013. URL: http://dx.doi.org/10.1137/110843071.
  14. R. Diestel. Graph Theory, 4th Edition. Springer, 2012. Google Scholar
  15. M. Dom, J. Guo, F. Hüffner, R. Niedermeier, and A. Truß. Fixed-parameter tractability results for feedback set problems in tournaments. JDA, 8(1):76-86, 2010. URL: http://dx.doi.org/10.1016/j.jda.2009.08.001.
  16. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. Google Scholar
  17. P. Erdős and L. Pósa. On independent circuits contained in a graph. Canad. J. Math, 17:347-352, 1965. Google Scholar
  18. G. Even, J. Naor, B. Schieber, and M. Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151-174, 1998. Google Scholar
  19. V. Guruswami and E. Lee. Inapproximability of H-transversal/packing. In APPROX/RANDOM, pages 284-304, 2015. Google Scholar
  20. N. Kakimura, K. Kawarabayashi, and Y. Kobayashi. Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. In SODA, pages 1726-1736, 2012. Google Scholar
  21. N. Kakimura, K. Kawarabayashi, and D. Marx. Packing cycles through prescribed vertices. J. Comb. Theory, Ser. B, 101(5):378-381, 2011. Google Scholar
  22. K. Kawarabayashi and Y. 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.
  23. K. Kawarabayashi, D. Král, M. Krcál, and S. Kreutzer. Packing directed cycles through a specified vertex set. In SODA, pages 365-377, 2013. Google Scholar
  24. T. Kociumaka and M. Pilipczuk. Faster deterministic feedback vertex set. IPL, 114(10):556-560, 2014. URL: http://dx.doi.org/10.1016/j.ipl.2014.05.001.
  25. M. Mnich and E. J. van Leeuwen. Polynomial kernels for deletion to classes of acyclic digraphs. In STACS, pages 1-13, 2016. Google Scholar
  26. M. Pontecorvi and P. Wollan. Disjoint cycles intersecting a set of vertices. J. Comb. Theory, Ser. B, 102(5):1134-1141, 2012. Google Scholar
  27. V. Raman, S. Saurabh, and C. R. Subramanian. Faster fixed parameter tractable algorithms for finding feedback vertex sets. TALG, 2(3):403-415, 2006. URL: http://dx.doi.org/10.1145/1159892.1159898.
  28. B. A. Reed, N. Robertson, P. D. Seymour, and R. Thomas. Packing directed circuits. Combinatorica, 16(4):535-554, 1996. Google Scholar
  29. P. D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281-288, 1995. Google Scholar
  30. P. D. Seymour. Packing circuits in eulerian digraphs. Combinatorica, 16(2):223-231, 1996. Google Scholar
  31. S. Thomassé. A 4k² kernel for feedback vertex set. TALG, 6(2), 2010. Google Scholar
  32. M. Wahlström. Half-integrality, LP-branching and FPT algorithms. In SODA, pages 1762-1781, 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 About DROPS Imprint Privacy Contact