patternMinor
Fewest traversals to visit all vertices of DAG
Viewed 0 times
visitalltraversalsfewestdagvertices
Problem
I want to find the fewest traversals to visit all vertices of a DAG. To take a very simple case:
There are lots of ways to traverse this graph, but to visit every vertex, you only need:
I have no preferences in how the graph is visited, and it's fine to visit the same vertex multiple times during different traversals.
(Real application: I am generating test cases for human testers and want them to help them perform their tests at every 'vertex' with as few run-throughs as possible.)
Boston -> New York -> San Francisco or Las Vegas, both to -> LA
-> Pittsburgh -> San Francisco or Las Vegas, both to -> LAThere are lots of ways to traverse this graph, but to visit every vertex, you only need:
1. Boston -> New York -> San Francisco -> LA
2. Boston -> Pittsburgh -> Las Vegas -> LAI have no preferences in how the graph is visited, and it's fine to visit the same vertex multiple times during different traversals.
(Real application: I am generating test cases for human testers and want them to help them perform their tests at every 'vertex' with as few run-throughs as possible.)
Solution
I think you can solve this problem by reducing it to a minimum-cost circulation problem.
Let $G$ be your graph. Replace each vertex $v$ with two vertices $v_\text{in},v_\text{out}$; replace each edge $u \to v$ into $v$ with an edge $u \to v_\text{in}$ and each edge $v \to w$ out of $v$ with an edge $v_\text{out} \to w$, and add the edge $v_\text{in} \to v_\text{out}$. Add a new source vertex $s_0$ and a new sink vertex $t_0$. For each vertex $v$ in your graph, add an edge $s_0 \to v_\text{in}$ and an edge $v_\text{out} \to t_0$. Finally, add an edge $t_0 \to s_0$. All edges have cost 0, lower bound 0, and upper bound $\infty$, except that all $v_\text{in} \to v_\text{out}$ edges have lower bound 1 and the $t_0 \to s_0$ edge has cost 1.
Now, find the minimum cost circulation in this graph. There are polynomial-time algorithms to do this.
I claim that this minimum-cost circulation corresponds to the minimal set of paths to cover all the verticies. In particular, if the minimum cost circulation has cost $c$, then that means there will be $c$ paths that cover the vertices. This circulation will have total flow $c$, so you can trace where each of the $c$ units of flow go starting from $s_0$ to $t_0$, and that will trace out a path; take those $c$ paths as your collection of paths. By the way I defined the lower bounds, this ensures that each vertex will be covered by at least one of these $c$ paths.
Let $G$ be your graph. Replace each vertex $v$ with two vertices $v_\text{in},v_\text{out}$; replace each edge $u \to v$ into $v$ with an edge $u \to v_\text{in}$ and each edge $v \to w$ out of $v$ with an edge $v_\text{out} \to w$, and add the edge $v_\text{in} \to v_\text{out}$. Add a new source vertex $s_0$ and a new sink vertex $t_0$. For each vertex $v$ in your graph, add an edge $s_0 \to v_\text{in}$ and an edge $v_\text{out} \to t_0$. Finally, add an edge $t_0 \to s_0$. All edges have cost 0, lower bound 0, and upper bound $\infty$, except that all $v_\text{in} \to v_\text{out}$ edges have lower bound 1 and the $t_0 \to s_0$ edge has cost 1.
Now, find the minimum cost circulation in this graph. There are polynomial-time algorithms to do this.
I claim that this minimum-cost circulation corresponds to the minimal set of paths to cover all the verticies. In particular, if the minimum cost circulation has cost $c$, then that means there will be $c$ paths that cover the vertices. This circulation will have total flow $c$, so you can trace where each of the $c$ units of flow go starting from $s_0$ to $t_0$, and that will trace out a path; take those $c$ paths as your collection of paths. By the way I defined the lower bounds, this ensures that each vertex will be covered by at least one of these $c$ paths.
Context
StackExchange Computer Science Q#107397, answer score: 2
Revisions (0)
No revisions yet.