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|))$.
[1]-https://www.cs.tau.ac.il/~yuvalroc/YuvalRochmanThesis.pdf, page 70.
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.
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.
