TIGHT BOUNDS FOR THE MAXIMUM ACYCLIC SUBGRAPH PROBLEM

Given a directed graph G = (V, A), the maximum acyclic subgraph proble m is to find a maximum cardinality subset A' of the arcs such that G' = (V, A') is acyclic. In this paper, we present polynomial-time and RN C algorithms which, when given any graph G without two-cycles, find an acyclic subgraph of size at least (1/2 + Omega(1/root Delta(G)))\A\, where Delta(G) is the maximum degree of G. This bound is existentially tight, since there exists a class of graphs without two-cycles for wh ich the largest acyclic subgraph has size at most (1/2 + O(1/root Delt a(G)))\A\. For the common case of low-degree graphs, our algorithms pr ovide an even better improvement over the known algorithms that find a n acyclic subgraph of size 1/2\A\. For example, for graphs without two -cycles, our algorithms find an acyclic subgraph of size al least 2/3\ A\ when Delta(G)= 2 or 3, and 19/30\A\ when Delta(G)= 4 or 5. For Delt a(G)= 2, this bound is optimal in the worst case. For 3-regular graphs , we can achieve 13/18\A\, which is slightly better than 2/3\A\. As a consequence of this work, vie find that all graphs without two-cycles contain large acyclic subgraphs, a fact which was not previously known . The results can also be extended to find large acyclic subgraphs of graphs with two-cycles. (C) 1997 Academic Press.