Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

Question

I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to the other one.

I know that each graph can be mapped to a graph with only two outgoing edges for each node, but i can't find a way to convert from many edges to two edges that allows me to perform the reduction. If I convert a node with 3 edges to something like

A----B-OUT1
|    |
OUT3 OUT2

Then the mimimun edge set will contain AB instead of B-OUT2 and B-OUT1, provided that OUT1 and OUT2 are generating a cycle, since by cutting AB it will save a point in the objective function.

Is this reduction possible?

Answer 1

The reduction is possible.

I'll give a reduction of minimum feedback arc set to minimum feedback arc set with maximum outdegree two. The basic idea is that if node $i$ has outdegree $d_{i}$, we make $d_{i}$ copies of node $i$. We add new nodes representing edges so that edges can still be cut in one operation.

Say the graph we want to solve minimum feedback arc set in is (V, E). We'll build a graph (V', E') such that (V', E') has a feedback arc set of size k or less if and only if (V, E) has a feedback arc set of size k or less, and the maximum outdegree of any node in (V', E') is two.

Let $d_{i}$ be the outdegree of node $v_{i}$ in $(V, E)$. Corresponding to node $v_{i}$ in $V$ we'll have nodes $v'_{i, 1} \dots v'_{i, d_{i}}$ in $V'$. For every node $v'_{i, j}$ we'll also have $d_{i}$ nodes $x'_{i, j, 1}, \dots, x'_{i, j, d_{i}}$.

Corresponding to edge $e_{i} = (s_{i}, t_{i})$ from node indexed $s_{i}$ to the one indexed $t_{i}$ in $E$, we'll have the node $e'_{i}$ and nodes $y'_{i, 1}, \dots, y'_{i, d_{t_{i}}}$ in $V'$.

For all vertices $v_{i} \in V$, let $id_{i, k}$ be the index of the $k$th edge leaving node $i$. In $E'$, for every $1 \leq j \leq d_{i}$ we'll have the edge $(v'_{i, j}, x'_{i, j, 1})$ and further for $1 \leq k < d_{i}$ the edge $(x'_{i, j, k}, x'_{i, j, k+1})$ and for $1 \leq k \leq d_{i}$ the edge $(x'_{i, j, k}, e_{id_{i, k}})$.

For all edges $e_{i} = (s_{i}, t_{i})$ in $E$, we have the edges $(e'_{i}, y'_{i, 1})$, for $1 \leq j < d_{t_{i}}$ the edge $(y'_{i, j}, y'_{i, j+1})$, and for $1 \leq j \leq d_{t_{i}}$ the edges $(y'_{i, j}, v'_{t_{i}, j})$.

By the way we defined the nodes, clearly every node has outdegree at most two.

I'll embed an image of an example of the reduction at the bottom of the proof.

Now we'll prove the main claim.

Clearly if $(V, E)$ has a feedback arc set of size $k$, so does $(V', E')$ (cut edge $(e'_{i}, y_{i, 1})$ for every edge $e_{i})$ cut in the original graph).

For the other direction, Take any feedback arc set of size $k'$ in $(V', E')$. We'll build a feedback arc set of cost $k \leq k'$ for $(V, E)$, by cutting edge $e_{i}$ if and only if one or both of the following hold:

1. One of the edges corresponding to $e_{i}$ in $E'$ is cut in $(V', E')$
2. For all of $v'_{s_{i}, 1}, \dots, v'_{s_{i}, d_{s_{i}}}$, at least one edge corresponding to them has been cut.

Note that the second case only happens if we make at least $d_{s_{i}}$ cuts in the copies corresponding to node $v_{s_{i}}$, so $k \leq k'$. Now assume that with these cuts $(V, E)$ has a directed cycle $v_{p_{1}}, \dots, v_{p_{m}}$. Then for the copies corresponding to $v_{p_{j}}$, at least one, say $v'_{p_{j}, h_{j}, 1}$ has has none of its or its $x'$s edges touched, otherwise by condition 2 for cutting an edge we would have no edges leaving $v_{p_{j}}$ in our solution in $(V, E)$.

But then $(V', E')$ also has a directed cycle: the cycle goes through $v'_{p_{j}, h_{j}}$ to $x'_{p_{j}, h_{j}, 1}$ to $\dots$ to $x'_{p_{j}, h_{j}, out_{p_{j}, p_{j+1}}}$ (where $out_{a, b}$ is the index in the edges out of $a$ of the edge to $b$) to $e'_{edi_{p_{j}, p_{j+1}}}$ (where $edi_{a, b}$ is the index of the edge from $a$ to $b$) to $y_{edi_{p_{j}, p_{j+1}}, 1}$ to $\dots$ to $y_{edi_{p_{j}, p_{j+1}}, h_{j+1}}$ to $v'_{p_{j+1}, h_{j+1}}$.

Since a contradiction followed, we must have that the cuts in $(V, E)$ form a feedback arc set, completing the proof.

---

Here's an image of the reduction graph for $V = \{1, 2, 3, 4, 5\}$, $E = \{(1, 2), (1, 3), (2, 4), (2, 5), (4, 1), (3, 1)\}$. Sorry for the massive size. The rectangles at the top-right show the graph $(V, E)$.