Title: Structured Connectivity Augmentation,
Abstract: We initiate the algorithmic study of the following "structured augmentation"
question: is it possible to increase the connectivity of a given graph G by
superposing it with another given graph H? More precisely, graph F is the
superposition of G and H with respect to injective mapping \phi: V(H)->V(G) if
every edge uv of F is either an edge of G, or \phi^{-1}(u)\phi^{-1}(v) is an
edge of H. We consider the following optimization problem. Given graphs G,H,
and a weight function \omega assigning non-negative weights to pairs of
vertices of V(G), the task is to find \varphi of minimum weight
\omega(\phi)=\sum_{xy\in E(H)}\omega(\phi(x)\varphi(y)) such that the edge
connectivity of the superposition F of G and H with respect to \phi is higher
than the edge connectivity of G. Our main result is the following "dichotomy"
complexity classification. We say that a class of graphs C has bounded
vertex-cover number, if there is a constant t depending on C only such that the
vertex-cover number of every graph from C does not exceed t. We show that for
every class of graphs C with bounded vertex-cover number, the problems of
superposing into a connected graph F and to 2-edge connected graph F, are
solvable in polynomial time when H\in C. On the other hand, for any hereditary
class C with unbounded vertex-cover number, both problems are NP-hard when H\in
C. For the unweighted variants of structured augmentation problems, i.e. the
problems where the task is to identify whether there is a superposition of
graphs of required connectivity, we provide necessary and sufficient
combinatorial conditions on the existence of such superpositions. These
conditions imply polynomial time algorithms solving the unweighted variants of
the problems.