Structured connectivity augmentation

Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 ρ: V(H) → V(G) if every edge uv of F is either an edge of G, or ψ-1(u)-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 (H). We consider the following optimization problem. Given graphs G, H, and a weight function assigning non-negative weights to pairs of vertices of V(G), the task is to find ψ of minimum weight ω(ψ) = σxy2E(H) (ψ(x)ψ(y)) such that the edge connectivity of the superposition F of G and H with respect to ψ 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 ϵ C. On the other hand, for any hereditary class C with unbounded vertex-cover number, both problems are NP-hard when H ϵ 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.

Original languageEnglish (US)
Title of host publication42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
EditorsKim G. Larsen, Jean-Francois Raskin, Hans L. Bodlaender
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770460
StatePublished - Nov 1 2017
Event42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 - Aalborg, Denmark
Duration: Aug 21 2017Aug 25 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017


  • Complexity
  • Connectivity augmentation
  • Graph superposition

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Structured connectivity augmentation'. Together they form a unique fingerprint.

Cite this