Structured Connectivity Augmentation

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



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.29.pdf
  • Filesize: 0.67 MB
  • 13 pages

Document Identifiers

Author Details

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

Cite AsGet BibTex

Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Structured Connectivity Augmentation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.29

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 non-negative 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 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.
Keywords
  • connectivity augmentation
  • graph superposition
  • complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. E. A. Dinic, A. V. Karzanov, and M. V. Lomonosov. The structure of a system of minimal edge cuts of a graph. In Studies in discrete optimization (Russian), pages 290-306. Izdat. "Nauka", Moscow, 1976. Google Scholar
  2. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  3. K. Eswaran and R. Tarjan. Augmentation problems. SIAM Journal on Computing, 5(4):653-665, 1976. URL: http://dx.doi.org/10.1137/0205044.
  4. Petr A. Golovach Fedor V. Fomin and Dimitrios M. Thilikos. Structured connectivity augmentation. CoRR, abs/1706.04255, 2017. URL: http://arxiv.org/abs/1706.04255.
  5. András Frank. Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math., 5(1):25-53, 1992. URL: http://dx.doi.org/10.1137/0405003.
  6. András Frank. Connections in combinatorial optimization, volume 38 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2011. Google Scholar
  7. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. URL: http://dx.doi.org/10.1145/28869.28874.
  8. Bill Jackson and Tibor Jordán. Independence free graphs and vertex connectivity augmentation. J. Comb. Theory, Ser. B, 94(1):31-77, 2005. URL: http://dx.doi.org/10.1016/j.jctb.2004.01.004.
  9. Tibor Jordán. On the optimal vertex-connectivity augmentation. J. Comb. Theory, Ser. B, 63(1):8-20, 1995. URL: http://dx.doi.org/10.1006/jctb.1995.1002.
  10. Tibor Jordán and Zoltán Szigeti. Detachments preserving local edge-connectivity of graphs. SIAM J. Discrete Math., 17(1):72-87, 2003. URL: http://dx.doi.org/10.1137/S0895480199363933.
  11. H. W. Kuhn. The Hungarian method for the assignment problem. Naval Res. Logist. Quart., 2:83-97, 1955. URL: http://dx.doi.org/10.1002/nav.3800020109.
  12. Hiroshi Nagamochi and Toshihide Ibaraki. Algorithmic aspects of graph connectivity, volume 123 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2008. URL: http://dx.doi.org/10.1017/CBO9780511721649.
  13. Ján Plesník. Minimum block containing a given graph. Arch. Math. (Basel), 27(6):668-672, 1976. URL: http://dx.doi.org/10.1007/BF01224737.
  14. Toshimasa Watanabe and Akira Nakamura. Edge-connectivity augmentation problems. Journal of Computer and System Sciences, 35(1):96-144, 1987. URL: http://dx.doi.org/10.1016/0022-0000(87)90038-9.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail