patternMinor
Find the minimal number of runs to visit every edge of a directed graph
Viewed 0 times
numberthevisitgrapheverydirectededgefindminimalruns
Problem
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:
Result:
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#1698, answer score: 5
Revisions (0)
No revisions yet.