1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ To clarify, please let me know if you mean the following. For every pair of vertices a, b, you want to find a path P(a,b). And you’d like to minimize the weights of the edges that get used more than once? Or would you like to say that if an edge gets used 5 times, this should be penalized more than if that same edge were only used twice? $\endgroup$
    – Pat Devlin
    Apr 22 '20 at 22:19
  • $\begingroup$ Not for every pair of vertices, just pairs of vertices between the two sets $V_a$ and $V_b$. I would prefer to use a higher penalty if used more than once like you suggested, but right now I'm looking for anything that's similar to this question so either will work. $\endgroup$
    – Grizz1618
    Apr 22 '20 at 22:41
  • $\begingroup$ One observation is that we could look for a shortest path between every two vertices. Then we see how well this did. The best possible will be between (that) and (that) minus weight of the entire graph. In the unweighted case, this approximates the thing you want to within an additive term of |E(G)| (not terrible since the value you care about will be quite large unless the vertex partition has one side very small). $\endgroup$
    – Pat Devlin
    Apr 22 '20 at 23:13
  • $\begingroup$ Extended problem, mathoverflow.net/questions/358266/… $\endgroup$ Apr 23 '20 at 7:08
1
$\begingroup$

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}

$\endgroup$
2
  • $\begingroup$ This is a nice formulation of the problem. I hadn't thought of it as a flow problem. Do you mean to write "$\forall i \in V$ and $\forall k \in K$ for the second constraint? $\endgroup$
    – Grizz1618
    Apr 23 '20 at 2:05
  • $\begingroup$ Yes, updated just now. $\endgroup$
    – RobPratt
    Apr 23 '20 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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