2026-07-23T00:20:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3876 2024-03-06T10:34:34Z ddc:004 open_access

Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound Crowston, Robert Gutin, Gregory Jones, Mark Acyclic Subgraph Fixed-parameter tractable Polynomial Kernel 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Crowston and Gregory Gutin and Mark Jones 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.400 urn:nbn:de:0030-drops-38765 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.400 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode