Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound

2012/07/16 by Crowston, Robert, Gutin, Gregory, Jones, Mark
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1207.3586

Abstract

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^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²).

Related

• Planar digraphs without large acyclic sets
• Counting the minimum number of arcs in an oriented graph having weak diameter 2
• On the Parameterized Complexity of the Acyclic Matching Problem
• Note about the complexity of the acyclic orientation with parity constraint problem
• Finding an Unknown Acyclic Orientation of a Given Graph