摘要：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).
