2019/10/16 by Chandra Chekuri, Chekuri, Chandra, Alina Ene +3
Computer Science · Materials Science · #Advanced Graph Theory Research #Carbon and Quantum Dots Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1910.07616
openalex publication_date 2019/10/16 · openalex created_date 2022/07/19 · openalex updated_date 2026/07/28
We consider node-weighted survivable network design (SNDP) in planar graphs\nand minor-closed families of graphs. The input consists of a node-weighted\nundirected graph G=(V,E) and integer connectivity requirements r(uv) for\neach unordered pair of nodes uv. The goal is to find a minimum weighted\nsubgraph H of G such that H contains r(uv) disjoint paths between u\nand v for each node pair uv. Three versions of the problem are\nedge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP) and\nvertex-connectivity SNDP (VC-SNDP) depending on whether the paths are required\nto be edge, element or vertex disjoint respectively. Our main result is an\nO(k)-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph\nis planar or more generally if it belongs to a proper minor-closed family of\ngraphs; here k=\maxuv r(uv) is the maximum connectivity requirement. This\nimproves upon the O(k \log n)-approximation known for node-weighted EC-SNDP\nand Elem-SNDP in general graphs [Nutov, TALG'12]. We also obtain an O(1)\napproximation for node-weighted VC-SNDP when the connectivity requirements are\nin 0,1,2 ; for higher connectivity our result for Elem-SNDP can be used in\na black-box fashion to obtain a logarithmic factor improvement over currently\nknown general graph results. Our results are inspired by, and generalize, the\nwork of [Demaine, Hajiaghayi and Klein, TALG'14] who obtained constant factor\napproximations for node-weighted Steiner tree and Steiner forest problems in\nplanar graphs and proper minor-closed families of graphs via a primal-dual\nalgorithm.\n