×

On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem. (English) Zbl 1407.90241

Summary: In this paper, we propose several integer programming (IP) formulations to exactly solve the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem, or the \((k,\lambda)\)-subgraph problem, based on its graph properties. Special cases of this problem include the well-known \(k\)-minimum spanning tree problem (if \(\lambda =1\)), \(\lambda \)-edge-connected spanning subgraph problem (if \(k=|V|\)) and \(k\)-clique problem (if \(\lambda = k-1\) and there are exact \(k\) vertices in the subgraph). As a generalization of \(k\)-minimum spanning tree and a case of the \((k,\lambda)\)-subgraph problem, the \((k,2)\)-subgraph problem is studied, and some special graph properties are proved to find stronger and more compact IP formulations. Additionally, we study the valid inequalities for these IP formulations. Numerical experiments are performed to compare proposed IP formulations and inequalities.

MSC:

90C10 Integer programming
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bendali F, Diarrassouba I, Didi Biha M, Mahjoub AR, Mailfert J (2007) The \(k\)-edge connected subgraph problem: valid inequalities and branch-and-cut. Design Reliab Commun Networks 1-8 · Zbl 1207.05192
[2] Bienstock, D; Brickell, EF; Monma, CL, On the structure of minimum-weight \(k\)-connected spanning networks, SIAM J Discret Math, 3, 320-329, (1990) · Zbl 0708.05053 · doi:10.1137/0403027
[3] Cai, GR; Sun, YG, The minimum augmentation of any graph to a \(k\)-edge-connected graph, Networks, 19, 151-172, (1989) · Zbl 0672.05057 · doi:10.1002/net.3230190112
[4] Chekuri C, Korula N (2008) Min-cost 2-connected subgraphs with \(k\) terminals, manuscript 2008. Available at arXiv:0802.2528
[5] Chimani, M; Kandyba, M; Ljubi, I; Mutzel, P, Obtaining optimal \(k\)-cardinality trees fast, J Exp Algorithm, 14, 1-23, (2009) · Zbl 1284.68660
[6] Fan, N; Watson, JP, Solving the connected dominating set problem and power dominating set problem by integer programming, Lecture Notes Comp Sci, 7402, 371-383, (2012) · Zbl 1358.05214 · doi:10.1007/978-3-642-31770-5_33
[7] Fortz, B; Mahjoub, AR; McCormick, ST; Pesneau, P, Two-edge-connected subgraphs with bounded rings: polyhedral results and branch-and-cut, Math Program, 105, 85-111, (2006) · Zbl 1085.90009 · doi:10.1007/s10107-005-0576-5
[8] Frederickson, GN; Ja’Ja’, J, Approximation algorithms for several graph augmentation problems, SIAM J Comp, 10, 270-283, (1981) · Zbl 0461.05040 · doi:10.1137/0210019
[9] Gabow, HN; Goemans, MX; Tardos, E; Williamson, DP, Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding, Networks, 53, 345-357, (2009) · Zbl 1205.05125 · doi:10.1002/net.20289
[10] Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-Completeness. Freeman, San Francisco
[11] Garg, N, Saving an epsilon: a \(2\)-approximation for the \(k\)-MST problem in graphs, Theory Comp, 37, 396-402, (2005) · Zbl 1192.05159
[12] Goemans, MX; Bertsimas, D, Survivable networks, linear programming relaxations and the parsimonious property, Mathl Program, 60, 145-166, (1993) · Zbl 0790.90072 · doi:10.1007/BF01580607
[13] Jain, K, A factor \(2\) approximation algorithm for the generalized Steiner network problem, Combinatorica, 21, 39-60, (2001) · Zbl 1107.68533 · doi:10.1007/s004930170004
[14] Karp RM (1972) Reducibility among combinatorial problems. Compl Comp Comput 85-103
[15] Khuller, S; Vishkin, U, Biconnectivity approximations and graph carvings, SIAM J Comp, 41, 214-235, (1994) · Zbl 0822.68082
[16] Lau, LC; Naor, J; Salavatipour, MR; Singh, M, Surivable network design with degree or order constraints, SIAM J Comp, 39, 1062-1087, (2009) · Zbl 1192.68911 · doi:10.1137/070700620
[17] Magnanti, TM; Raghavan, S, Strong formulations for network design problems with connectivity requirements, Networks, 45, 61-79, (2005) · Zbl 1067.68104 · doi:10.1002/net.20046
[18] Menger, K, Zur allgemeinen kurventheorie, Fund Mathem, 10, 96-115, (1927) · JFM 53.0561.01
[19] Quintpo, FP; Cunha, AS; Mateus, GR; Lucena, A, The \(k\)-cardinality tree problem: reformulations and Lagrangian relaxation, Discret Appl Math, 158, 1305-1314, (2010) · Zbl 1231.05139 · doi:10.1016/j.dam.2009.01.017
[20] Robbins, HE, A theorem on graphs, with an application to a problem of traffic control, Am Math Monthly, 46, 281-283, (1939) · JFM 65.0861.01 · doi:10.2307/2303897
[21] Safari, MA; Salavatipour, MR, A constant factor approximation for minimum \(λ \)-edge-connected \(k\)-subgraph with metric costs, Lecture Notes Comp Sci, 5171, 233-246, (2008) · Zbl 1159.68676 · doi:10.1007/978-3-540-85363-3_19
[22] Sebő A, Vygen J (2014) Shorter tours by nicer ears: \(7/5\)-approximation for graphic tsp, \(3/2\) for the path version, and \(4/3\) for two edge-connected subgraphs. Combinatorica. doi:10.1007/s00493-011-2960-3 · Zbl 1340.90201
[23] Simonetti, L; Protti, F; Frota, Y, New branch-and-bound algorithms for \(k\)-cardinality tree problems, Electron Notes Discret Math, 37, 27-32, (2011) · Zbl 1268.05211 · doi:10.1016/j.endm.2011.05.006
[24] Simonetti, L; Cunha, AS; Lucena, A, Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem, Math Program, 142, 511-538, (2013) · Zbl 1282.90155 · doi:10.1007/s10107-012-0590-3
[25] Sun Y (2013) Theoretical and experimental studies on the minimum size \(2\)-edge-connected spanning subgrpah problem, Master thesis, University of Ottawa, Ottawa, Canada
[26] Zhou R, Liu C, Xu Yu J, Liang W, Chen B, Li J (2012) Finding maximal \(k\)-edge-connected subgraphs from a large graph. Proceedings of the 15th International Conference on Extending Database Technology 480-491
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.