5
$\begingroup$

I am looking for an algorithm to find a minimal traversal of a directed graph of the following type. Two vertices are given, a start vertex and a terminating vertex. The traversal consists of several runs; each run is a path from the start vertex to the terminating vertex. A run may visit a node more than once. The length of a traversal is the total number of vertices traversed by the runs, with multiplicity; in other words, the length of a traversal is the number of runs plus the sum of the lengths of the runs.

If there are edges that are not reachable (i.e. the origin of the edge is not reachable from the start vertex, or the terminating vertex is not reachable from the target of the edge), they are ignored.

To illustrate my needs, I give a simple graph and post the result, I would like to receive by the algorithm (start vertex $1$, terminating vertex $4$):

Graph edges:

  • $1 \to 2,3$
  • $2 \to 1,3,4$
  • $3 \to 4$

Result:

  • Run A: $1, 2, 1, 3, 4$
  • Run B: $1, 2, 4$
  • Run C: $1, 2, 3, 4$

Each edge (also each direction) has been covered. Each run begins with vertex $1$ and ends with vertex $4$. The minimum total number of visited vertices is searched. In the given example, the minimum number is $5+3+4=12$. There is no unreachable edge in this example.

$\endgroup$
  • $\begingroup$ May be some edges are inaccessible from source, you want return no way? Also If all edges are accessible from source (without visiting destination), why do not run a dfs to find a path which covers all the edges, and then another dfs from end of a this path to destination? $\endgroup$ – user742 May 6 '12 at 23:11
  • $\begingroup$ I added details according to @Gilles. Unfortunately I did not understand your comment yet (@Saeed_Amiri). I gues dfs means deep-first-search, but please clarify your comment. $\endgroup$ – Lukas May 6 '12 at 23:25
  • 1
    $\begingroup$ So you want to cover all edges between $s$ and $t$ with some number of (not necessarily simple) paths, such that the total length of all paths is minimized? Are we allowed to use the same edge more than once? $\endgroup$ – Artem Kaznatcheev May 7 '12 at 2:52
  • 1
    $\begingroup$ Is it allowed to visit a source and destination in one run multiple times? e.g source is 1, dest is 2, is it possible to have a run like: 1,3,4,2,5,6,2? $\endgroup$ – user742 May 7 '12 at 15:39
  • 1
    $\begingroup$ If you add a directed edge from $t$ to $s$, is this not the chinese postman problem? $\endgroup$ – Nicholas Mancuso May 8 '12 at 15:17
5
$\begingroup$

This looks like a minimum-cost flow problem, but with demands instead of capacities.

A flow in a directed graph $G = (V,E)$ is a function $\phi: E\to \mathbb{R}_{\ge 0}$ that assigns a non-negative real value to every edge, such that for every vertex $v$ except $s$ and $t$, the total flow into $v$ is equal to the total flow out of $v$, or more formally, $ \sum_u \phi(u\mathord\to v) = \sum_w \phi(v\mathord\to w). $ (This equality is usually called the conservation constraint.)

It's useful to think of a flow as a weighted sum of paths from $s$ to $t$. In particular, suppose $P$ is a set of simple $(s,t)$-paths, and for any edge $e$, let $\#P(e)$ denote the number of paths in $P$ that use edge $e$. Then the function $\#P$ is a flow.

In most traditional flow problems, each edge $e$ also has a capacity $c(e)$, and a flow is feasible if and only if $\phi(e) \le c(e)$ for every edge. However, in your case, you want to force the flow to use every edge; so instead, you have a demand constraint $\phi(e) \ge 1$ at each edge.

Finally, we can define the cost of a flow $\phi$ to be the sum of the flow values: $\$(\phi) = \sum_{e\in E} \phi(e)$. Possibly up to some off-by-one errors, your goal is to find a flow $\phi$ of minimum cost that satisfies all the conservation and demand constraints.

This problem can be solved in polynomial time using textbook flow algorithms. Your specific problem is unlikely to appear in any textbook, but all the necessary components are described in Kleinberg and Tardos' Algorithm Design. You may also find my lecture notes on flow algorithms (groundwork, basic algorithms, and extensions) helpful.

$\endgroup$
  • $\begingroup$ A good explanation :) It seems that this algorithm cannot be applied in undirected graph. I have found the same method several days before, but I failed to notice that the graph in this problem is directed. Do you have any ideas about how to solve the undirected version? $\endgroup$ – Wu Yin May 9 '12 at 5:44
2
$\begingroup$

You wish to find the minimal set of ($s$-$t$)-paths such that each edge is covered. I believe this problem is very similar to the chinese postman problem. First, add a directed edge from $t$ to $s$ to make a new graph $G'$. If $G'$ is eulerian the solution happens to be a simple eulerian tour. Otherwise there exists a subset of vertices $T \subseteq V(G')$ that have odd degree. We can resolve this issue by finding something called a $T$-join.

We know there are an even amount of odd-degree vertices by the Handshaking lemma. We then find a minimal $T$-join by finding a minimal matching over the odd-degree vertices. After this we 'double' the $T$-joined vertices to make our final graph $G''$ and then find a eulerian tour under this graph.

Once the tour has been found, simply remove the $(t,s)$ edge, and you will have your set of $(s,t)$-paths. Both finding the minimal $T$-join and finding the minimal eulerian tour take $O(n^3)$ steps. While a flow formulation certainly works fine, this may be a bit faster in practice.

$\endgroup$

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.