Find the minimal number of runs to visit every edge of a directed graph

Question

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.

Answer 1

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.

Answer 2

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.