The Art Gallery Guardian

Reducing edge connectivity to vertex connectivity with small increase in edges


Problem1

Let \(G=(V,E)\) be a graph, we are interested in finding a graph \(G'=(V',E')\), such that \(G\) is a minor of \(G'\). We want a partition \(P\) of \(V'\) and a bijection \(f:P\to V\), such that for any \(s\in S\), \(t\in T\) and \(S,T\in P\), we have \(\kappa_{G'}(s,t) = \lambda_{G}(f(S),f(T))\).

Although there is rarely a reason to reduce edge connectivity computation to vertex connectivity computation, because vertex connectivity is much harder in almost every way. It is still a interesting exercise.

The naive method: For each vertex \(v\), expand it into a clique of size \(deg(v)\), and find a bijective label between new vertex in the clique with the edges incident to \(v\). Connect all the vertices with the same label. Thus in the worst case, we can loosely bound the edges in \(G'\) to be \(\sum_{v} deg^2(v)\leq \sum_{v} (m/n)^2 = m^2/n = O(nm)\).

There is another way with the edge blow up to be \(O(nm)\) [1].

However, we want to blow up the number of edges by at most \(O(m)\).

Definition2

A \(n\)-connector is a graph with two disjoint set of vertices \(I\) (inputs) and \(O\) (outputs) such that \(|I|=|O|=n\), and for any bijection \(f:I\to O\), there exist vertex disjoint paths connecting \(v\) and \(f(v)\) simultaneously.

It is known a \(n\)-connector exists with \(O(n)\) edges, because there is a even stronger notion of \(n\)-nonblocking graph[2].

\(n\)-connector seems to be what we need here, but it forces us to have input and output vertices. Thus we can define the following.

Definition3

A \(n\)-symmetric-connector is a graph with a set of \(n\) vertices \(T\), such that for any \(f\) a bijection between two disjoint subsets of \(T\), there exist vertex disjoint paths connecting \(v\) and \(f(v)\) simultaneously.

Let \(G\) be a \(n\)-connected with inputs \(I\) and outputs \(O\), we construct a \(n\)-symmetric connector by make a copy of \(O\) as \(O'\), maintaining the edges of the copies too. Then we pick \(f\) any bijection between \(I\) and \(O\), and contract \(v\) and \(f(v)\) into one vertex. The contracted vertex will be the set \(T\), and the new graph is a \(n\)-symmetric-connector.

References

[1] Z. Galil, G.F. Italiano, Reducing edge connectivity to vertex connectivity, SIGACT News. 22 (1991) 57–61 10.1145/122413.122416.

[2] F.R.K. Chung, On concentrators, superconcentrators, generalizers, and nonblocking networks, Bell System Technical Journal. 58 (1979) 1765–1777 10.1002/j.1538-7305.1979.tb02972.x.

Posted by Chao Xu on 2014-10-30.
Tags: connectivity.