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:

• Shortest path from that passes through a set of edges once: edges $e \in E$ must be visited exactly once, not at most once.

• Shortest directed path connecting given subset of vertices, Minimum path between two vertices passing through a given set exactly once, Find the shortest path in a graph which visits certain nodes : the constraint is on edges, not on the vertices.

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$:

-
Compute the weight of the path for each permutation of

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.

StackExchange Computer Science Q#67451, answer score: 7