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

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

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

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, and $l(v_j) = \sum_{k=1}^{j-1} weight(v_j\to v_{k})$ $$ \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) $$

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