Node-connectivity
Contents
Problems in this category
Introduction
Node-connectivity is a fundamental concept in both undirected and directed graphs. By versions of Menger's theorem, deciding whether a graph is k-node-connected is as simple as for edge-connectivity. Many questions can be posed for both edge- and node-connectivity; however, in several cases the node-connectivity version turns out to be significantly harder. On this page we will survey some open problems in certain fields related to node-connectivity, far from being comprehensive.
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 easily based on 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[1] developed a pseudopolynomial combinatorial algorithm, that is, the running time is a function of the maximum value of the requirement function p. It remains an important open problem to find a strongly 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 still open. However, many partial result are known, including an algorithm for finding the optimum for fixed k [2], or augmenting connectivity by one [3].
References
- ↑ L. A. Végh, A. A. Benczúr, Primal-dual approach for directed vertex connectivity augmentation and generalizations, DOI link, Author link
- ↑ B. Jackson, T. Jordán, Independence free graphs and vertex connectivity augmentation, DOI link, EGRES Technical Report.
- ↑ L. A. Végh, Augmenting undirected node-connectivity by one, Proc. 42nd ACM STOC (2010), 563-572, DOI link, EGRES Technical Report.
