Undirected node-connectivity augmentation

From Egres Open
Jump to: navigation, search

Given an undirected graph G=(V,E) and a positive integer k, find a minimum cardinality edge set F so that G+F is k-node-connected!


If k is not part of the input but fixed, Jackson and Jordán[1] gave a polynomial algorithm with running time [math]O(n^5 + f(k)n^3)[/math], where f(k) is an exponential function of k. For augmenting connectivity by one, that is, if G is already (k-1)-connected, Végh[2] proved a min-max formula and gave a polynomial algorithm for finding an optimal augmenting edge set. The minimum cardinality of an augmenting edge set is equal to the maximum value of a certain 2-packing-type structure ("grove") of node partitions corresponding to undirected node cuts ("clumps"). As shown by an example in [2], this cannot be directly extended to the general case.

Related conjectures

For k=n-2, the augmentation problem is equivalent to finding a maximum cardinality matching in the complement graph of G, while for k=n-3, the equivalent problem in the complement graph is the Maximum square-free 2-matching problem.


  1. B. Jackson, T. Jordán, Independence free graphs and vertex connectivity augmentation, J. Comb. Theory Ser. B, 94(1) 2005, 31-77, DOI link
  2. 2.0 2.1 L. A. Végh, Augmenting undirected node-connectivity by one, Proc. 42nd ACM STOC (2010), 563-572, DOI link, EGRES Technical Report no. 2009-10