LIPIcs.FSTTCS.2012.400.pdf
- Filesize: 489 kB
- 12 pages
Document
Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound
Authors
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2012-12-14
Cite As Get BibTex
Robert Crowston, Gregory Gutin, and Mark Jones. Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 400-411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.FSTTCS.2012.400
Abstract
An oriented graph is a directed graph without directed 2-cycles. Poljak and Turzik (1986) proved that every connected oriented graph G on n vertices and m arcs contains an acyclic subgraph with at least m/2+(n-1)/4 arcs. Raman and Saurabh (2006) gave another proof of this result and left it as an open question to establish the parameterized complexity of the following problem: does G have an acyclic subgraph with least m/2 + (n-1)/4 + k arcs, where k is the parameter? We answer this question by showing that the problem can be solved by an algorithm of runtime (12k)!n^{O(1)}. Thus, the problem is fixed-parameter tractable. We also prove that there is a polynomial time algorithm that either establishes that the input instance of the problem is a Yes-instance or reduces the input instance to an equivalent one of size O(k^2).
Subject Classification
Keywords
- Acyclic Subgraph
- Fixed-parameter tractable
- Polynomial Kernel
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads