Edge-connectivity

Problems in this category

• Acyclic orientation with connectivity prescriptions
• Constructive characterization of dumpy graphs
• Covering a crossing supermodular function with graph edges
• Covering a crossing supermodular function with pairwise non-parallel arcs
• Covering a symmetric crossing supermodular function with hyperedges of prescribed size
• Disjoint spanning in- and out-arborescences
• Disjoint strongly connected spanning subgraphs
• Edge-disjoint T-connectors
• Edge-independent spanning trees
• Goddyn's conjecture on thin spanning trees
• Incomplete splitting-off in digraphs
• Kriesell's conjecture
• Local edge-connectivity augmentation of a hypergraph with fixed rank
• Minimum k-way cut in a hypergraph
• Parity constrained strongly connected orientations
• Rank-respecting augmentation of hypergraphs with negamodular constraints
• Red-blue cut problem
• Smooth well-balanced orientations with prescribed in-degrees
• Sparsifier subgraphs
• Well-balanced orientations of hypergraphs
• Woodall's conjecture

Introduction

The notion of edge-connectivity can be defined both in undirected and in directed structures (graphs or hypergraphs). An important starting point of the investigations on edge-connectivity is Menger's theorem with its many versions. Here we survey some related results and open problems.

Undirected structures

Edge-connectivity augmentation

Edge-connectivity augmentation is the following problem: given a directed or undirected graph or hypergraph [math]G_0=(V,\mathcal{E}_0)[/math] and some edge-connectivity requirements, add an optimal set of new edges or hyperedges [math]G=(V,\mathcal{E})[/math] to [math]G_0[/math] in order to satisfy these requirements. In this section the new (hyper)edges in [math]\mathcal{E}[/math] are assumed to be undirected. The requirements can be given for example between node-pairs, or more generally between node-sets. Optimality can also be defined in many ways. See a survey in or in . There are many variants, some of which are detailed below.

An abstract framework of edge-connectivity augmentation is the problem of covering a set function by edges or hyperedges. A general class of set functions arising in edge-connectivity augmentation problems is the class of skew-supermodular functions. A more restricted class is crossing supermodular functions. The latter is a common framework of global edge-connectivity augmentation problems.

Global edge-connectivity augmentation

In the global edge-connectivity augmentation problem, [math]G_0[/math] is an undirected (hyper)graph and the edge-connectivity requirement is as follows: given a positive integer k, find a (hyper)graph G such that [math]G_0+G[/math] is k-edge-connected. There are many versions depending on the allowed hyperedge-sizes in [math]G_0[/math] and [math]G[/math], and on the objective function. The first problem in this category was solved by Watanabe and Nakamura ([math]G_0[/math] and [math]G[/math] are both graphs, the objective is to minimize the number of edges in G).

The problem of covering a symmetric crossing supermodular function with a minimum number of graph edges (which is an abstract version of global edge-connectivity augmentation problems) was solved by Benczúr and Frank . The possible generalization to non-symmetric functions is posed as an open problem (more details):

Given a crossing supermodular function [math]p:2^V\to \mathbb{Z}[/math] satisfying [math]p(\emptyset)=p(V)=0[/math], what is the minimum number of edges of an undirected graph G covering p (that is, with the property that [math]d_G(X)\ge p(X)[/math] holds for every [math]X\subseteq V[/math])?

Tamás Király generalized the result of Benczúr and Frank in another direction when he solved the problem of covering a symmetric crossing supermodular function with a minimum number of uniform hyperedges in . However, the following question is open (more details).

Given a symmetric crossing supermodular function [math]p:2^V\to \mathbb{R}[/math] and positive integers [math]n_1,n_2,\dots,n_k[/math], does there exist a hypergraph H=(V,E) covering p and having exactly k hyperedges of sizes [math]n_1,n_2,\dots,n_k[/math]?

Local edge-connectivity augmentation

In this problem the edge-connectivity requirement is a local edge-connectivity requirement. The general problem is the following.

Given a hypergraph [math]G_0=(V,\mathcal{E}_0)[/math] and a symmetric function [math]r:V\times V\to \mathbb{Z}_+[/math], find a hypergraph [math]G=(V,\mathcal{E})[/math] of minimum total size such that [math]\lambda_{G_0+G}(x,y)\ge r(x,y)[/math] for every [math]x,y\in V[/math].

The fundamental result here is due to Frank : he solved this problem if [math]G_0[/math] and [math]G[/math] are both graphs. The problem when there is no restriction on the rank of [math]G_0 [/math] and [math]G[/math] was solved by Szigeti . If we prescribe that the rank of [math]G[/math] should not exceed the rank of [math]G_0[/math], then the problem was solved first by Ben Cosh (see a simplified treatment in ). If we require that [math]G[/math] must be a graph (but we do not restrict the rank of [math]G_0[/math]) then the problem becomes NP-complete: this was observed by Ben Cosh et al . However, the following problem is open, even for [math]k=4[/math] (more details).

We are given a hypergraph [math]G_0=(V,\mathcal{E}_0)[/math] of rank at most [math]k[/math] (where [math]k[/math] is fixed, not part of the input) and a symmetric function [math]r:V\times V\to \mathbb{Z}_+[/math]. Can we find in polynomial time a graph [math]G=(V,{E})[/math] with a minimum number of edges such that [math]\lambda_{G_0+G}(x,y)\ge r(x,y)[/math] for every [math]x,y\in V[/math]?

Node-to-area edge-connectivity augmentation

In this set of problems the requirements are between nodes and node-sets. The motivation is the following: given a computer network, we are at a node and we want to use some service (e.g. download a big file). We are able to do this if we are connected with at least one of the servers of this service (i.e. the mirrors where this file can be found). For every such service i we want to assure that the network is robust against [math]k_i[/math] edge-failures.

Let us consider the following general problem.

General node-to-area edge-connectivity augmentation problem: given an undirected hypergraph [math]G_0=(V,\mathcal{E}_0)[/math], a family of sets (called areas) [math]\mathcal{W}\subseteq 2^V[/math] and a requirement function [math]r:\mathcal{W}\to \mathbb{Z}_+[/math], find a hypergraph [math]G=(V,\mathcal{E})[/math] of minimum total size such that [math] \lambda_{H_0+H}(x,W)\ge r(W) [/math] for every [math]x\in V,W\in \mathcal{W}[/math].

First assume that [math]G_0[/math] and [math]G[/math] are both graphs. This problem in this case was first considered by Miwa and Ito. They observed that the problem is NP-complete even if [math]G_0[/math] is the empty graph and [math]r(W)=1[/math] for every [math]W\in \mathcal{W}[/math]. However, they could solve it in polynomial time if [math]r(W)=2[/math] for every [math]W\in \mathcal{W}[/math]. This was later generalized by Ishii et al. : they showed that the problem can be solved in polynomial time if [math]r(W)=k[/math] for every [math]W\in \mathcal{W}[/math] for some positive integer k>1. The most surprising result in this topic is that of Ishii and Hagiwara who observed that the problem is solvable in polynomial time in the following more general case, too: [math]G_0[/math] and [math]G[/math] are both graphs and [math]r(W)\gt1[/math] for every [math]W\in \mathcal{W}[/math].

Next assume that [math]G_0[/math] and [math]G[/math] both can be hypergraphs. Then the problem is a special case of covering a symmetric skew-supermodular function with hyperedges of minimum total size solved by Szigeti . Here we don't need the assumption that [math]r\gt1[/math]. Another problem raised in Bernáth and Király is the following: we also require that the rank of [math]G[/math] should not exceed the rank of [math]G_0[/math]. This contains the problem for graphs detailed above, therefore we need the assumption that [math]r(W)\gt1[/math] for every [math]W\in \mathcal{W}[/math]. The following, more general version is considered in (see also).

Given a crossing negamodular function [math]R:2^V\to \mathbb{Z}[/math] such that [math]R(X)\ne 1[/math] for every [math]X\subseteq V[/math] and a hypergraph [math]G_0=(V,\mathcal{E}_0)[/math], find a hypergraph [math]G=(V,\mathcal{E})[/math] of minimum total size such that [math]d_G(X)\ge R(X)-d_{G_0}(X)[/math] holds for every [math]X\subseteq V[/math] and the rank of [math]G[/math] does not exceed the rank of [math]G_0[/math].

This is indeed a generalization of the problem from above: set [math]R(X)=\max\{r(W):W \cap X= \emptyset, W\in \mathcal W\}[/math]. This problem was solved in if the rank of [math]G_0[/math] is at least 3, and remained open if it is 2. However (even the solved cases of) this problem raises algorithmic difficulties if the function [math]R[/math] is given with a function evaluation oracle: in the algorithms we need a more general, so called maximizing oracle (see details in ) . The problem is the following (see also).

Given a skew-supermodular function [math]p:2^V\to \mathbb{Z}[/math] with a function evaluation oracle, is it possible to find a set [math]X\subseteq V[/math] in polynomial time such that [math]p(X)=\max\{p(Y): Y\subseteq V\}[/math]? The problem is open even if [math]p[/math] is a crossing negamodular function.

Another generalization of the node-to-area edge-connectivity augmentation is the area-to-area edge-connectivity augmentation. This is introduced and investigated in , where approximation algorithms and inapproximability results can be found.

Directed structures

Splitting-off

The directed splitting-off operation is a useful tool for solving problems concerning directed graphs, e.g. in inductive proofs or in arc-connectivity augmentation. The main tool is Mader's Directed Splitting-off Theorem. One extension of Mader's theorem, due to András Frank, says that if [math]\delta_D(s)\le \varrho_D(s)\lt 2\delta_D(s)[/math] for a digraph D=(V+s,A) which is k-arc-connected in V, then there still exists an incoming and an outgoing arc incident to s that can be split off without destroying the k-arc-connectivity in V. This motivates the following question (see also).

Given a digraph D=(V+s,A) which is k-arc-connected in V, what is the maximum number of (disjoint) pairs of arcs, consisting of entering and leaving arcs at [math]s[/math], whose (simultaneous) splitting off does not destroy the k-arc-connectivity of D in V?

Disjoint subdigraphs

There are many conjectures about the existence of disjoint subgraphs in a digraph under some arc-connectivity assumption. The first, due to Kriesell, is about Disjoint Steiner-trees:

Let G=(V,E) be a graph, and [math]T \subseteq V[/math]. Is it true that if T is 2k-edge-connected in G (i.e. there are 2k edge-disjoint paths between any two nodes of T), then G contains k edge-disjoint Steiner trees for T?

Another conjecture on disjoint spanning in- and out-arborescences is the following:

Does there exist a value k so that in every k-arc-connected directed graph D=(V,A) and for every node [math]v\in V[/math], there is a spanning in-arborescence and a disjoint spanning out-arborescence rooted in v?

A stronger version of this conjecture on Disjoint strongly connected spanning subgraphs is the following:

Does there exist a value k so that every k-arc-connected directed graph contains a pair of arc-disjoint strongly connected spanning sub-digraphs?

Orientations with edge-connectivity requirements

There is a separate page on orientations, see the section on orientations with edge-connectivity requirements there.