K-Connected Spanning Subgraph

Background

Consider that you are given a transportation network, which is a graph. Now you are asked to find out a sub-graph that the transportation capacity between any two sites in the sub-graph is above some threshold k.

This sub-graph could be viewed as kind of a backbone. Its importance is as follows: even if some lines in the transportation network break down, so long as the lines of this sub-graph operates, we can guarantee that the network is able to transport k capacity cargo between any two sites.

If we examine this problem deeply, we may ask the following questions:

Does such a sub-graph exist?
If such a sub-graph exist, how to find one with the minimum number of edges?

Solution

Existence could be answered right now. If the minimum cut of the graph is no less than k, then we could find such a sub-graph. A trivial case is the graph itself. But the second one is difficult. It is believed that this is a NP hard problem.

Approximation algorithms are proposed. One of them was given by Hiroshi Nagamochi and Toshihide ibaraki [A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph] in 1992.

We firstly formalize the notions. To simplify the problem, we focus on graphs that are undirected and consist of no multiple edges and self loops.

k-Connected Graph: A graph is k-Connected if the minimum cut of the graph is no less than k.

Nagamoci-Ibaraki Algorithm Given a graph $G=<V,E>$ , if $F_i = <V, E_i>$ is the maximal spanning forest of $G = <V, E - E_1 - E_2 - .. - E_{i - 1}>$ , the $G_i = <V, E_1 \cup E_2 \cup ... \cup E_{i - 1}>$ is a k-Connected Sub-graph with $k|V| - k(k + 1)$ edges if $k \le \lambda(G)$ , where $\lambda(G)$ is the minimum cut of G.

Here only a scratch of proof is given. Consider a particular cut C in G, whose value $\lambda(C)$ is no less than $\lambda(G)$ . For any $G_i$ with $i <= \lambda(G)$ , it must consist of at least one edge of C. Otherwise we could add an arbitrary edge in $C-E_1-E_2-...-E_{i - 1}$ to $F_i$ such that $F_i$ is still a forest, contradicting $F_i$ is maximal.

Finding a maximal forest in $G=<V,E>$ requires $O(|V| + |E|)$ time. So $O(k(|V| + |E|))$ is required for k-Connected Graph. Nagamochi and Ibaraki did it in $O(|V| + |E|)$ time. They scaned all nodes and edges once and classify edges into different $E_i$ , here $i \in [1...|E|]$ .

Pseudo Code:

h(v) = 0, $\forall v \in V$
$E_i = \emptyset, \forall i \in [1..|E|] $
while $\exists u$ that has not been scanned
- find u with maximum h(u)
- marked u as scanned
- for all $(u,v) \in E$ that has not been scanned
  - marked (u,v) as scanned.
  - if h(u) == h(v) then
    - ++h(u)
  - end if
  - ++h(v)
  - $E_{h(v)} = E_{h(v)} \cup {(u,v)}$
- end for

end while

Analysis

To see that the algorithm indeed works, we have to check two things:

$F_i=<V, E_i>$ is a forest, i.e., $F_i$ does not contain a cycle.
$F_i=<V, E_i>$ is maximal.

$F_i$ doesn't contain a cycle: suppose that when u is being scanned and (u,v) is added to $E_i$ , a cycle is created. Then some edge incident to v belongs to $F_i$ . Thus h(v) >= i before (u, v) is added to $E_i$ . But (u,v) is added to $E_{h(v)}$ after $'++h(v)'$ . So $(u,v) \notin E_i$ . A contradiction.

$F_i$ is maximal. If $F_i$ is not maximal, there is some edge $(u,v) \in E_j$ for some $j > i$ such that $<V, E_i \cup \{(u,v)\}>$ is a forest. Denote the tree containing u in $F_i$ by $T_u$ and the one containing v in $F_i$ by $T_v$ . Further, denote the order of nodes in $T_u$ and $T_v$ being scanned by $[x_1, x_2,..., u,...]$ $[y_1,y_2,...v,...]$ respectively. Without losing generality, suppose $x_1$ is scanned before $y_1$ . When $x_1$ is scanned, we must have $h(x_1) == i - 1$ and $h(y_1) \le i - 1$ . After $x_1$ is scanned, $h(x_1) == h(x_2) ==i$ . For any other node $z \ne {x_1}$ such that $h(z) == i$ , we guarantee that $h(z) == i -1$ before $x_1$ is scanned and $z \in [x_2, x_3,...]$ , otherwise z is scanned before $x_1$ . Now $h(x_2) =i > h(y_1)$ , it's scanned before $y_1$ . Following this way, u is scanned before $y_1$ . When u is scanned, $h(v) \le i - 1$ . So (u, v) is add to some $E_j$ for $j \le i$ . A contradiction.

The number of edges in $G_i$

Suppose the order of nodes being scanned in V is $v_1, v_2, ..$ . The value of $h(v_i)$ could not exceed i, since there are at most one edge $(v_j, v_i)$ incident to $v_i$ for some j less than i. So $v_i$ does not appear in forest $F_k$ for $k > i$ . Then $F_k$ contains at most |V| - 1 - (k - 1) = |V| - k edges. Thus the number of edges in $G_i$ is at most

\Sigma_{i = 1}^{k} (|V| - i) = k|V| - k(k + 1) /2