3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Can you define what you mean by "fewest traversals"? Are you looking for a collection of paths that covers every vertex at least once, and that minimizes the total number of paths? If so, sounds like it could easily be NP-hard; have you tried reducing from some other NP-complete problem (like vertex cover or something)? $\endgroup$ – D.W. Apr 23 at 0:46
  • $\begingroup$ @D.W. I think there's an obvious reduction to show NP-completeness if this were not a DAG (see here). In a DAG however, I think this question (a) in CLRS would be a similar problem (wiki also mentions this). It seems that "Min Path Cover in a DAG" would be the relevant problem here. You just need to be able to show equivalence between this version and min vertex-disjoint path covers. Not sure if this is the answer, but the answer is probably somewhere in this material. $\endgroup$ – ryan Apr 23 at 1:01
  • $\begingroup$ Yeah I think something like min path cover in a dag via matching could work. You could probably show reduction by finding all vertex disjoint paths $a \rightarrow b$ (via black box) then "extending" them to include a prefix path from source to $a$ and a suffix path from $b$ to sink. $\endgroup$ – ryan Apr 23 at 1:06
  • $\begingroup$ @ryan, oh, good point! Your comment suggested an algorithm to me; see my answer below. Does it look correct to you? $\endgroup$ – D.W. Apr 23 at 5:18
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This looks good. I think the only thing I would suggest, is that tracing back the paths is not quite so trivial (but almost). The flow could go from $s_0 \rightarrow v_{in} \rightarrow v_{out} \rightarrow t_0$, without that path $\{s, v, t\}$ existing in the original DAG. If this is the case, then you just need to find some path to $v$ from $s$ and some path from $v$ to $t$, or generalize this. This is kinda what I was hinting at with "extending" paths to include prefix and suffix paths. So you would need this flow-path to include prefix and suffix paths as well. $\endgroup$ – ryan Apr 23 at 6:14
  • $\begingroup$ @ryan, I would treat that as a path of length 0 that starts and ends at $v$. (There doesn't seem to be any restriction about where paths can start or end.) $\endgroup$ – D.W. Apr 23 at 6:19
  • $\begingroup$ Fair enough, it's a minor detail. I had inferred from traversal that OP always intended to start at source and end at sink. Also hinting at this from their "real application" comment. $\endgroup$ – ryan Apr 23 at 6:28
  • $\begingroup$ It seems like another good real-world application for this would be concolic testing of programs. Where the goal is to maximize code coverage (and minimize code runs). Think of each path through the DAG as a potential execution path. We want to hit all sections of code (nodes) but want to minimize the runs. Something like that. $\endgroup$ – ryan Apr 23 at 6:33
  • $\begingroup$ If paths must start and end at the sink, then rather than adding edges $s_0 \to v$ for every vertex $v$, they should only be added to source vertices in the original DAG; and rather than adding $v \to t_0$ for all vertices $v$, do it only for sink vertices in the original DAG. Then that deals with that constraint, and no need to mess around with post-processing the paths. $\endgroup$ – D.W. Apr 23 at 7:30
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "the number of traversals needed to cover all cities is the maximum number of cities" $\endgroup$ – Apass.Jack Apr 24 at 4:40
  • $\begingroup$ I like this solution too but have the same problem of not being able to find a readily available implementation of the algorithm. $\endgroup$ – ed94133 Apr 24 at 17:39

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.