3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Tom van der Zanden Aug 30 '18 at 7:14
  • $\begingroup$ 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. $\endgroup$ – user3563894 Aug 30 '18 at 7:25
  • $\begingroup$ * The graph $G'$, not $G$ $\endgroup$ – user3563894 Aug 30 '18 at 8:22
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do you want to randomize it? I'm curious how efficient this approach would be :) $\endgroup$ – Szymon Stankiewicz Aug 30 '18 at 0:06
  • $\begingroup$ 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. $\endgroup$ – Dmitry Kamenetsky Aug 30 '18 at 1:34
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.