Given a directed graph G s V, A , the maximum acyclic subgraph problem is to ลฝ . find a maximum cardinality subset Aะ of the arcs such that Gะ s V, Aะ is acyclic. In this paper, we present polynomial-time and RNC algorithms which, when given ลฝ any graph G without two-cycles, find an acyclic subgraph of size at least 1r2 q ลฝ . . < < ลฝ .
'
where โฌ G is the maximum degree of G. This bound is
ลฝ .
existentially tight, since there exists a class of graphs without two-cycles for which ลฝ ลฝ . . < < ' the largest acyclic subgraph has size at most 1r2 q O 1r โฌ G A. For the ลฝ .
common case of low-degree graphs, our algorithms provide an even better im-1 < < provement over the known algorithms that find an acyclic subgraph of size A .
2 For example, for graphs without two-cycles, our algorithms find an acyclic subgraph 2 1 9
or 3, and
A when โฌ G s 4 or 5. For 3 3 0
ลฝ . โฌ G s 2, this bound is optimal in the worst case. For 3-regular graphs, we can 13 2 < < < < achieve A , which is slightly better than A . As a consequence of this work, we 18 3 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.