Node-connectivity

Problems in this category

• Characterization of graphs having a k-connected orientation
• Decomposing rooted (k,l)-connected graphs into rooted k-connected parts
• Highly element-connected orientation
• Independent trees
• Maximum square-free 2-matching
• S-T edge-connectivity augmentation
• Undirected node-connectivity augmentation

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 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 , or augmenting connectivity by one .