# How to prove this simple randomized algorithm is 2-approximate for MAS?

The Maximum Acyclic Subgraph (MAS) problem is:

Given a directed graph $$G = (V, E)$$, find the largest subset of edges which are acyclic.

In this paper the authors state the following algorithm:

A simple randomized algorithm achieves a factor 1/2 for this problem: Simply pick a random ordering of the vertices. In fact, one can achieve factor 1/2 by an even simpler algorithm: Pick an arbitrary ordering of the vertices $$\pi$$ and its reverse $$\pi^R$$. One of them has at least 1/2 fraction of the edges in the forward direction.

How can we prove that this is indeed a 2-approximation algorithm? I'm having trouble understanding what a reverse of an ordering could be, and what a "forward" direction is (since we're not dealing with network flow).

To prove the approximation guarantee for any algorithm, we mostly aim to find a lower bound on the optimal value (for minimization problem) or an upper bound on the optimal value (for maximization problem).

Since yours is a maximization problem, a trivial upper bound is $$|E|$$ for the optimal value since any solution is a subset of $$E$$ and thus contains less than $$|E|$$ edges.

Now, let us see how we get $$2$$-approximation. Take any arbitrary ordering of vertices: $$v_1, \dotsc, v_n$$.

1. Let $$|E_f|$$ be the set of edges that goes forward, i.e., all edges in $$E_f$$ are of the form $$(v_i, v_j)$$ such that $$i < j$$. It is easy to see that this subset of edges forms an acyclic subgraph.
2. Similarly, $$E_b$$ be the set of edges that goes backward, i.e., all edges in $$E_b$$ are of the form $$(v_i, v_j)$$ such that $$i > j$$. This subset of edges forms an acyclic subgraph as well.

It is easy to see that either $$|E_f| \geq |E|/2$$ or $$|E_b| \geq |E|/2$$.

Since $$\mathsf{OPT} \leq |E|$$, we get $$|E_f| \geq \mathsf{OPT}/2$$ or $$|E_b| \geq \mathsf{OPT}/2$$.

In other words, either $$E_f$$ or $$E_b$$ is a $$2$$-approximation. The algorithm simply chooses the one with the maximum cardinality.

• Thanks for your answer. Could you please elaborate why it is easy to see that $|E_f| \geq |E|/2$? I'm having trouble grasping that part. Commented May 14, 2023 at 22:02
• @a6623 Okay. Tell me, what if both $|E_f|$ and $|E_b|$ are $< |E|/2$? what would happen to their sum? Commented May 14, 2023 at 22:09