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?

  • 6
    $\begingroup$ en.wikipedia.org/wiki/Feedback_arc_set $\endgroup$ – Sasho Nikolov Oct 6 '14 at 6:08
  • 1
    $\begingroup$ 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. $\endgroup$ – R B Oct 6 '14 at 7:33
  • $\begingroup$ 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. $\endgroup$ – Asterix Oct 6 '14 at 22:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Oct 9 '14 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.