Changes
==Connectivity augmentation==
There are four basic connectivity augmentation problems since one may consider both edge- and node-connectivity in both directed and undirected graphs. While optimal ''k''-edge-connectivity augmentation can be solved relatively simply easily based on [[Mader's splitting-off theorem|splitting off-techniques]] both in the directed and undirected case, node-connectivity augmentation is more difficult.
===Directed case===
A min-max formula for directed ''k''-node-connectivity follows from the [[Frank-Jordán theorem]]. Along with the theorem, Frank and Jordán gave an algorithm based on the ellipsoid method, which is neither combinatorial nor strongly polynomial. Benczúr and Végh<ref>L. A. Végh, A. A. Benczúr, ''Primal-dual approach for directed vertex connectivity augmentation and generalizations'', [http://doi.acm.org/10.1145/1361192.1361197 DOI link], [http://www.cs.elte.hu/~veghal/benczur-vegh-08.pdf Author link]<name="BeVe"/ref> developed a pseudopolynomial combinatorial algorithm, that is, the running time is a functionof the maximum value of the requirement function ''p''. It remains an important open problem to find a strongly polynomial, or at least, a polynomial algorithm for the Frank-Jordán theorem.
Note that, for node-connectivity augmentation, the connectivity requirement ''k'' cannot exceed ''n'' and hence the running time can be bounded by a polynomial of ''n''. However, [[S-T edge-connectivity augmentation]] is another natural special case of the Frank-Jordán theorem where the input value ''k'' may be arbitrarly large, independently from ''n''.
===Undirected case===
As the last one among of the four basic problems, the complexity status of [[undirected node-connectivity augmentation]] is yet still open. However, many partial result are known, including an algorithm for finding the optimum for fixed ''k'' <ref>B. Jackson, T. Jordán, ''Independence free graphs and vertex connectivity augmentation'', [http:name="JaJo"//dx.doi.org/10.1016/j.jctb.2004.01.004 DOI link], [http://www.cs.elte.hu/egres/tr/egres-01-04.pdf EGRES Technical Report].</ref>, or augmenting connectivity by one <ref>L. A. Végh, ''Augmenting undirected node-connectivity by one'', Proc. 42nd ACM STOC (2010), 563-572, [http:name="Ve1"//doi.acm.org/10.1145/1806689.1806767 DOI link], [http://www.cs.elte.hu/egres/tr/egres-09-10.pdf EGRES Technical Report].</ref>.
==References==
<references> <ref name="BeVe">L. A. Végh, A. A. Benczúr, ''Primal-dual approach for directed vertex connectivity augmentation and generalizations'', [http://doi.acm.org/10.1145/1361192.1361197 DOI link], [http://www.cs.elte.hu/~veghal/benczur-vegh-08.pdf Author link]</ref> <ref name="JaJo">B. Jackson, T. Jordán, ''Independence free graphs and vertex connectivity augmentation'', [http://dx.doi.org/10.1016/j.jctb.2004.01.004 DOI link], [http://www.cs.elte.hu/egres/tr/egres-01-04.pdf EGRES Technical Report].</ref> <ref name="Ve1">L. A. Végh, ''Augmenting undirected node-connectivity by one'', Proc. 42nd ACM STOC (2010), 563-572, [http://doi.acm.org/10.1145/1806689.1806767 DOI link], [http://www.cs.elte.hu/egres/tr/egres-09-10.pdf EGRES Technical Report].</ref> </references>
[[Category:Surveys]]
