2
$\begingroup$

Given an undirected graph $G=\{V, E\}$ with its vertices numbered from $1$ to $V$, given two vertices $s$ and $t$ $(1 \leq s \lt t \leq V)$, what is the minimum number of vertices (except $s$ and/or $t$) that we need to remove (we also remove the edges associated with those vertices) so that there doesn't exist any path between $s$ and $t$ anymore?

If it's difficult to solve under general constraints, can it then at least be solved efficiently in case the maximum possible degree of any vertex in the graph is $4$?

My current progress: Maybe it can be solved by using the BFS/DFS numbers obtained from starting BFS/DFS from $s$?

$\endgroup$
2
2
$\begingroup$

Your problem is known as minimum vertex cut or minimum vertex separator. There is a simple reduction from this problem to the directed minimum edge cut, adopted from notes by Locke.

The new graph contains vertices $(s,0),(t,1)$, and $(u,0),(u,1)$ for any $u \neq s,t$, as well as the following edges:

  • For every $\{s,u\} \in E$: the edge $(s,0) \to (u,1)$.
  • For every $\{u,v\} \in E$ (where $u,v \neq s,t$): the edges $(u,0) \to (v,1)$ and $(v,0) \to (u,1)$.
  • For every $\{t,u\} \in E$: the edge $(u,0) \to (t,1)$.
  • For every $u \neq s,t$: the edge $(u,1) \to (u,0)$.

A path $s \to x \to y \to z \to t$ in $G$ lifts to the following directed path in the new graph from $(s,0)$ to $(t,1)$: $$ (s,0) \to (x,1) \to (x,0) \to (y,1) \to (y,0) \to (z,1) \to (z,0) \to (t,1). $$ As can be seen, in order to realize an $s$-$t$ path, we need to use the edges $(u,1) \to (u,0)$ for all vertices $u$ appearing internally in the path.

We now give unit weight to the edges $(u,1) \to (u,0)$ and infinite (or large enough) weight to all other edges, and look for a minimum edge cut between $(s,1)$ to $(t,0)$; this can be solved by computing a maximum flow. A minimum edge cut in the new graph is the same as a minimum vertex cut in $G$.

$\endgroup$

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.