World's most popular travel blog for travel bloggers.

# [Answers] Proving the correctness of an algorithm, which computes the connectivity of a directed graph

, ,
Problem Detail:

Let $G=(V,E)$ be a directed graph. The connectivity of a graph is the defined as the cardinality of a smallest separator of $G$. A separator of $G$ is a subset $U$ of $V$, such that $G-U$ is not strongly connected.

Why does the following algorithm compute the connectivity of a graph correctly?

$$\begin{split} &\text{Connectivity}(\text{graph }G=(V,E)) \\ &\;\;\;\;01\text{:}\;\;k=\infty \\ &\;\;\;\;02\text{:}\;\;\text{for }i=1,\ldots,|V| \\ &\;\;\;\;03\text{:}\;\;\{\\ &\;\;\;\;04\text{:}\;\;\;\;\;\;\text{for each }v\in V\\ &\;\;\;\;05\text{:}\;\;\;\;\;\;\{\\ &\;\;\;\;06\text{:}\;\;\;\;\;\;\;\;\;\;\text{compute a minimum }v_i,v\text{-seperator }U_{v_i,v}\\ &\;\;\;\;07\text{:}\;\;\;\;\;\;\;\;\;\;k=\min\left\{k,\left|U_{v_i,v}\right|\right\}\\ &\;\;\;\;08\text{:}\;\;\;\;\;\;\;\;\;\;\text{if }(i>k+1) \text{ return }k\\ &\;\;\;\;09\text{:}\;\;\\ &\;\;\;\;10\text{:}\;\;\;\;\;\;\;\;\;\;\text{compute a minimum }v,v_i\text{-seperator }U_{v,v_i}\\ &\;\;\;\;11\text{:}\;\;\;\;\;\;\;\;\;\;k=\min\left\{k,\left|U_{v,v_i}\right|\right\}\\ &\;\;\;\;12\text{:}\;\;\;\;\;\;\;\;\;\;\text{if }(i>k+1) \text{ return }k\\ &\;\;\;\;13\text{:}\;\;\;\;\;\;\}\\ &\;\;\;\;14\text{:}\;\;\} \end{split}$$

More precisely, why can we return $k$ in line 08 (resp. 12) without concerning the other $u,v$-seperators?

#### Answered By : Yuval Filmus

Suppose that the algorithm is incorrect. We can slightly modify the algorithm by moving lines 8,12 just after the inner loop. If the algorithm returns $k$ incorrectly at the end of step $i$, then there must exist vertices $v_s,v_t$, for $s,t>i$, and a set $S$ of size $k-1$ not containing $v_s,v_t$, such that after removing $S$ there is no path from $v_s$ to $v_t$. I claim that $v_1,\ldots,v_i \in S$: if $v_j \notin S$ for some $j \leq i$, then since $S$ does not disconnect $v_j$ from any other vertex, we would have a path $v_s \to v_j \to v_t$. Since $v_1,\ldots,v_i \in S$, in particular $|S| \geq i$. Stated differently, $k-1 \geq i$. So if $i > k-1$, this is impossible.

My proof, if correct, shows that you can actually use the weaker condition $i > k-1$ in lines 8,12.