Edge-Connectivity Augmentation of Simple Graphs
Kasper Skov Johansen, Eva Rotenberg, Carsten Thomassen · SIAM Journal on Discrete Mathematics · 2025
Abstract. We consider the following variant of the edge-augmentation problem: Given a [Formula: see text]-edge-connected graph with no loops or multiple edges, find a smallest edge set in the complement whose addition to [Formula: see text] results in a [Formula: see text]-edge-connected graph. We establish the following dichotomy for this problem: If the complement of [Formula: see text] contains a matching covering all vertices of [Formula: see text]-degree [Formula: see text] (and possibly more), then the complement also contains a matching whose addition to [Formula: see text] results in a [Formula: see text]-edge-connected graph. A smallest matching which augments the minimum degree can be found, in polynomial time, by Edmonds’ matching algorithm, but it need not augment the edge-connectivity. Indeed, it is NP-hard to find a smallest edge-connectivity augmenting edge set, by a result of Tibor Jordán. On the other hand, if the complement of [Formula: see text] contains no matching covering all vertices of [Formula: see text]-degree [Formula: see text], then the complement has a minimum degree augmenting path system consisting of paths of length 1 or 2. Again we can find such a path system with as few edges as possible by Edmonds’ matching algorithm. We can, in polynomial time, modify it to an edge-connectivity augmenting path system of paths of length 1 or 2 with the same number of edges, and this time it yields a smallest edge-connectivity augmenting set of edges. Combining these results, we conclude that a smallest edge-connectivity augmenting edge set in the complement of a [Formula: see text]-regular, [Formula: see text]-edge-connected simple graph has size [Formula: see text], where [Formula: see text] is the number of vertices of [Formula: see text], and [Formula: see text] is the size of a maximum matching in the complement of [Formula: see text]. Another corollary is that the complement of every simple noncomplete graph [Formula: see text] with [Formula: see text] vertices has a set of at most [Formula: see text] edges whose addition to [Formula: see text] results in a graph of larger edge-connectivity, with equality holding if and only the complement of [Formula: see text] is a disjoint union of 3-cycles.