# Shortest walk through a given subset of edges

Given an undirected weighted graph $G = (V, \{E,F\})$, how to find the shortest walk that passes through all edges $e \in E$ exactly once?

I'd like to know if there is a general approach to this problem. However, additional constraint may be added for my specific scenario.

The graph $G_0 = (V, E)$ initially has only edges that must be crossed, but it's disconnected:

• Each connected component is formed by 2 vertices and 1 edge.
• Each vertex $v$ is the endpoint of exactly one edge $\in E$. This means that any two edges $e_i, e_j \in E$ don't have a vertex $v$ in common.
• The cost of each edge $e \in E$ is $0$.
• The number of edges in $E$ is at most 1000, usually between 10 and 100.

Then other edges $f \in F$ are added with to link any two vertices (except the one already linked by $e$), so $G = (V, \{E,F\})$.

• The cost of each edge $f \in F$ is $> 0$

Related questions

I found a few related questions, but they doesn't seem to help:

Not working solutions

I tried a few approaches so far, but I'm unable to make them work properly. E.g.:

• Convert $G$ to its line graph $L$. I can't figure out how to assign a proper weight to edges in $L$
• If I can find a proper way to construct $L$, adding a dummy vertex $s$ on $L$ allows to solve this with TSP. Then I'll know the order of the edges $e$, but not the direction.
• I really don't want to use brute-force. It may become impractical very soon.

Almost-Working solutions for the specific case

Since by construction every walk will be of the form: $e_1, f_1, e_2, ... f_n, e_n$:

1. Compute the weight of the path for each permutation of edges in $E$. The edge $f$ between two edges $e$ will be the mininmum weight one. Pick up the minimum weight path. This solution is brute-force, so not really practical for a large number of edges in E.

2. Start from an edge $e$. Follow the min-cost edge $f$ starting from the end-vertex in $e$. Repeat until all edges in $E$ are reached. This solution is not guaranteed to find the shortest path.

This is NP-hard, so it's very unlikely that a polynomial-time algorithm exists.

Given any instance $G=(V, E)$ of Hamiltonian Path, create a new graph $G'=(V', E')$ in which every vertex $v \in V$ becomes a pair of vertices $v_+, v_-$ connected by an edge in $G'$. All of these edges should also be added to $F$. Then for each $(u, v) \in E$, add the corresponding 4 edges $(u_-, v_-), (u_-, v_+), (u_+, v_-), (u_+, v_+)$ to $E'$ (but not to $F$). All edges in $E'$ get weight 1.

Now if and only if there is a Hamiltonian Path in $G$, there is a path (and thus also a walk) of length $2|V|-1$ in $G'$ that passes through all the edges in $F$. (Exercise: Prove that if a walk having length $2|V|-1$ and passing through all edges in $F$ exists in $G'$, then $G$ has a Hamiltonian Path; the other direction is easy.) IOW, if your problem could be solved efficiently by some algorithm, then that algorithm could be used as a subroutine to solve Hamiltonian Path efficiently too, and people don't think that's very likely.

• My answer doesn't describe an algorithm for solving your problem; it describes an "algorithm" for solving the Hamiltonian Path problem by converting it into an instance of your problem. This is one way to show that your problem is NP-hard -- that is, that it's very unlikely that any algorithm exists that can solve your problem. – j_random_hacker Dec 15 '16 at 15:01
• "Also, I understand that this problem may probably be NP. This isn't a major concern right now." You mean "NP-hard", BTW ("NP" is a larger class of problems). It is a major concern that your problem is NP-hard if you "really don't want to use brute-force", since being NP-hard effectively means that brute force is the only way that guarantees an optimal solution. – j_random_hacker Dec 15 '16 at 15:03
• It's unfortunate that the problem is NP-hard, but that's not my fault -- I'm just the messenger here. What you perhaps don't seem to appreciate is that the proof sketch above saves you time hunting for something that doesn't exist. You can now pick a brute-force algorithm with your conscience clear that nothing better exists "out there, somewhere". (Not quite true; for many NP-hard problems there exist algorithms that save time over the most naive brute force, but they are all still exponential in the input size -- at best, the exponent decreases a bit.) – j_random_hacker Dec 15 '16 at 15:43
• You can turn an instance of your problem into a TSP instance with a simple transformation, and then apply one of the advanced (exact or heuristic) solvers to it: Just subdivide each edge in $E$ (earlier I had $E$ and $F$ mixed up, BTW) by adding a new vertex in the middle. Now any TSP tour can only visit such a vertex by visiting one of its 2 neighbours, then the vertex, then the other neighbour -- equivalent to visiting the original "edge". Finally add a single extra vertex at a huge distance from every vertex in your original graph (and not adjacent to the other extra vertices). – j_random_hacker Dec 15 '16 at 16:08
• You're welcome. The tour you get from the TSP solver will necessarily include exactly 2 edges to this "far-away" vertex -- cut them to find the path you want. (Actually this will find the shortest path that visits all edges in $E$ exactly once; to allow a vertex to be revisited multiple times, you can turn each original vertex into $n$ copies, all connected to each other by 0-length edges.) – j_random_hacker Dec 15 '16 at 16:13

If you want a walk from $v$ to $u$, and it has to cross every edge of $F$ once, you can do the next: -Duplicate al the nodes from G |F| times (you put every copy in levels) -A node $v_{i}$ (node in level i) has and edge to a node $v_{i+1}$ iff this two had an edge in the original graph and this edge is in F. Then, you want the min walk from $v_0$ to $u_{|F|}$. You can use Dijkstra for this. I think this works but I'm not sure.

If this is your original graph, the red edges are the ones I want for my path

Then I say to copy it so you have the next graph

Then you want a path from u_o to v_2 since there are the paths that uses two red edges. I added weight 1 to the edges because you don't want to cross it more than once. (If the weight were 0, then the min path can go through this edge many times without cost)

• Thanks, let me think about it. However, I need to go trough edges in E exactly once, not F. It's just notation, doesn't change much – Miki Dec 15 '16 at 12:29
• I can't figure out how to make this work. Can you please elaborate? – Miki Dec 15 '16 at 13:03
• I need to verify this, but thanks for your effort – Miki Dec 15 '16 at 15:43
• I'm afraid this won't work reliably for $|F| \ge 2$, since nothing stops Dijkstra from choosing several layer-traversing edges that correspond to the same original edge in $F$, and leaving other edges from $F$ unvisited. You need to somehow record which edges from $F$ have already been visited by the path so far, so that they can be forbidden from later layers... You can do this by turning each vertex in $G$ into $2^{|F|}$ vertices, each corresponding to a different set of already-visited $F$-edges, but of course this makes the problem exponential-time (and -space). – j_random_hacker Dec 15 '16 at 16:45
• Another way is to fix a particular ordering of $F$-edges. You can then apply your poly-time and -space algorithm directly -- but you'll need to rerun it for every possible ordering (i.e., $|F|!$ times) and take the best overall. – j_random_hacker Dec 15 '16 at 16:48