Minimum Cardinality Point-to-point Connectivity Augmentation Problem

• Autorzy: Roayaei M. , Razzazi M. R.

Identyfikatory

DOI

10.3233/FI-2018-1690

• Języki publikacji: EN

Abstrakty

EN

We consider an augmentation problem to establish point-to-point connectivity on unweighted graphs where there is no restriction on choosing the augmenting edges (arcs). Given a directed (an undirected) graph G and set P = {(s_i, t_i) : 1 ≤ i ≤ m} of pairs of vertices in the graph, one has to find the minimum cardinality set of arcs (edges) to be added to the graph so that the resulting graph has (can be oriented in order to have) directed paths between the specified pairs of vertices. In the case of undirected graphs, an efficient polynomial-time algorithm is presented. In the case of directed graphs, we find that this problem is NP-hard. In addition, we show that it is fixed-parameter tractable with respect to the combined parameter the number of sink vertices and the number of source vertices of a graph, however, it is W[1]-hard with respect to both parameters the number of new edges and the number of input pairs.

Słowa kluczowe

EN

graph augmentation; point-to-point connectivity; strong-connectivity; bridge-connectivity; FPT-algorithm

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 160, nr 4
• Strony: 447--463
• Opis fizyczny: Bibliogr. 42 poz., rys.

Twórcy

autor

Roayaei M.

• Department of Computer Engineering and Information Technology, Amirkabir University of Technology, Tehran, Iran

autor

Razzazi M. R.

• Department of Computer Engineering and Information Technology, Amirkabir University of Technology, Tehran, Iran
• School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran

Bibliografia

• [1] Mancini F. Graph modification problems related to graph classes. Norway, Bergen: University of Bergen; 2008.
• [2] Yannakakis M. Computing the minimum fill-in. SIAM J Algebr Discret Methods. 1981;2(1):297-309. URL https://doi.org/10.1137/0602010.
• [3] Shamir R, Sharan R, Tsur D. Cluster graph modification problems. Discret Appl Math. 2004;144(1-2):173-182. URL https://doi.org/10.1016/j.dam.2004.01.007.
• [4] Yannakakis M. Node-and edge-deletion NP-complete problems. In: Proceedings of the tenth annual ACM symposium on Theory of Computing; 1978 May 1; ACM. p. 253-264. doi:10.1145/800133.804355.
• [5] Dehne F, Fellows M, Langston M, Rosamond F, Stevens K. An O(2O(k)n3) FPT Algorithm for the Undirected Feedback Vertex Set Problem. Theory Comput Syst. 2007;41:479-492.
• [6] Watanabe T, Nakamura A. Edge-connectivity augmentation problems. J Comput Syst Sci. 1987;144(1): 96-144. URL https://doi.org/10.1016/0022-0000(87)90038-9.
• [7] Szigeti Z. Edge-connectivity augmentations of graphs and hypergraphs. Research Trends in Combinatorial Optimization. 2009;483-521. doi:10.1007/978-3-540-76796-1_22.
• [8] Hsu T, Ramachandran V. A linear time algorithm for triconnectivity augmentation. 32nd Annual Symposium on Foundations of Computer Science; 1991 Oct 1; IEEE. p. 548-559. doi:10.1109/SFCS.1991.185418.
• [9] Jordán T. Minimax theorems in graph connectivity augmentation. EGRES Tech Google Scholar. 2001 Aug 24.
• [10] Hsu T, Ramachandran V. Finding a smallest augmentation to biconnect a graph. SIAM J Comput. 1993; 22(5):889-912. URL https://doi.org/10.1137/0222056.
• [11] Kant G, Bodlaender HL. Planar graph augmentation problems. Lect Notes Comput Sci. 1991;519:286-298. doi:10.1007/BFb0028270.
• [12] Jackson B, Jordán T. Independence free graphs and vertex connectivity augmentation. J Comb Theory, Ser B. 2005;2081(1):31-77. URL https://doi.org/10.1016/j.jctb.2004.01.004.
• [13] Végh L. Augmenting undirected node-connectivity by one. In: Proceedings of the 42nd ACM symposium on Theory of computing. 2010 Jun 5; ACM. p. 695718. doi:10.1145/1806689.1806767.
• [14] Meyerson A, Tagiku B. Minimizing average shortest path distances via shortcut edge addition. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, Berlin, Heidelberg. 2009; p. 272-285. doi:10.1007/978-3-642-03685-9_21.
• [15] Bil D, Gual L, Proietti G. Improved approximability and non-approximability results for graph diameter decreasing problems. Theor Comput. Sci. 2012;417:1222. URL https://doi.org/10.1016/j.tcs.2011.05.014.
• [16] Dodis Y, Khanna S. Design networks with bounded pairwise distance. In: Proceedings of the thirty-first annual ACM symposium on Theory of computing. 1999 May 1; ACM. p. 750759. doi:10.1145/301250.301447.
• [17] Demaine E, Zadimoghaddam M. Minimizing the diameter of a network using shortcut edges. In: AS-candinavian Workshop on Algorithm Theory. 2010 Jun 21; Springer. p. 420-431. doi:10.1007/978-3-642-13731-0_39.
• [18] Papagelis M, Bonchi F, Gionis A. Suggesting ghost edges for a smaller world. In: Proceedings of the 20th ACM international conference on Information and knowledge management. 2011 Oct 24; ACM. p.2305-2308. doi:10.1145/2063576.2063952.
• [19] Leung JMY, Magnanti TL, Singhal V. Routing in point-to-point delivery systems: formulations and solution heuristics. Transp Sci. 1990;24:245-260. URL https://doi.org/10.1287/trsc.24.4.245.
• [20] Hu TC, Kuh E. Theory and Concepts of Circuit Layout In: VLSI circuit layout: theory and design. 1985; IEEE. p. 3-18.
• [21] Robbins HE. A theorem on graphs, with an application to a problem of traffic control. Am Math Mon. 1939;46(5):281-283. URL http://www.jstor.org/stable/2303897.
• [22] Koh KM, Tay EG. Optimal orientations of graphs and digraphs: a survey. Graph Combinator. 2002; 18(4):745-756.
• [23] Gamzu I, Medina M. Improved approximation for orienting mixed graphs. Struct Inf Commun Complex. 2010;7355: 243-253.
• [24] Frank A. Augmenting graphs to meet edge-connectivity requirements. SIAM J Discret Math. 1992; 5(1):25-53. URL https://doi.org/10.1137/0405003.
• [25] Chen YC, Wei HW, Huang, PC, Shih WK, Hsu, T. The bridge-connectivity augmentation problem with a partition constraint. Theor Comput Sci. 2010;411(31-33):2878-2889. URL https://doi.org/10.1016/j.tcs.2010.04.019.
• [26] Nagamochi H. An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree. Discret Appl Math. 2003;126(1):83-113. URL https://doi.org/10.1016/S0166-218X(02)00218-4.
• [27] Nutov Z. Approximating node-connectivity augmentation problems. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, Berlin, Heidelberg. LNCS vol 5687, Springer, 2009 p. 286297. doi:10.1007/978-3-642-03685-9_22.
• [28] Guo J, Uhlmann J. Kernelization and Complexity Results for Connectivity Augmentation Problems. Networks. 2009; 56:31-142. URL https://doi.org/10.1002/net.20354.
• [29] Eswaran KP, Tarjan RE. Augmentation problems. SIAM J Comput. 1976;5:653-665.
• [30] Li CL, McCormick ST, Simchi-Levi D. The point-to-point delivery and connection problems: complexity and algorithms. Discret Appl Math. 1992;36(3):267-292. URL https://doi.org/10.1016/0166-218X(92)90258-C.
• [31] Natu M, Fang SC. On the point-to-point connection problem. Inf Process Lett. 1995;53(6):333-336. URL https://doi.org/10.1016/0020-0190(94)00216-L.
• [32] Natu M, Shu-Cherng F. The point-to-point connection problem analysis and algorithms. Discret Appl Math. 1997;78(1-3):207-226. URL https://doi.org/10.1016/S0166-218X(97)00010-3.
• [33] Feldman J, Ruhl M. The directed Steiner network problem is tractable for a constant number of terminals. SIAM J Comput. 2006; 36(2):543-561. URL https://doi.org/10.1137/S0097539704441241.
• [34] Ishii T, Akiyama Y, Nagamochi H. Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs. Electron Notes Theor Comput Sci. 2003;78:236-259. URL https://doi.org/10.1016/S1571-0661(04)81016-8.
• [35] Taoka S, Watanabe T. Minimum augmentation to k-edge-connect specified vertices of a graph. In: International Symposium on Algorithms and Computation. Springer, Berlin, Heidelberg. 1994 Aug 25; Springer. p. 217-225. doi:10.1007/3-540-58325-4_184.
• [36] Hsu T, Kao M. A unifying augmentation algorithm for two-edge connectivity and biconnectivity. J Comb Optim. 1998; 256(3):237-256. URL doi.org/10.1023/A:1009746026508.
• [37] Niedermeier R. Invitation to Fixed Parameter Algorithms. Habilitationschrift, University of Tubingen; 2006. ISBN: 9780198566076.
• [38] Tarjan R. Depth-first search and linear graph algorithms. SIAM J Comput. 1972;1(2):146-160. URL https://doi.org/10.1137/0201010.
• [39] Tarjan R. A note on finding the bridges of a graph. Inf Process Lett. 1974;2:160-161. doi:10.1016/0020-0190(74)90003-9.
• [40] Medvedovsky A, Bafna V, Zwick U, Sharan R. An algorithm for orienting graphs based on cause-effect pairs and its applications to orienting protein networks. In: International Workshop on Algorithms in Bioinformatics. Springer, Berlin, Heidelberg. 2008 Sep 15; Springer. p. 222-232. doi:10.1007/978-3-540-87361-7_19.
• [41] Guo J, Niedermeier R, Suchý. Parameterized complexity of arc-weighted directed steiner problems. SIAM J Discret Math. 2011;25(2):583-599.
• [42] Fellows MR, Hermelin D, Rosamond F, Vialette S. On the parameterized complexity of multiple-interval graph problems. Theor Comput Sci. 2009;410(1):53-61. URL https://doi.org/10.1016/j.tcs.2008.09.065.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).