1
$\begingroup$

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).

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – a6623
    May 14, 2023 at 22:02
  • $\begingroup$ @a6623 Okay. Tell me, what if both $|E_f|$ and $|E_b|$ are $< |E|/2$? what would happen to their sum? $\endgroup$ May 14, 2023 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.