Node-connectivity

From Egres Open
Jump to: navigation, search

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

  1. L. A. Végh, A. A. Benczúr, Primal-dual approach for directed vertex connectivity augmentation and generalizations, DOI link, Author link
  2. B. Jackson, T. Jordán, Independence free graphs and vertex connectivity augmentation, DOI link, EGRES Technical Report.
  3. L. A. Végh, Augmenting undirected node-connectivity by one, Proc. 42nd ACM STOC (2010), 563-572, DOI link, EGRES Technical Report.