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. Thus F contains both G and H as subgraphs, and the edge set of F is the union of the edge sets of G and \phi(H). We consider the following optimization problem. Given graphs G, H, and a weight function \omega assigning nonnegative weights to pairs of vertices of V(G), the task is to find \phi of minimum weight \omega(\phi)=\sum_{xy\in E(H)}\omega(\phi(x)\phi(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 vertexcover number, if there is a constant t depending on C only such that the vertexcover number of every graph from C does not exceed t. We show that for every class of graphs C with bounded vertexcover number, the problems of superposing into a connected graph F and to 2edge connected graph F, are solvable in polynomial time when H\in C. On the other hand, for any hereditary class C with unbounded vertexcover number, both problems are NPhard 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.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2017:8060,
author = {Fedor V. Fomin and Petr A. Golovach and Dimitrios M. Thilikos},
title = {{Structured Connectivity Augmentation}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {29:129:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8060},
URN = {urn:nbn:de:0030drops80603},
doi = {10.4230/LIPIcs.MFCS.2017.29},
annote = {Keywords: connectivity augmentation, graph superposition, complexity}
}
Keywords: 

connectivity augmentation, graph superposition, complexity 
Collection: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 
Issue Date: 

2017 
Date of publication: 

01.12.2017 