Structured connectivity augmentation
From MaRDI portal
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_{xyin 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 Hin C. On the other hand, for any hereditary class C with unbounded vertex-cover number, both problems are NP-hard when Hin 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.
Recommendations
Cites work
- A note on finding the bridges of a graph
- Algorithmic Aspects of Graph Connectivity
- An exact characterization of tractable demand patterns for maximum disjoint path problems
- Approximation Algorithms for Several Graph Augmentation Problems
- Augmentation Problems
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Connections in combinatorial optimization
- Detachments Preserving Local Edge-Connectivity of Graphs
- Edge-connectivity augmentation problems
- Fibonacci heaps and their uses in improved network optimization algorithms
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- Independence free graphs and vertex connectivity augmentation
- Minimum block containing a given graph
- On the optimal vertex-connectivity augmentation
- Parameterized algorithms
Cited in
(6)- Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
- Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem
- scientific article; zbMATH DE number 1757953 (Why is no real title available?)
- Structured connectivity augmentation
- Connectivity preserving network transformers
- A survey of parameterized algorithms and the complexity of edge modification
This page was built for publication: Structured connectivity augmentation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4555048)
