I'm curious to find an algorithm that solves the following graph-theory problem.


Suppose I have a graph $G(V,E)$ with two disjoint sets of vertices, $V\_a$ and $V\_b$.


My goal is to find paths from every vertex in $V\_a$ to every vertex in $V\_b$ where the edges in these paths are minimally overlapping. Here we define two paths to be overlapping if they share a same edge. When we say minimally overlapping this can be quantified by measuring the weights of overlapping edges (e.g., two overlapping edges with total weight of 5 is better than one overlapping edge with weight of 10).


Does such an algorithm exist?



Algorithm for finding minimally overlapping paths in a graph
You can formulate this as a multicommodity flow problem and solve it via linear programming. The commodities are $K = V\_a \times V\_b$. Let $A$ be the arc set, with one arc in each direction for each edge in $E$. For $(i,j)\in A$ and $k\in K$, let variable $x\_{i,j}^k \ge 0$ be the flow along arc $(i,j)$ of commodity $k$. Let variable $y\_{i,j}\ge 0$ be the amount by which the total flow (in either direction) across edge $\{i,j\}\in E$ exceeds $1$. Let $b\_{i,k}$ be the supply at node $i$ of commodity $k$; explicitly, $b\_{i,k}$ is $1$ for the source node of commodity $k$, $-1$ for the sink node of commodity $k$, and $0$ otherwise. Let $c\_{i,j}$ be the weight of edge $\{i,j\}$. The problem is to minimize $\sum\_{\{i,j\}\in E} c\_{i,j} y\_{i,j}$ subject to:
\begin{align}
\sum\_{k\in K} (x\_{i,j}^k + x\_{j,i}^k) &\le 1 + y\_{i,j} &&\text{for all $\{i,j\}\in E$}\\
\sum\_j (x\_{i,j}^k - x\_{j,i}^k) &= b\_{i,k} &&\text{for all $i\in V$ and $k\in K$}\\
\end{align}


