Finding paths with minimum intersections

Question

Given a graph and a set of origin-destination $\langle o_i,d_i\rangle$ pairs. The goal is computing a set of paths such that every pair has a path and number of common vertices between paths is minimized.

If you have any relevant references to share I'd like to read them.

• xskxzr: If 3 paths share a specific vertex, is the vertex counted once or three times?
• ghedas: @xskxzr In my problem setting it is counted three times.

Answer 1

Let there be $n$ such pairs, and $k$ vertices. Then you can translate this problem into a minimum-cost integer multi-commodity flow problem.

The core trick is to encode the minimum intersections by turning each vertex of your original problem into a triplet of vertices in the minimum-cost flow problem, an input node, and output node, and $n$ edges connecting the input node to the output node. Each edge has capacity 1ドル,ドル but the costs are respectively 1ドル,ドル $k,ドル $k^2,ドル $k^3,ドル etc. This ensures that no vertex is visited twice unless there is no more efficient solution, and similarly thrice, etc.

Then connect the output nodes to the input nodes in the flow network as in the original graph. If the original graph was an undirected graph make sure to connect the input and outputs of the pair both ways for each edge.

Finally add a source node of commodity $i$ with demand 1ドル$ and connect it to the input node of each $o_i,ドル and a sink node for that commodity connected to the output node of each $d_i$.

---

You can tweak the cost scaling for each shared vertex, that is up to you to decide. Is one triple shared vertex equally bad to two doubly shared vertices? Then use costs 0,ドル 1, 1, \dots$.

Unfortunately minimum-cost integer multi-commodity flow is NP-complete in general, so this does not guarantee any polynomial runtime. But it's a well-studied problem so you might be able to find fast approximations and/or good libraries. Maybe someone else has a better solution, but this problem seems difficult to me to find globally optimal solutions.

• Szymon Stankiewicz: It seems very reasonable to use this approach because problem from the question is NP-complete, because it's harder then vertice disjoint paths problem which is already NP-complete.
• ghedas: @orlp Given vertices have no cost unless they are shared. Shared vertices have the same constant cost, and each edge has a constant cost as well. Aim is finding a set of paths with the minimum cost. Do you know how to find it for small graphs? I am looking for an exact solution rather than approximates or heuristics.
• xskxzr: It seems the costs should be 0,1,2... according to OP's comment.