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.
