Approximating node-connectivity augmentation problems

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


We consider the (undirected) Node Connectivity Augmentation (NCA) problem: Given a graph J = (V ,EJ ) and connectivity requirements {r(u,v) : U, v ε V }, find a minimum size set I of new edges (any edge is allowed) such that the graph J I contains r(u,v) internally-disjoint uv-paths, for all u, v ε V . In Rooted NCA there is s ε V such that r(u,v) > 0 implies u ε s or v = s. For large values of k = maxu,v?V r(u,v), NCA is at least as hard to approximate as Label-Cover and thus it is unlikely to admit an approximation ratio polylogarithmic in k. Rooted NCA is at least as hard to approximate as Hitting-Set. The previously best approximation ratios for the problem were O(k ln n) for NCA and O(ln n) for Rooted NCA. In this paper we give an approximation algorithm with ratios O(k ln 2 k) for NCA and O(ln 2 k) for Rooted NCA. This is the first approximation algorithm with ratio independent of n, and thus is a constant for any fixed k. Our algorithm is based on the following new structural result which is of independent interest. If D is a set of node pairs in a graph J , then the maximum degree in the hypergraph formed by the inclusion minimal tight sets separating at least one pair in D is O(l 2), where l is the maximum connectivity in J of a pair in D.

שפה מקוריתאנגלית
עמודים (מ-עד)398-410
מספר עמודים13
כתב עתAlgorithmica
מספר גיליון1-2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יוני 2012

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating node-connectivity augmentation problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי