The Algorithm Design Manual Second Edition

348

9 .

I N T R A C T A B L E P R O B L E M S A N D A P P R O X I M A T I O N A L G O R I T H M S

9.10.3

Maximum Acyclic Subgraph

Directed acyclic graphs (DAGs) are easier to work with than general digraphs.

Sometimes it is useful to simplify a given graph by deleting a small set of edges or

vertices that suffice to break all cycles. Such feedback set problems are discussed in

Section

16.11

(page

559

).

Here we consider an interesting problem in this class where seek to retain as

many edges as possible while breaking all directed cycles:

Problem: Maximum Directed Acyclic Subgraph

Input: A directed graph G = (V, E).

Output: Find the largest possible subset E



∈ E such that G



= (V, E



) is acyclic.

In fact, there is a very simple algorithm that guarantees you a solution with at

least half as many edges as optimum. I encourage you to try to find it now before

peeking.

Construct any permutation of the vertices, and interpret it as a left-right or-

dering akin to topological sorting. Now some of the edges will point from left to

right, while the remainder point from right to left.

One of these two edge subsets must be at least as large as the other. This means

it contains at least half the edges. Furthermore each of these two edge subsets must

be acyclic for the same reason only DAGs can be topologically sorted—you cannot

form a cycle by repeatedly moving in one direction. Thus, the larger edge subset

must be acyclic and contain at least half the edges of the optimal solution!

This approximation algorithm is simple to the point of almost being stupid.

But note that heuristics can make it perform better in practice without losing this

guarantee. Perhaps we can try many random permutations, and pick the best. Or

we can try to exchange pairs of vertices in the permutations retaining those swaps,

which throw more edges onto the bigger side.