<p>I'm searching for an algorithm to do the following</p>

<p>I have a graph $G = (V, E)$ and a set of terminal pairs $\{(s_i, t_i)\}$. I need to find a cut smaller than a given quantity $k$, such that there is a path connecting at least a terminal pair in both subgraphs created by the cut.</p>

CC BY-SA 3.0
2012-08-28T14:33:39.427Z
As stated, the trivial cut (with no edges) works.  In every (in fact the only) component of $G\setminus\varnothing$, there is a path connecting at least one (in fact every) terminal pair.
Jeffε
CC BY-SA 3.0
2012-08-28T14:55:08.217Z
Sorry, I forgot to mention, I need a cut that divides $G$ into 2 subgraphs.
user10522
<ds.algorithms><graph-theory><graph-algorithms>
Min-cut variation
user10522
# Min-cut variation

(Asked by: username_0 on 2012-08-28)

I'm searching for an algorithm to do the following

I have a graph $G = (V, E)$ and a set of terminal pairs $\{(s\_i, t\_i)\}$. I need to find a cut smaller than a given quantity $k$, such that there is a path connecting at least a terminal pair in both subgraphs created by the cut.

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: As stated, the trivial cut (with no edges) works.  In every (in fact the only) component of $G\setminus\varnothing$, there is a path connecting at least one (in fact every) terminal pair.  
> **username_0**: Sorry, I forgot to mention, I need a cut that divides $G$ into 2 subgraphs.  

---

## 0 answers

