Consider a weighted directed graph G and a special node $u$ in $G$. Are there any complexity results and algorithms on finding a minimum-weight directed acyclic subgraph $S^*$ of $G$ that contains $u$ and $S^*$ also contains exactly $k$ nodes.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This problem is $\mathrm{NP}$-hard. We can reduce DFAS to this problem.
Directed Feedback Arc Set (DFAS) problem is the following: given a directed graph $D$ and number $k$ check whether there is an arc set $S$ of cardinality at most $k$ such that $D - S$ is acyclic. This problem is one of 21 $\mathrm{NP}$-complete problems in the Karp's list.
To build a graph $G$ we give weight $-1$ (minus one) to every arc of the given directed graph $D$ and select an arbitrary vertex $u \in V(D)$. Setting $k = |G| = |D|$ we see that minimum weight acyclic subgraph $S^* \ni u$ of order $k$ of the graph $G$ is the same as the maximum acyclic subgraph of the graph $D$ which has $|A(D)| - |S_{\min}|$ arcs, where $|A(D)|$ is the number of arcs in $D$ and $|S_{\min}|$ is the number of arcs in minimum DFAS $S_{\min}$ of $D$.
