6
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – j_random_hacker
    Commented Dec 15, 2016 at 15:01
  • 1
    $\begingroup$ "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. $\endgroup$
    – j_random_hacker
    Commented Dec 15, 2016 at 15:03
  • 1
    $\begingroup$ 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.) $\endgroup$
    – j_random_hacker
    Commented Dec 15, 2016 at 15:43
  • 2
    $\begingroup$ 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). $\endgroup$
    – j_random_hacker
    Commented Dec 15, 2016 at 16:08
  • 2
    $\begingroup$ 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.) $\endgroup$
    – j_random_hacker
    Commented Dec 15, 2016 at 16:13
1
$\begingroup$

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

Your original graph

Then I say to copy it so you have the next graph enter image description here

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)

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – j_random_hacker
    Commented Dec 15, 2016 at 16:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – j_random_hacker
    Commented Dec 15, 2016 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.