Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound

Original · EN

An oriented graph is a directed graph without directed 2-cycles. Poljak and Turzík (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ᵒ⁽¹⁾. 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²).