{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T03:27:01Z","timestamp":1648870021062},"reference-count":34,"publisher":"Springer Science and Business Media LLC","license":[{"start":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T00:00:00Z","timestamp":1614556800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T00:00:00Z","timestamp":1614556800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["00021\u02d9159697\/1"]},{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["200020B\u02d9182865\/1"]},{"name":"The National Science Centre Poland","award":["2015\/17\/N\/ST6\/03684"]},{"name":"The National Science Centre Poland","award":["2015\/18\/E\/ST6\/00456"]},{"name":"The National Science Centre Poland","award":["2018\/28\/T\/ST6\/00366"]},{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["00021\u02d9159697\/1"]},{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["00021\u02d9159697\/1"]},{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["00021\u02d9159697\/1"]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"abstract":"Abstract<\/jats:title>In the k<\/jats:italic>-Connectivity Augmentation Problem we are given a k<\/jats:italic>-edge-connected graph and a set of additional edges called links<\/jats:italic>. Our goal is to find a set of links of minimum size whose addition to the graph makes it (k<\/jats:italic> +\u20091)-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case k<\/jats:italic> =\u20091 (a.k.a. the Tree Augmentation Problem or TAP) or k<\/jats:italic> =\u20092 (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-2 approximation algorithms are known for TAP, for CacAP only recently this barrier was breached (hence for k<\/jats:italic>-Connectivity Augmentation in general). As a first step towards better approximation algorithms for CacAP, we consider the special case where the input cactus consists of a single cycle, the Cycle Augmentation<\/jats:italic> Problem (CycAP). This apparently simple special case retains part of the hardness of the general case. In particular, we are able to show that it is APX-hard. In this paper we present a combinatorial $\\left (\\frac {3}{2}+\\varepsilon \\right )$<\/jats:tex-math>\n \n \n \n \n 3<\/mml:mn>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mfrac>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for CycAP, for any constant \u03b5<\/jats:italic> >\u20090. We also present an LP formulation with a matching integrality gap: this might be useful to address the general case of the problem.<\/jats:p>","DOI":"10.1007\/s00224-020-10025-6","type":"journal-article","created":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T09:03:11Z","timestamp":1614589391000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Cycle Augmentation Problem: Hardness and Approximation Algorithms"],"prefix":"10.1007","author":[{"given":"Waldo","family":"G\u00e1lvez","sequence":"first","affiliation":[]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0001-5620-9039","authenticated-orcid":false,"given":"Afrouz","family":"Jabal Ameli","sequence":"additional","affiliation":[]},{"given":"Krzysztof","family":"Sornat","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,1]]},"reference":[{"key":"10025_CR1","doi-asserted-by":"crossref","unstructured":"Adjiashvili, D.: Beating approximation factor two for weighted tree augmentation with bounded costs. ACM Transactions on Algorithms, 1549\u20136325 (2018)","DOI":"10.1137\/1.9781611974782.157"},{"key":"10025_CR2","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Jabal Ameli, A.: Breaching the 2-Approximation barrier for connectivity augmentation: a reduction to steiner tree. ACM Symposium on Theory of Computing (STOC), 815\u2013825 (2020)","DOI":"10.1145\/3357713.3384301"},{"key":"10025_CR3","first-page":"800","volume":"2014","author":"M Basavaraju","year":"2014","unstructured":"Basavaraju, M., Fomin, F. V., Golovach, P., Misra, P., Ramanujan, M. S., Saurabh, S.: Parameterized algorithms to preserve connectivity. ICALP 2014, 800\u2013811 (2014)","journal-title":"ICALP"},{"key":"10025_CR4","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1007\/s00453-016-0270-4","volume":"80","author":"J Cheriyan","year":"2018","unstructured":"Cheriyan, J., Gao, Z.: Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP. Algorithmica 80, 530\u2013559 (2018)","journal-title":"Algorithmica"},{"key":"10025_CR5","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/s00453-017-0275-7","volume":"80","author":"J Cheriyan","year":"2018","unstructured":"Cheriyan, J., Gao, Z.: Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II. Algorithmica 80, 608\u2013651 (2018)","journal-title":"Algorithmica"},{"key":"10025_CR6","first-page":"510","volume":"1999","author":"J Cheriyan","year":"1999","unstructured":"Cheriyan, J., Jord\u00e1n, T., Ravi, R.: On 2-Coverings and 2-Packings of laminar families. ESA 1999, 510\u2013520 (1999)","journal-title":"ESA"},{"key":"10025_CR7","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1016\/j.orl.2008.01.009","volume":"36","author":"J Cheriyan","year":"2008","unstructured":"Cheriyan, J., Karloff, H., Khandekar, R., K\u00f6nemann, J.: On the integrality ratio for tree augmentation. Oper. Res. Lett. 36, 399\u2013401 (2008)","journal-title":"Oper. Res. Lett."},{"key":"10025_CR8","doi-asserted-by":"crossref","unstructured":"Cohen, N., Nutov, Z.: A (1 + ln2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius. Theor. Comput. Sci., 67\u201374 (2013)","DOI":"10.1016\/j.tcs.2013.04.004"},{"key":"10025_CR9","unstructured":"Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.: Introduction to algorithms. Third edition (2009)"},{"key":"10025_CR10","unstructured":"Dinitz, E., Karzanov, A., Lomonosov, M.: On the structure of the system of minimum edge cuts of a graph. Studies in Discrete Optimization, 290\u2013306 (1976)"},{"key":"10025_CR11","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/1497290.1497297","volume":"5","author":"G Even","year":"2009","unstructured":"Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ACM Trans. Algorithms 5, 21:1\u201321:17 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"10025_CR12","first-page":"817","volume":"2018","author":"S Fiorini","year":"2018","unstructured":"Fiorini, S., Gro\u00df, M., K\u00f6nemann, J., Sanit\u00e0, L.: Approximating weighted tree augmentation via Chv\u00e1tal-Gomory cuts. SODA 2018, 817\u2013831 (2018)","journal-title":"SODA"},{"key":"10025_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1137\/0405003","volume":"5","author":"A Frank","year":"1992","unstructured":"Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math. 5, 25\u201353 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"10025_CR14","unstructured":"Frank, A.: Connections in combinatorial optimization. Number 38 in Oxford lecture series in mathematics and its applications (2011)"},{"key":"10025_CR15","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0210019","volume":"10","author":"GN Frederickson","year":"1981","unstructured":"Frederickson, G. N., J\u00e1J\u00e1, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10, 270\u2013283 (1981)","journal-title":"SIAM J. Comput."},{"key":"10025_CR16","first-page":"223","volume":"1994","author":"MX Goemans","year":"1994","unstructured":"Goemans, M. X., Goldberg, A. V., Plotkin, S., Shmoys, D. B., Tardos, \u00c9., Williamson, D.P.: Improved approximation algorithms for network design problems. SODA 1994, 223\u2013232 (1994)","journal-title":"SODA"},{"key":"10025_CR17","first-page":"632","volume":"2018","author":"F Grandoni","year":"2018","unstructured":"Grandoni, F., Kalaitzis, C., Zenklusen, R.: Improved approximation for tree augmentation: Saving by rewiring. STOC 2018, 632\u2013645 (2018)","journal-title":"STOC"},{"key":"10025_CR18","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1006\/jagm.2000.1077","volume":"35","author":"T Hsu","year":"2000","unstructured":"Hsu, T.: On four-connecting a triconnected graph. J. Algorithms 35, 202\u2013234 (2000)","journal-title":"J. Algorithms"},{"key":"10025_CR19","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"10025_CR20","first-page":"202","volume":"35","author":"T Jordan","year":"1995","unstructured":"Jordan, T.: On the optimal vertex-connectivity augmentation. J. Combin. Theory 35, 202\u2013234 (1995)","journal-title":"J. Combin. Theory"},{"key":"10025_CR21","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/jagm.1993.1010","volume":"14","author":"S Khuller","year":"1993","unstructured":"Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. J. Algorithms 14, 214\u2013225 (1993)","journal-title":"J. Algorithms"},{"key":"10025_CR22","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1008304.1008305","volume":"6","author":"DE Knuth","year":"1974","unstructured":"Knuth, D. E.: Postscript about NP-hard problems. SIGACT News 6, 15\u201316 (1974)","journal-title":"SIGACT News"},{"key":"10025_CR23","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/S0097539702416736","volume":"33","author":"G Kortsarz","year":"2004","unstructured":"Kortsarz, G., Krauthgamer, R., Lee, J. R.: Hardness of approximation for Vertex-Connectivity network design problems. SIAM J. Comput. 33, 704\u2013720 (2004)","journal-title":"SIAM J. Comput."},{"key":"10025_CR24","first-page":"23:1","volume":"12","author":"G Kortsarz","year":"2015","unstructured":"Kortsarz, G., Nutov, Z.: A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2. ACM Trans. Algorithms 12, 23:1\u201323:20 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"10025_CR25","first-page":"202","volume":"35","author":"G Kortsarz","year":"2007","unstructured":"Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity problems. Handbook on Approximation Algorithms and Metaheuristics 35, 202\u2013234 (2007)","journal-title":"Handbook on Approximation Algorithms and Metaheuristics"},{"key":"10025_CR26","first-page":"13:1","volume":"2016","author":"G Kortsarz","year":"2016","unstructured":"Kortsarz, G., Nutov, Z.: LP-relaxations for tree augmentation. APPROX\/RANDOM 2016, 13:1\u201313:16 (2016)","journal-title":"APPROX\/RANDOM"},{"issue":"4","key":"10025_CR27","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/2700210","volume":"11","author":"D Marx","year":"2015","unstructured":"Marx, D., V\u00e9gh, L.: Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation. ACM Trans. Algorithms 11 (4), 27:1\u201327:24 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"10025_CR28","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0166-218X(02)00218-4","volume":"126","author":"H Nagamochi","year":"2003","unstructured":"Nagamochi, H.: An approximation for finding a smallest 2-Edge-Connected subgraph containing a specified spanning tree. Discrete Appl. Math. 126, 83\u2013113 (2003)","journal-title":"Discrete Appl. Math."},{"key":"10025_CR29","first-page":"61:1","volume":"2017","author":"Z Nutov","year":"2017","unstructured":"Nutov, Z.: On the tree augmentation problem. ESA 2017, 61:1\u201361:14 (2017)","journal-title":"ESA"},{"key":"10025_CR30","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: Gap location. Comput. Complex. 4, 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"key":"10025_CR31","unstructured":"Shmoys, D. B.: The design of approximation algorithms. Cambridge (2011)"},{"key":"10025_CR32","doi-asserted-by":"crossref","unstructured":"V\u00e9gh, L.: Augmenting undirected Node-Connectivity by one. SIAM Journal of Discrete Mathematics, 695\u2013718 (2011)","DOI":"10.1137\/100787507"},{"key":"10025_CR33","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0022-0000(87)90038-9","volume":"35","author":"T Watanabe","year":"1987","unstructured":"Watanabe, T., Nakamura, A.: Edge-Connectivity Augmentation problems. J. Comput. Syst. Sci. 35, 96\u2013144 (1987)","journal-title":"J. Comput. Syst. Sci."},{"key":"10025_CR34","volume-title":"Algorithms and Complexity","author":"DP Williamson","year":"2011","unstructured":"Williamson, D. P., Shmoys, D. B.: Algorithms and Complexity. Elsevier, Amsterdam (2011)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10025-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-020-10025-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10025-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T09:33:19Z","timestamp":1614591199000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-020-10025-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,1]]},"references-count":34,"alternative-id":["10025"],"URL":"http:\/\/dx.doi.org\/10.1007\/s00224-020-10025-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":["Computational Theory and Mathematics","Theoretical Computer Science"],"published":{"date-parts":[[2021,3,1]]},"assertion":[{"value":"7 December 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}