5
$\begingroup$

Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where each path must start at $s$. The cost of a collection of paths is the sum of the lengths of the paths.

Is there an efficient algorithm to find the minimum-cost collection of paths? This smells like it might be NP-hard to me (it sounds like a set cover problem), so I'm guessing not. If it is NP-hard, are there any good approximation algorithms or heuristics for this problem?

This sounds a bit like some kind of network-flow problem. Every collection of paths from $s$ to $t$ is an integral flow from $s$ to $t$, and every integral flow from $s$ to $t$ can be expressed as a union of paths from $s$ to $t$. The difference is that (1) the objective function we are trying to minimize is different from the standard network flow problem, and (2) the starting point of each edge is fixed to $s$, but the ending point is not fixed. So, I don't know if network flow like techniques would help.

Motivation: Suppose I have a DFA, and I want to find a testsuite that achieves full edge coverage. A test is a word over the alphabet of the DFA; a testsuite is a collection of tests. A transition is covered by this testsuite if there exists at least one test in the testsuite that causes the DFA to follow that transition at some point. Suppose the cost of a test is its length, and the cost of a testsuite is the sum of the costs of the tests.

Then we can ask whether there is an efficient algorithm that, given a DFA as input, outputs a minimum-cost testsuite that achieves full transition coverage. That's exactly the graph problem outlined above.

Improve this question
$\endgroup$
12
  • $\begingroup$ Does it need to be minimal? You can generate a set that covers all transitions in quadratic time, which will itself be quadratic in the number of transitions. For each transition p ->a q, just find the word of the shortest path from the start to p, concat with a, concat with the shortest path from q to a final state. Two DFS for each transition. You get one word for each transition, and since there's no loops in shortest paths, no word is longer than the number of transitions. $\endgroup$
    – Joey Eremondi
    Commented Jul 8, 2014 at 19:48
  • 1
    $\begingroup$ @jmite, I'd prefer minimal. Your construction is one approximation algorithm, but it's easy to construct examples where it has quadratic cost, while the minimal set has linear cost. Billiska, no, shortest paths doesn't work. It is easy to construct a counterexample: consider, e.g., a long sequential chain of states. (Note that if 2 paths overlap in some edges, those edges contribute twice to the total cost.) The motivation seems fine to me. There are applications (e.g., in formal methods) where our model is a DFA and we'd like to validate the model; transition coverage is standard. $\endgroup$
    – D.W. ♦
    Commented Jul 9, 2014 at 4:07
  • $\begingroup$ Related question. $\endgroup$
    – Raphael
    Commented Jul 9, 2014 at 13:24
  • 1
    $\begingroup$ @vzn How could it be an approximation? A spanning tree is not a collection of paths. "A minimum spanning tree starting at S" doesn't make sense to me. $\endgroup$
    – Juho
    Commented Jul 11, 2014 at 5:24
  • 1
    $\begingroup$ Spanning tree algorithms are generally applied to undirected graphs. As the question states, I am asking about directed graphs. So I can't see any way in which spanning trees solve this problem. Yes, the paths are certainly allowed to overlap. What do you think needs more precision? Is there anything specific that you found unclear or imprecise? $\endgroup$
    – D.W. ♦
    Commented Jul 11, 2014 at 5:51

1 Answer 1

Reset to default
2
$\begingroup$

This is related to a well known problem with a conjecture due to Karpovsky and Moskalev [1] (I still believe is open) that at most V-1 paths are needed. It is tied to conjector of Erdos, Goodman, and Posa [2].

If you want the state of the art today, I suggest doing a thorough reverse-citation search on [1].

[1] Karpovsky, M. G., and E. A. Moskalev. "Covering of edges of graph by a minimal set of paths." Discr. Math 58.2 (1986): 214. (This is in the "research problems" section)

[2] Erdos, Paul, Adolph W. Goodman, and Louis Pósa. "The representation of a graph by set intersections." Canad. J. Math 18.106-112 (1966): 86.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you! This is very interesting -- I appreciate it. However, it doesn't quite answer the question I asked, because those papers talk about minimizing the number of paths; in contrast, I am asking about minimizing the total length of the paths. Therefore, my problem isn't quite the same problem as what those authors seem to be studying. $\endgroup$
    – D.W. ♦
    Commented Jul 10, 2014 at 22:09
  • $\begingroup$ I believe that minimizing total length is at least as hard as minimizing number of paths. Take any graph G covered by a set of paths P. Each path must contain at least one edge not contained in any other path (or else it is superfluous). Take that edge and subdivide it in as many components needed to make all paths from s to a sink of the same length. In this modified graph, minimizing total length is equivalent to minimizing number of paths, but paths haven't changed. $\endgroup$
    – Ari Trachtenberg
    Commented Jul 11, 2014 at 1:22
  • $\begingroup$ Hmm, I have some questions about the proposed equivalence. (1) You seem to be restricting attention to paths that start at $s$ and end at a sink, but I'm not limiting the paths in that way; I want to allow paths that end anywhere. Am I missing something? (2) I don't see how to arrange that all paths from $s$ to a sink have the same length, just by subdividing a few edges. How would I do that? Why is that guaranteed to be possible? $\endgroup$
    – D.W. ♦
    Commented Jul 11, 2014 at 5:49
  • $\begingroup$ 1. You are right ... I have edited the answer to indicate that the problems are related, but not exactly the same. 2. as long as each path has a unique edge of its own, you can subdivide it as needed to get a long enough path length that is common to all $\endgroup$
    – Ari Trachtenberg
    Commented Jul 13, 2014 at 14:32
  • $\begingroup$ 2. OK, given a set of paths $P$, I can make all of them the same length by subdividing edges. But now why would you expect that in the resulting graph minimizing total length is equivalent to minimizing number of paths? The total length of $P$ is equal to (a constant) the total number of paths in $P$, but that's not guaranteed to hold for other sets of paths, so I don't see why minimizing total number of paths in this modified graph will be equivalent to minimizing total path length. Basically, the path length will be the same for all paths in $P$, but not necessarily for other paths. $\endgroup$
    – D.W. ♦
    Commented Jul 13, 2014 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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