The Art Gallery Guardian

Reducing edge connectivity to vertex connectivity with small increase in edges


Problem1

Let G=(V,E)G=(V,E) be a graph, we are interested in finding a graph G=(V,E)G'=(V',E'), such that GG is a minor of GG'. We want a partition PP of VV' and a bijection f:PVf:P\to V, such that for any sSs\in S, tTt\in T and S,TPS,T\in P, we have κG(s,t)=λG(f(S),f(T))\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 vv, expand it into a clique of size deg(v)deg(v), and find a bijective label between new vertex in the clique with the edges incident to vv. Connect all the vertices with the same label. Thus in the worst case, we can loosely bound the edges in GG' to be vdeg2(v)v(m/n)2=m2/n=O(nm)\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)O(nm) [1].

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

Definition2

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

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

nn-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 nn-symmetric-connector is a graph with a set of nn vertices TT, such that for any ff a bijection between two disjoint subsets of TT, there exist vertex disjoint paths connecting vv and f(v)f(v) simultaneously.

Let GG be a nn-connected with inputs II and outputs OO, we construct a nn-symmetric connector by make a copy of OO as OO', maintaining the edges of the copies too. Then we pick ff any bijection between II and OO, and contract vv and f(v)f(v) into one vertex. The contracted vertex will be the set TT, and the new graph is a nn-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 .
Tags: connectivity.