LIPIcs.STACS.2016.55.pdf
- Filesize: 0.63 MB
- 13 pages
Document
Polynomial Kernels for Deletion to Classes of Acyclic Digraphs
Authors
-
Part of:
Volume:
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-02-16
Cite AsGet BibTex
Matthias Mnich and Erik Jan van Leeuwen. Polynomial Kernels for Deletion to Classes of Acyclic Digraphs. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.STACS.2016.55
https://doi.org/10.4230/LIPIcs.STACS.2016.55
Abstract
We consider the problem to find a set X of vertices (or arcs) with |X| <= k in a given digraph G such that D = G-X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made.
In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains NP-hard, but we can obtain a kernel with k^{O(1)} vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.
Keywords
- directed feedback vertex/arc set
- parameterized algorithms
- kernels
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- F. N. Abu-Khzam. A kernelization algorithm for d-hitting set. J. Comput. System Sci., 76(7):524-531, 2010. URL: http://dx.doi.org/10.1016/j.jcss.2009.09.002.
- V. Bafna, P. Berman, and T. Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math., 12(3):289-297, 1999. URL: http://dx.doi.org/10.1137/S0895480196305124.
-
J. Bang-Jensen, A. Maddaloni, and S. Saurabh. Algorithms and kernels for feedback set problems in generalizations of tournaments. Algorithmica, to appear.
- 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):21:1-21:19, November 2008. URL: http://dx.doi.org/10.1145/1411509.1411511.
- M. Cygan, F. Fomin, B.M.P. Jansen, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Open problems for FPT school. Technical report, Warsaw University, 2014. URL: http://fptschool.mimuw.edu.pl/opl.pdf.
- M. Cygan, L. Kowalik, and M. Pilipczuk. Open problems from workshop on kernels. Technical report, Warsaw University, 2013. URL: http://worker2013.mimuw.edu.pl/slides/worker-opl.pdf.
- M. Dom, J. Guo, F. Hüffner, R. Niedermeier, and A. Truß. Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms, 8(1):76-86, 2010. URL: http://dx.doi.org/10.1016/j.jda.2009.08.001.
-
R.G. Downey and M.R. Fellows. Fundamentals of Parameterized Complexity Theory. Springer, 2013.
- G. Even, J. Naor, B. Schieber, and M. Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151-174, 1998. URL: http://dx.doi.org/10.1007/PL00009191.
-
M.R. Fellows, J. Guo, D. Marx, and S. Saurabh. Data reduction and problem kernels (Dagstuhl seminar 12241). Technical Report 2(6), Dagstuhl Reports, 2012.
-
J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006.
- F.V. Fomin, S. Saurabh, and Y. Villanger. A polynomial kernel for proper interval vertex deletion. SIAM J. Discrete Math., 27(4):1964-1976, 2013. URL: http://dx.doi.org/10.1137/12089051X.
-
A.C. Giannopoulou, D. Lokshtanov, S. Saurabh, and O. Suchy. Tree deletion set has a polynomial kernel (but no OPT^O(1) approximation). In Proc. FSTTCS 2014, volume 29 of LIPIcs, pages 85-96, 2014.
-
R.M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85-103, New York, 1972. Plenum.
-
D.G. Kirkpatrick and P. Hell. On the completeness of a generalized matching problem. In Proc. STOC 1978, pages 240-245, New York, 1978. ACM.
-
A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003.
- P.D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281-288, 1995. URL: http://dx.doi.org/10.1007/BF01200760.
- E. Speckenmeyer. On feedback problems in digraphs. In Manfred Nagl, editor, Proc. WG 1990, volume 411 of Lecture Notes Comput. Sci., pages 218-231. Springer, 1990. URL: http://dx.doi.org/10.1007/3-540-52292-1_16.
- S. Thomassé. A 4k² kernel for feedback vertex set. ACM Trans. Algorithms, 6(2), 2010. URL: http://dx.doi.org/10.1145/1721837.1721848.
- M. Yannakakis. The effect of a connectivity requirement on the complexity of maximum subgraph problems. J. ACM, 26(4):618-630, 1979. URL: http://dx.doi.org/10.1145/322154.322157.