Timeline for $k$ vertex-disjoint paths cover in Directed Acyclic Graph
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 22 at 23:12 | comment | added | Neal Young | The algorithm as described has a bug in: "we connect $s$ to all vertices with zero in-degree, and connect all vertices with zero out-degree to $t$." You actually need to connect $s$ to all vertices, and connect all vertices to $t$. E.g. consider the case where $G$ already contains just one root and just one sink. | |
| Aug 30, 2018 at 11:53 | history | edited | user3563894 | CC BY-SA 4.0 |
added 1 character in body
|
| Aug 30, 2018 at 8:22 | comment | added | user3563894 | * The graph $G'$, not $G$ | |
| Aug 30, 2018 at 7:25 | comment | added | user3563894 | 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. | |
| Aug 30, 2018 at 7:14 | comment | added | Tom van der Zanden | 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). | |
| Aug 29, 2018 at 23:26 | history | answered | user3563894 | CC BY-SA 4.0 |