How to find 2-approximate solution for maximum acyclic subgraph of an oriented graph?

Question

How can I find 2-approximate solution for a problem of determining a maximum subgraph with no cycles of an oriented graph? Subgraph is "maximum" if it contains the maximal number of edges amongst other graphs that bear the same property.

2-approximate means that we can build 2 times smaller graph than the optimal one. That's quite a big constraint reduction and should lead to quite a dumb algorithm that--wow!--turns out to be only twice worse than the exact solution.

[That's a problem from the exam I passed recently. Not a homework anymore.]

Answer 1

Divide the set of nodes into two nonempty sets, A and B. Consider the set of edges from A to B and the set of edges from B to A. Throw out the edges from the smaller set and keep the edges from the larger set (break ties arbitrarily). Recurse on A and B individually.

The resulting graph is acyclic because every cycle will be broken the first time the cycle's nodes are split among A and B. The total set of edges we throw out is no bigger than the total set of edges we keep, so we've thrown out at most half of the edges.

[note: I don't think you mean 'maximal' here, you mean 'maximum'. A 'Maximal' graph typically means one which has no proper superset meeting the condition. A maximal acyclic subgraph is easy to construct with no approximation factor, just add all the edges to a new graph one at a time only if they don't add a cycle.]

Answer 2

Vijay Vazirani's book on approximation algorithms has this as the first exercise problem, for which he gives a very obvious hint which I'll paraphrase here.

1. Arbitrarily number the nodes from 1 to n;
2. Split the edges into two sets, forward and backward (no cross edges anymore);
3. Choose the larger set between the forward set and the backward set.

Both the correctness and approximation ratio proofs are trivial.

EDIT: Actually @Keith Randall's solution is just a variant of this, in which he numbered the nodes in set A from 1 to |A| and nodes in B from |A| + 1 to |A| + |B|, and similarly for the recursive case.