{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T04:56:33Z","timestamp":1790916993362,"version":"4.1.0"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds $B_v$ on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a $(2,2B_v+3)$-approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex v is at most $2B_v+3$. This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly k-Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost $\\lambda$-edge-connected subgraph with at least k vertices, which we call the $(k,\\lambda)$-subgraph problem. This generalizes some well-studied classical problems such as the k-MST and the minimum cost $\\lambda$-edge-connected subgraph problems. We give a polylogarithmic approximation for the $(k,2)$-subgraph problem. However, by relating it to the Densest k-Subgraph problem, we provide evidence that the $(k,\\lambda)$-subgraph problem might be hard to approximate for arbitrary $\\lambda$.<\/jats:p>","DOI":"10.1137\/070700620","type":"journal-article","created":{"date-parts":[[2009,9,2]],"date-time":"2009-09-02T18:07:04Z","timestamp":1251914824000},"page":"1062-1087","source":"Crossref","is-referenced-by-count":48,"title":["Survivable Network Design with Degree or Order Constraints"],"prefix":"10.1137","volume":"39","author":[{"given":"Lap Chi","family":"Lau","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,9,2]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979528826X"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Bansal, R. Khandekar, and V. Nagarajan,\n                      Additive guarantees for degree bounded directed network design\n                      , in Proceedings of the 40th ACM Symposium on Theory of Computing, ACM, New York, 2008, pp. 769\u2013778.","DOI":"10.1145\/1374376.1374486"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581256"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1542"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"K. Chaudhuri, S. Rao, S. Riesenfeld, and K. Talwar,\n                      What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs\n                      , in Proceedings of APPROX 2005, Berkeley, CA, 2005, pp. 26\u201339.","DOI":"10.1007\/11538462_3"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"K. Chaudhuri, S. Rao, S. Riesenfeld, and K. Talwar,\n                      Push relabel and an improved approximation algorithm for the bounded-degree mst problem\n                      , in Proceedings of ICALP 2006, Venice, Italy, 2006, pp. 191\u2013201.","DOI":"10.1007\/11786986_18"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"C. Chekuri, M. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour,\n                      Approximation algorithms for non-uniform buy-at-bulk network design problems\n                      , in Proceedings of FOCS 2006, IEEE Computer Society, Washington, DC, 2006, pp. 677\u2013686.","DOI":"10.1109\/FOCS.2006.15"},{"key":"R10","unstructured":"C. Chekuri and N. Korula,\n                      Pruning 2-Connected Graphs, and Applications\n                      , to appear in Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2008."},{"key":"R11","unstructured":"T. Feder, R. Motwani, and A. Zhu,\n                      \n                        k\n                        -Connected spanning subgraphs of low degree\n                      \n                      , in The Electronic Colloquium on Computational Complexity, ECCC report 41, 2006."},{"key":"R12","unstructured":"M. F\u00fcrer and B. Raghavachari,\n                      An NC approximation algorithm for the minimum degree spanning tree problem\n                      , in Proceedings of the 28th Annual Allerton Conference on Communication, Control, and Computing, Allerton, IL, 1990, pp. 274\u2013281."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1042"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"R15","first-page":"63","volume":"41","author":"Frank A.","year":"1979","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"H. Gabow,\n                      On the $L_\\infty$-norm of extreme points for crossing supermodular directed network LPs\n                      , in Proceedings of IPCO 2005, Berlin, Germany, 2005, pp. 392\u2013406.","DOI":"10.1007\/11496915_29"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"N. Garg,\n                      \n                        A 3-approximation for the minimum tree spanning\n                        k\n                        vertices\n                      \n                      , in Proceedings of the 37th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 1996, pp. 302\u2013309.","DOI":"10.1109\/SFCS.1996.548489"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"N. Garg,\n                      Saving an epsilon: A 2-approximation for the k-MST problem in graphs\n                      , in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 396\u2013402.","DOI":"10.1145\/1060590.1060650"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. X. Goemans,\n                      Minimum bounded-degree spanning trees,\n                      in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2006, pp. 273\u2013282.","DOI":"10.1109\/FOCS.2006.48"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer-Verlag, New York, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"T. Kir\u00e1ly, L. C. Lau, and M. Singh,\n                      Degree bounded matroids and submodular flows\n                      , in Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization, Bertinoro, Italy, 2008, pp. 259\u2013272.","DOI":"10.1007\/978-3-540-68891-4_18"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1002\/net.20031"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"J. K\u00f6nemann and R. Ravi,\n                      Quasi-polynomial time approximation algorithm for low-degree minimum-cost Steiner trees\n                      , in Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science, Springer-Verlag, New York, 2003, pp. 289\u2013301.","DOI":"10.1007\/978-3-540-24597-1_25"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970036917X"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702418048"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416736"},{"key":"R29","unstructured":"L. C. Lau, R. Ravi, and M. Singh,\n                      Iterative Relaxations\n                      , manuscript, 2008."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"L. C. Lau and M. Singh,\n                      Additive approximation for bounded degree survivable network design\n                      , in Proceedings of the 40th ACM Symposium on Theory of Computing, ACM, New York, 2008, pp. 759\u2013768.","DOI":"10.1145\/1374376.1374485"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"L. Lewin-Eytan, J. Naor, A. Orda, and M. Singh,\n                      Maximum-Lifetime Routing in Wireless Networks: System Optimization & Game-Theoretic Perspectives\n                      , manuscript, 2007.","DOI":"10.1145\/1288107.1288130"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1002\/net.20005"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrants, and H .B. Hunt,\n                      Many birds with one stone: Multi-objective approximation algorithms\n                      , in Proceedings of the 25th ACM Symposium on Theory of Computing, ACM, New York, 1993, pp. 438\u2013447.","DOI":"10.1145\/167088.167209"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194266331"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0038-2"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"R. Ravi, B. Raghavachari, and P. Klein,\n                      Approximation through local optimality: Designing networks with small degree\n                      , in Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Comput. Sci. 652, Springer-Verlag, Berlin, 1992, pp. 279\u2013290.","DOI":"10.1007\/3-540-56287-7_112"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"R. Ravi and M. Singh,\n                      Delegate and conquer: An LP-based approximation algorithm for minimum degree MSTs\n                      , in Proceedings of ICALP 2006, Venice, Italy, 2006, pp. 169\u2013180.","DOI":"10.1007\/11786986_16"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"M. Safari and M. R. Salavatipour,\n                      \n                        A constant factor approximation for minimum $\\lambda$-edge-connected\n                        k\n                        -subgraph with metric costs\n                      \n                      , in Proceedings of APPROX 2008, Boston, MA, 2008, pp. 233\u2013246.","DOI":"10.1007\/978-3-540-85363-3_19"},{"key":"R40","unstructured":"A. Schrijver,\n                      Combinatorial Optimization\u2014Polyhedra and Efficiency\n                      , Springer-Verlag, New York, 2005."},{"key":"R41","unstructured":"P. D. Seymour,\n                      Sums of Circuits\n                      , in Graph Theory and Related Topics, (Waterloo, Ontario, 1977), Academic Press, New York, 1979, pp. 341\u2013355."},{"key":"R42","doi-asserted-by":"crossref","unstructured":"M. Singh and L. C. Lau,\n                      Approximating minimum bounded degree spanning trees to within one of optimal\n                      , in Proceedings of the 39th ACM Symposium on Theory of Computng, ACM, New York, 2007, pp. 661\u2013670.","DOI":"10.1145\/1250790.1250887"},{"key":"R43","unstructured":"V. Vazirani,\n                      Approximation Algorithms\n                      , Springer-Verlag, New York, 2001."},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070307"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070700620","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:06Z","timestamp":1787337186000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070700620"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/070700620"],"URL":"https:\/\/doi.org\/10.1137\/070700620","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}