# Undirected node-connectivity augmentation

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!

## Remarks

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.

## References

- ↑ 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.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