# 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.