Approximating the biggest acyclic subgraph of a given weighted digraph $G= (V,E)$

Question

The base scenario is this: We're given a weighted, directed graph $G= (V,E)$, and are tasked to find an approximating algorithm which returns a digraph $G' = (V,E')$ (i.e. which only deletes edges) so that $G'$ is acyclic, and so that the sum of the weights of the remaining edges $\sum_{e\in E'} weight(e)$ is as big as possible.

Furthermore, the approximation shall be at worst half as good as the optimal solution (i.e. the sum of weights the approximation algorithm returns is at least half as big as the sum of weights of the optimal solution)

This is a homework problem, and I'm looking for hints how to solve it, as I can't seem to figure out any tactic to somehow compare the approximation algorithm ideas to any bound on the optimum solution.

I've come up with 4 ideas of choosing nodes/edges, from which 2 could go arbitrarily bad, and from which I believe 4) has the best chance of succeeding.

So far I have the following results:

1)
Using an algorithm to identify the strongly connected components, I can partition $G$ into a set of subgraphs (one for every strongly connected component), and solve for each subgraph individually (all edges between these subgraphs never create a cycle, and can always be taken into the solution).

2)
Using the tactic to iteratively identify a cycle and remove the one edge of it which has the lowest weight can go arbitrarily bad .

The optimal subgraph $\hat G = (\hat V, \hat E)$ has a topological sorting.
Therefore, there exists a numbering $v_1,..,v_{|V|}$ of the nodes so that with $T:= [v_1,..,v_{|V|}]$, the sum $$\sum_{j=1}^n \sum_{ k=2}^j weight(v_j\to v_k) $$ is minimal. (The sum represents for each node $v$ in $T$ the weight of all edges $(v,v')$ that is lost because $v'$ appears before $v$ in the list, and thus there mustn't exist an edge $v\to v'$

Therefore, an approximation algorithm might guess the topological sorting of the optimal graph.

3)
Going from left to right, and always picking the node that brings with it the highest weight (as sum of its outgoing edges that are eligible) can go arbitrarily bad.

4)
However, so far I haven't found any counter-example for going from right to left, and always picking the node which loses the least weight.

For the last approach, we can show the following inequality:
Let $T:= [v_1,..,v_{n}]$ be the result of the approximation algorithm, then holds: $$ \sum_{k=1}^{j-1} weight(v_j\to v_{k}) \le \sum_{j=2}^n\sum_{k=2}^j weight(v_1\to v_k) = \sum_{j=1}^{n-1} (n-j)weight(v_1\to v_j) $$

Answer 1

First: The upper bound is as stupid as they come: Namely, that at most, the optimal solution contains all edges.

With this upper bound, our approximating algorithm now asserts the following statement:
In every weighted, directed graph $G =(V,E)$ there exists a subgraph $G' = (V,E'), E'\subseteq E$ so that $G'$ is acyclic, and $\sum_{e\in E'} weight(e) \ge \frac 1 2 \sum_{e\in E} weight(e)$,
i.e. we can choose the edges in $E'$ so that they accumulate at least half of the weight of all edges in $E$.

To find such a graph $G'$, we enumerate the vertices in $V$ as $x_1,...,x_n$, and now create two edge sets using it: $$ E_1 = \{(x_i,x_j)\in E\mid x_i<x_j \} \\ E_2 = \{(x_i,x_j)\in E\mid x_i>x_j \} $$ Differently put, imagine the graph $G$. Now move the vertices, so that they form the line $x_1,...,x_n$ from left to right (while keeping the edges intact).
Now, for $E_1$, you remove all edges going left.
For $E_2$, you remove all edges going right.

Each of the corresponding graphs $G_1 := (V,E_1), G_2:=(V,E_2)$ is acyclic, and $E_1\dot\cup E_2=E$, i.e. $E_1, E_2$ contain all edges in $E$ exactly once.

Therefore, either $G_1$ or $G_2$ has to contain at least half of the edge weight, and thus one of them is the wanted subgraph.