# $k$ vertex-disjoint paths cover in Directed Acyclic Graph

The problem is that: in a directed acyclic graph $G$, I want to know the maximum vertices that can be covered by $k$ vertex-disjoint paths.

Obviously, the value of $k$ is smaller than the minimum path coverage of $G$. Are there any approximation algorithms that can solve this problem?

TL;DR- The problem can be solve optimally using min-cost flow algorithms, such as the Successive Shortest Path (SSP) algorithm. The run time of the algorithm is $O(k\cdot (|E|+|V|\log |V|))$, which is polynomial by the size of the graph (note that $k \in O(|V|)$).

First, note that the problem can be converted into finding $k$ edge-disjointed paths problem, covering the maximum number of vertices. We simply split every vertex $v$ into $v^{in}$ and $v^{out}$ such that: 1) If $(u,v)\in E$ was in the original graph $G=(V,E)$, than $(u^{out},v^{in})\in E'$ is in the transformed graph $G'=(V',E')$. 2) There is an edge $(v^{in},v^{out})\in E'$ for every vertex $v \in V$. A set of $k$ edge-disjointed paths, covering the maximum number of vertices in $G'$ is equivalent to a set of $k$ vertex-disjointed paths, covering the maximum number of vertices in $G$.

Second, we add a source $s$ and a sink $t$ to $G'$. Then, we connect $s$ to all vertices with zero indegree ($d^{in}(v^{in})=0$), and connect all vertices with zero outdegree ($d^{out}(v^{out})=0$) to $t$. We associate every edge $e$ in $G'$ to have capacity $c(e)=1$, and the cost of every edge $e=(v^{in},v^{out})$ is equal to $w(e)=-1$, and for every other edge the cost is $w(e)=0$. We set the required flow between source $s$ and sink $t$ to be equal to $k$. The corresponding min cost flow is simply a union of $k$ edge-disjointed paths in $G'$, which cover the maximum number of vertices. Thus, deriving the min cost flow will imply the corresponding $k$ vertex-disjointed paths in $G$, which cover the maximum number of vertices, as required.

The graph $G'$ is acyclic, even after adding $s$ and $t$. Thus, we can use the SSP algorithm for acyclic graphs with negative weights (more information can be in [1]). The run time of the algorithm will be $O(k\cdot (|E|+|V|\log |V|))$.

• Note that this crucially depends on the graph being acyclic. Otherwise, even though a min cost flow can still be found in polynomial time, it could have circulations. For general graphs the problems is NP-complete (for $k=1$ it's Longest Path). – Tom van der Zanden Aug 30 '18 at 7:14
• We can use SSP algorithm for negative edges if and only if the graph $G$ has no negative cycles. This is follows as the initial node potentials of every node $v$ is set to be the shortest path distance between the source $s$ and a vertex $v$. In particular, when $G$ is acyclic, we use SSP with negative edges. – user3563894 Aug 30 '18 at 7:25
• * The graph $G'$, not $G$ – user3563894 Aug 30 '18 at 8:22

Not sure if this helps, but there is a polynomial time algorithm for finding the longest path in a DAG:

https://en.m.wikipedia.org/wiki/Longest_path_problem

I suppose you can find $k$ such paths by removing the found nodes from the graph. With many random restarts you should get a good set of $k$ paths that cover many nodes.

• How do you want to randomize it? I'm curious how efficient this approach would be :) – Szymon Stankiewicz Aug 30 '18 at 0:06
• You can fix the starting vertex of a given path. By randomizing the starting vertices you should get a different set of paths every time. – Dmitry Kamenetsky Aug 30 '18 at 1:34

If we randomly select $k$ edges which do not have common endpoints between each other as the $k$ initial match, then traverse the edge set and greedily add an edge to these $k$ match if it does not conflict with the current match. I just wonder how well does this approach perform.