{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,4]],"date-time":"2026-01-04T08:07:10Z","timestamp":1767514030517,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2020,3,18]],"date-time":"2020-03-18T00:00:00Z","timestamp":1584489600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this paper, we consider the problem of improving the reachability of a graph. We approach the problem from a graph augmentation perspective, in which a limited set size of edges is added to the graph to increase the overall number of reachable nodes. We call this new problem the Maximum Connectivity Improvement (MCI) problem. We first show that, for the purpose of solve solving MCI, we can focus on Directed Acyclic Graphs (DAG) only. We show that approximating the MCI problem on DAG to within any constant factor greater than     1 \u2212 1  \/  e     is    NP   -hard even if we restrict to graphs with a single source or a single sink, and the problem remains    NP   -complete if we further restrict to unitary weights. Finally, this paper presents a dynamic programming algorithm for the MCI problem on trees with a single source that produces optimal solutions in polynomial time. Then, we propose two polynomial-time greedy algorithms that guarantee     ( 1 \u2212 1  \/  e )    -approximation ratio on DAGs with a single source, a single sink or two sources.<\/jats:p>","DOI":"10.3390\/a13030068","type":"journal-article","created":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T03:54:14Z","timestamp":1584590054000},"page":"68","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Adding Edges for Maximizing Weighted Reachability"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7321-3467","authenticated-orcid":false,"given":"Federico","family":"Cor\u00f2","sequence":"first","affiliation":[{"name":"Department of Computer Science, Sapienza University of Rome, 00161 Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianlorenzo","family":"D'Angelo","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute (GSSI), 67100 L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristina M.","family":"Pinotti","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Mathematics, University of Perugia, 06123 Perugia PG, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,3,18]]},"reference":[{"unstructured":"Cordasco, G., Gargano, L., Lafond, M., Narayanan, L., Rescigno, A.A., Vaccaro, U., and Wu, K. (2016). Whom to befriend to influence people. arXiv.","key":"ref_1"},{"unstructured":"D\u2019Angelo, G., Severini, L., and Velaj, Y. (2017, January 21\u201325). Selecting nodes and buying links to maximize the information diffusion in a network. Proceedings of the 42st International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, Aalborg, Denmark.","key":"ref_2"},{"doi-asserted-by":"crossref","unstructured":"Cor\u00f2, F., D\u2019Angelo, G., and Velaj, Y. (2019, January 10\u201316). Recommending Links to Maximize the Influence in Social Networks. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China.","key":"ref_3","DOI":"10.24963\/ijcai.2019\/304"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.tcs.2013.08.003","article-title":"On the approximability of the link building problem","volume":"518","author":"Olsen","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_5","first-page":"12","article-title":"Refining social graph connectivity via shortcut edge addition","volume":"10","author":"Papagelis","year":"2015","journal-title":"ACM Trans. Knowl. Discov. Data (TKDD)"},{"doi-asserted-by":"crossref","unstructured":"Jung, J., Seo, D., and Lee, J. (2018). Counter-Based Broadcast Scheme Considering Reachability, Network Density, and Energy Efficiency for Wireless Sensor Networks. Sensors, 18.","key":"ref_6","DOI":"10.3390\/s18010120"},{"doi-asserted-by":"crossref","unstructured":"Cor\u00f2, F., D\u2019Angelo, G., and Velaj, Y. (2019). Recommending Links to Control Elections via Social Influence. Algorithms, 12.","key":"ref_7","DOI":"10.3390\/a12100207"},{"doi-asserted-by":"crossref","unstructured":"Castiglioni, M., Ferraioli, D., and Gatti, N. (2019). Election Control in Social Networks via Edge Addition or Removal. arXiv.","key":"ref_8","DOI":"10.1609\/aaai.v34i02.5556"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1137\/0205044","article-title":"Augmentation problems","volume":"5","author":"Eswaran","year":"1976","journal-title":"SIAM J. Comput."},{"key":"ref_10","first-page":"420","article-title":"Minimizing the Diameter of a Network Using Shortcut Edges","volume":"Volume 6139","author":"Demaine","year":"2010","journal-title":"Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.tcs.2011.05.014","article-title":"Improved approximability and non-approximability results for graph diameter decreasing problems","volume":"417","author":"Proietti","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1016\/j.ipl.2015.06.015","article-title":"Reducing the diameter of a unit disk graph via node addition","volume":"115","author":"Ianni","year":"2015","journal-title":"Inf. Process. Lett."},{"unstructured":"Bil\u00f2, D. (2018, January 16\u201319). Almost Optimal Algorithms for Diameter-Optimally Augmenting Trees. Proceedings of the 29th International Symposium on Algorithms and Computation, ISAAC 2018, Jiaoxi, Yilan, Taiwan.","key":"ref_13"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1080\/15326340600649052","article-title":"The Effect of New Links on Google Pagerank","volume":"22","author":"Avrachenkov","year":"2006","journal-title":"Stoc. Models"},{"key":"ref_15","first-page":"272","article-title":"Minimizing Average Shortest Path Distances via Shortcut Edge Addition","volume":"Volume 5687","author":"Meyerson","year":"2009","journal-title":"Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)"},{"key":"ref_16","first-page":"43","article-title":"Greedily improving our own centrality in a network","volume":"Volume 9125","author":"Crescenzi","year":"2015","journal-title":"Proceedings of the 14th International Symposium on Experimental Algorithms (SEA 2015)"},{"key":"ref_17","first-page":"9:1","article-title":"Greedily Improving Our Own Closeness Centrality in a Network","volume":"11","author":"Crescenzi","year":"2016","journal-title":"TKDD"},{"doi-asserted-by":"crossref","unstructured":"Ishakian, V., Erd\u00f6s, D., Terzi, E., and Bestavros, A. (2012, January 26\u201328). A Framework for the Evaluation and Management of Network Centrality. Proceedings of the 12th SIAM International Conference on Data Mining (SDM), Anaheim, CA, USA.","key":"ref_18","DOI":"10.1137\/1.9781611972825.37"},{"doi-asserted-by":"crossref","unstructured":"Kapron, B.M., King, V., and Mountjoy, B. (2013, January 6\u20138). Dynamic graph connectivity in polylogarithmic worst case time. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, LA, USA.","key":"ref_19","DOI":"10.1137\/1.9781611973105.81"},{"doi-asserted-by":"crossref","unstructured":"Nanongkai, D., Saranurak, T., and Wulff-Nilsen, C. (2017, January 15\u201317). Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA.","key":"ref_20","DOI":"10.1109\/FOCS.2017.92"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s00453-007-9051-4","article-title":"Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure","volume":"51","author":"Demetrescu","year":"2008","journal-title":"Algorithmica"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"712","DOI":"10.1137\/13093618X","article-title":"A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time","volume":"45","author":"Roditty","year":"2016","journal-title":"SIAM J. Comput."},{"unstructured":"Cor\u00f2, F., D\u2019Angelo, G., and Pinotti, C.M. (2018, January 23\u201324). On the Maximum Connectivity Improvement Problem. Proceedings of the Algorithms for Sensor Systems\u201414th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018, Helsinki, Finland.","key":"ref_23"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company.","key":"ref_25"},{"doi-asserted-by":"crossref","unstructured":"Feige, U. (1998). A Threshold of Ln N for Approximating Set Cover. J. ACM, 45.","key":"ref_26","DOI":"10.1145\/285055.285059"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0167-6377(96)00021-1","article-title":"An O(pn2). algorithm for the p-median and related problems on tree graphs","volume":"19","author":"Tamir","year":"1996","journal-title":"Oper. Res. Lett."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","article-title":"An analysis of approximations for maximizing submodular set functions\u2014I","volume":"14","author":"Nemhauser","year":"1978","journal-title":"Math. Program."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/3\/68\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:07:46Z","timestamp":1760173666000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/3\/68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,18]]},"references-count":28,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2020,3]]}},"alternative-id":["a13030068"],"URL":"https:\/\/doi.org\/10.3390\/a13030068","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,3,18]]}}}