Document Open Access Logo

Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS

Authors Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Roohani Sharma, Meirav Zehavi

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2018.110.pdf
  • Filesize: 390 kB
  • 4 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Polynomial Kernel
  • Directed Feedback Vertex Set
  • Treewidth Modulator

Metrics

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

Abstract

In the Directed Feedback Vertex Set (DFVS) problem, we are given as input a directed graph D and an integer k, and the objective is to check whether there exists a set S of at most k vertices such that F=D-S is a directed acyclic graph (DAG). Determining whether DFVS admits a polynomial kernel (parameterized by the solution size) is one of the most important open problems in parameterized complexity. In this article, we give a polynomial kernel for DFVS parameterized by the solution size plus the size of any treewidth-eta modulator, for any positive integer eta. We also give a polynomial kernel for the problem, which we call Vertex Deletion to treewidth-eta DAG, where given as input a directed graph D and a positive integer k, the objective is to decide whether there exists a set of at most k vertices, say S, such that D-S is a DAG and the treewidth of D-S is at most eta.

Cite As Get BibTex

Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 110:1-110:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.110

Author Details

Daniel Lokshtanov
  • Department of Informatics, University of Bergen, Norway
M. S. Ramanujan
  • Algorithms and Complexity Group, TU Wien, Austria
Saket Saurabh
  • Institute of Mathematical Sciences, HBNI, India and UMI ReLax
Roohani Sharma
  • Institute of Mathematical Sciences, HBNI, India and UMI ReLax
Meirav Zehavi
  • Department of Computer Science, Ben-Gurion University, Israel

References

  1. F N Abu-Khzam. A kernelization algorithm for d-Hitting Set. JCSS, 76(7):524-531, 2010. Google Scholar
  2. Akanksha Agrawal, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Kernels for deletion to classes of acyclic digraphs. J. Comput. Syst. Sci., 92:9-21, 2018. URL: http://dx.doi.org/10.1016/j.jcss.2017.07.008.
  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. Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. Towards a polynomial kernel for directed feedback vertex set. In MFCS 2017, 2017. To Appear. Google Scholar
  5. 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.
  6. 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. URL: http://dx.doi.org/10.1007/s00224-013-9480-1.
  7. 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.
  8. 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
  9. 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
  10. Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi. Subquadratic kernels for implicit 3-hitting set and 3-set packing problems. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 331-342, 2018. Google Scholar
  11. Matthias Mnich and Erik Jan van Leeuwen. Polynomial kernels for deletion to classes of acyclic digraphs. Discrete Optimization, 25:48-76, 2017. URL: http://dx.doi.org/10.1016/j.disopt.2017.02.002.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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