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