{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:47:51Z","timestamp":1787320071395,"version":"build-2736575974"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE40-0028"],"award-info":[{"award-number":["ANR-17-CE40-0028"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0028"],"award-info":[{"award-number":["ANR-16-CE40-0028"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We initiate the algorithmic study of the following \u201cstructured augmentation\u201d 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 $\\varphi\\colon V(H)\\rightarrow V(G)$ if every edge $uv$ of $F$ is either an edge of $G$ or $\\varphi^{-1}(u)\\varphi^{-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 $\\varphi(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 $\\varphi$ of minimum weight $\\omega(\\varphi)= \\sum_{xy\\in E(H)}\\omega(\\varphi(x)\\varphi(y))$ such that the edge connectivity of the superposition $F$ of $G$ and $H$ with respect to $\\varphi$ is higher than the edge connectivity of $G$. Our main result is the following \u201cdichotomy\u201d complexity classification. We say that a class of graphs $\\mathcal{C}$ has bounded vertex-cover number if there is a constant $t$ depending on $\\mathcal{C}$ only such that the vertex-cover number of every graph from $\\mathcal{C}$ does not exceed $t.$ We show that for every class of graphs $\\mathcal{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\\mathcal{C}.$ On the other hand, for any hereditary class $\\mathcal{C}$ with unbounded vertex-cover number, both problems are NP-hard when $H\\in\\mathcal{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.<\/jats:p>","DOI":"10.1137\/17m1146233","type":"journal-article","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T13:23:22Z","timestamp":1542288202000},"page":"2612-2635","source":"Crossref","is-referenced-by-count":1,"title":["Structured Connectivity Augmentation"],"prefix":"10.1137","volume":"32","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,11,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015,https:\/\/doi.org\/10.1007\/978-3-319-21275-3.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory,\n                      4th ed., Grad. Texts in Math. 173, Springer, New York, 2012.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb3","unstructured":"E. A. Dinic, A. V. Karzanov, and M. V. Lomonosov,\n                      The Structure of a System of Minimal Edge Cuts of a Graph\n                      , Izdat. Nauka, Moscow, 1976."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, New York, 2013,https:\/\/doi.org\/10.1007\/978-1-4471-5559-1.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/0205044"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/0405003"},{"key":"atypb7","unstructured":"A. Frank,\n                      Connections in Combinatorial Optimization\n                      , Oxford Lecture Ser. Math. Appl. 38, Oxford University Press, Oxford, UK, 2011."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"atypb10","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.01.004"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1002"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199363933"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"atypb15","first-page":"642","author":"Marx D.","year":"2015","journal-title":"Philadelphia"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"H. Nagamochi and T. Ibaraki,\n                      Algorithmic Aspects of Graph Connectivity\n                      , Encyclopedia Math. Appl. 123, Cambridge University Press, Cambridge, UK, 2008,https:\/\/doi.org\/10.1017\/CBO9780511721649.","DOI":"10.1017\/CBO9780511721649"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01224737"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(74)90003-9"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(87)90038-9"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1146233","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:53:58Z","timestamp":1787316838000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1146233"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1146233"],"URL":"https:\/\/doi.org\/10.1137\/17m1146233","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}