Fewest traversals to visit all vertices of DAG

Question

I want to find the fewest traversals to visit all vertices of a DAG. To take a very simple case:

Boston -> New York   -> San Francisco or Las Vegas, both to -> LA
       -> Pittsburgh -> San Francisco or Las Vegas, both to -> LA

There 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     -> LA

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.)

Answer 1

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.

Answer 2

This is the classical problem of chain decomposition of partially ordered set (poset), in the sense that they can be reduced to each other very easily.

Any directed acyclic graph (DAG) $G(V,E)$ defines a poset $P(V, \preceq)$ naturally by $u\preceq v$ for any pair of vertices $(u,v)$ such that there is a path from $u$ to $v$ in $G$. A path (which is named traversal in the question) in $G$ corresponds to a chain in $P$ naturally. A set of paths whose union covers all vertices means exactly that the corresponding set of chains is a not-necessarily-disjoint chain decomposition of $P$.

Note that it is straightforward to modify a not-necessarily-disjoint chain decomposition of $P$ to a disjoint chain decomposition of $P$. Conversely, we can insert vertices between the vertices that correspond to a chain in $P$ so that they become a path in $G$.

There are efficient algorithms to compute a chain decomposition of a poset such as On the Decomposition of Posets by Yangjun Chen and Yibin Chen, 2012. In that paper a poset is, in fact, given by a DAG in the first place.

This is the perfect time to present the very nice Dilworth's theorem: for any finite poset the largest antichain has the same size as the smallest chain decomposition. It says that, for the situation in the question, the minimum number of traversals needed to cover all cities is the maximum number of cities that are pairwise unreachable to one another. Note that New York and Pittsburgh are not reachable from each other.