patternMinor
Finding paths with minimum intersections
Viewed 0 times
withintersectionspathsminimumfinding
Problem
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.
If you have any relevant references to share I'd like to read them.
Solution
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.
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.
Context
StackExchange Computer Science Q#96746, answer score: 3
Revisions (0)
No revisions yet.