iBGP and Constrained Connectivity
Sep 30, 2009
In this work we first show that the problem of minimizing the size of
an iBGP overlay subject to maintaining a natural notion of correctness
can be reduced to a new connectivity problem that we call "constrained
connectivity".  In constrained connectivity we are given a graph and
are asked to find the smallest subgraph in which every pair of nodes
is connected by a path that is contained in a special subset defined
by the pair.  The iBGP problem is equivalent to a special case of
constrained connectivity with G = K_n.  For this case we give an
Omega(log n) hardness of approximation result and an O(n^{2/3})
approximation algorithm, and for the general case we show that it is
as hard to approximate as Label Cover.  We will also discuss the
integrality gap of the natural LP and some special cases for which
constrained connectivity is easier.