Skip to main content
2 of 4
deleted 41 characters in body
Sudix
  • 719
  • 3
  • 13

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

More precisely, I'm looking for a 2-factor approximation that returns a graph $G' = (V,E')$ (i.e. which only deletes edges) so that $G'$ is acyclic.

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


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.


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.


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

Sudix
  • 719
  • 3
  • 13