<p>I'm bumping my head against the wall trying to prove this problem is NP-complete (it might not be)</p>

<p>Let $G = (V,E)$ be a directed graph with weights $w:E \to \mathbb{R_{\geq 0}}$ on the edges. </p>

<p>The goal is to find a an ordering $\sigma(1),...,\sigma(|V|)$ of $V$ such that the sum of  weights of ``forward edges''
$\sum_{(\sigma(i),\sigma(j)) \in E, i &lt; j} w(\sigma(i),\sigma(j))$
is minimized.</p>

<p>Is this problem NP-complete, or am I missing an obvious algorithm?</p>

CC BY-SA 3.0
2014-10-06T06:08:25.633Z
http://en.wikipedia.org/wiki/Feedback_arc_set
Sasho Nikolov
CC BY-SA 3.0
2014-10-06T07:33:25.790Z
As @SashoNikolov mentioned, this is the FAS problem which is well known to be NP-hard. That said, if you're interested in approximations, look [here](http://www.mathoverflow.net/questions/159558/is-there-a-polynomial-time-approximation-scheme-for-the-feedback-arc-set-problem).
R B
CC BY-SA 3.0
2014-10-06T22:00:41.110Z
Thanks, this turned out to be right. I thought feedback arc sets could only be used to solve the problem of maximizing $\sum w(\sigma(i),\sigma(j))$ (by computing a minimum feedback arc set $S$ and looking at the weight of the DAG that remains after removing $S$), but it turns out if we reverse the permutation $\sigma$ they can also be used to minimize the sum.
Asterix
CC BY-SA 3.0
2014-10-09T18:21:10.867Z
Maximizing the weight of the remaining DAG is known as the Maximum Acyclic Subgraph problem. While they are basically the same problem in terms of exact solutions, they are very different in terms of approximation. MaxAS admits a trivial 2-approximation and doing better is unique games hard.
Sasho Nikolov
<np-hardness><directed-acyclic-graph>
Minimum Weight Ordering of nodes on a directed graph
Asterix
# Minimum Weight Ordering of nodes on a directed graph

(Asked by: username_0 on 2014-10-06)

I'm bumping my head against the wall trying to prove this problem is NP-complete (it might not be)

Let $G = (V,E)$ be a directed graph with weights $w:E \to \mathbb{R\_{\geq 0}}$ on the edges.

The goal is to find a an ordering $\sigma(1),...,\sigma(|V|)$ of $V$ such that the sum of weights of ``forward edges''
$\sum\_{(\sigma(i),\sigma(j)) \in E, i < j} w(\sigma(i),\sigma(j))$
is minimized.

Is this problem NP-complete, or am I missing an obvious algorithm?

**Tags:** np-hardness, directed-acyclic-graph
> **Comments:**
> **username_1**: http://en.wikipedia.org/wiki/Feedback_arc_set  
> **username_2**: As @SashoNikolov mentioned, this is the FAS problem which is well known to be NP-hard. That said, if you're interested in approximations, look [here](http://www.mathoverflow.net/questions/159558/is-there-a-polynomial-time-approximation-scheme-for-the-feedback-arc-set-problem).  
> **username_0**: Thanks, this turned out to be right. I thought feedback arc sets could only be used to solve the problem of maximizing $\sum w(\sigma(i),\sigma(j))$ (by computing a minimum feedback arc set $S$ and looking at the weight of the DAG that remains after removing $S$), but it turns out if we reverse the permutation $\sigma$ they can also be used to minimize the sum.  
> **username_1**: Maximizing the weight of the remaining DAG is known as the Maximum Acyclic Subgraph problem. While they are basically the same problem in terms of exact solutions, they are very different in terms of approximation. MaxAS admits a trivial 2-approximation and doing better is unique games hard.  

---

## 0 answers

