K-edge-connected graph

Last updated December 26, 2023

In graph theory, a connected graph is $k$ -edge-connected if it remains connected whenever fewer than $k$ edges are removed.

Formal definition

Let $G=(V,E)$ be an arbitrary graph. If the subgraph $G'=(V,E\setminus X)$ is connected for all $X\subseteq E$ where $|X|<k$ , then G is said to be k-edge-connected. The edge connectivity of $G$ is the maximum value k such that G is k-edge-connected. The smallest set X whose removal disconnects G is a minimum cut in G.

The edge connectivity version of Menger's theorem provides an alternative and equivalent characterization, in terms of edge-disjoint paths in the graph. If and only if every two vertices of G form the endpoints of k paths, no two of which share an edge with each other, then G is k-edge-connected. In one direction this is easy: if a system of paths like this exists, then every set X of fewer than k edges is disjoint from at least one of the paths, and the pair of vertices remains connected to each other even after X is deleted. In the other direction, the existence of a system of paths for each pair of vertices in a graph that cannot be disconnected by the removal of few edges can be proven using the max-flow min-cut theorem from the theory of network flows.

Related concepts

Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph $G=(V,E)$ is k-edge-connected then it is necessary that k ≤ δ(G), where δ(G) is the minimum degree of any vertex v ∈ V. Deleting all edges incident to a vertex v would disconnect v from the graph.

Edge connectivity is the dual concept to girth, the length of the shortest cycle in a graph, in the sense that the girth of a planar graph is the edge connectivity of its dual graph, and vice versa. These concepts are unified in matroid theory by the girth of a matroid, the size of the smallest dependent set in the matroid. For a graphic matroid, the matroid girth equals the girth of the underlying graph, while for a co-graphic matroid it equals the edge connectivity.^[2]

The 2-edge-connected graphs can also be characterized by the absence of bridges, by the existence of an ear decomposition, or by Robbins' theorem according to which these are exactly the graphs that have a strong orientation.^[3]

Computational aspects

There is a polynomial-time algorithm to determine the largest k for which a graph G is k-edge-connected. A simple algorithm would, for every pair (u,v), determine the maximum flow from u to v with the capacity of all edges in G set to 1 for both directions. A graph is k-edge-connected if and only if the maximum flow from u to v is at least k for any pair (u,v), so k is the least u-v-flow among all (u,v).

If n is the number of vertices in the graph, this simple algorithm would perform $O(n^{2})$ iterations of the Maximum flow problem, which can be solved in $O(n^{3})$ time. Hence the complexity of the simple algorithm described above is $O(n^{5})$ in total.

An improved algorithm will solve the maximum flow problem for every pair (u,v) where u is arbitrarily fixed while v varies over all vertices. This reduces the complexity to $O(n^{4})$ and is sound since, if a cut of capacity less than k exists, it is bound to separate u from some other vertex. It can be further improved by an algorithm of Gabow that runs in worst case $O(n^{3})$ time. ^[4]

The Karger–Stein variant of Karger's algorithm provides a faster randomized algorithm for determining the connectivity, with expected runtime $O(n^{2}\log ^{3}n)$ .^[5]

A related problem: finding the minimum k-edge-connected spanning subgraph of G (that is: select as few as possible edges in G that your selection is k-edge-connected) is NP-hard for $k\geq 2$ .^[6]

Related Research Articles

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

<span class="mw-page-title-main">Component (graph theory)</span> Maximal subgraph whose vertices can reach each other

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.

In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices. Proved by Karl Menger in 1927, it characterizes the connectivity of a graph. It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs.

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.

In the mathematical discipline of graph theory, the dual graph of a planar graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes, and for sparse random graphs it runs in time with high probability.$

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph $G$ , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

In graph theory, a connected graph $G$ is said to be $k$ -vertex-connected if it has more than $k$ vertices and remains connected whenever fewer than $k$ vertices are removed.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

<span class="mw-page-title-main">Ear decomposition</span> Partition of graph into sequence of paths

In graph theory, an ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in G. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An open ear decomposition or a proper ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other.

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

References

↑ Jordan, Camille (1869). "Sur les assemblages de lignes". Journal für die reine und angewandte Mathematik (in French). 70 (2): 185–190.
↑ Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics, 155 (18): 2456–2470, doi: 10.1016/j.dam.2007.06.015 , MR 2365057 .
↑ Robbins, H. E. (1939). "A theorem on graphs, with an application to a problem on traffic control". American Mathematical Monthly . 46: 281–283. doi:10.2307/2303897. JSTOR 2303897.
↑ Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259–273, 1995.
↑ Karger, David R.; Stein, Clifford (1996). "A new approach to the minimum cut problem" (PDF). Journal of the ACM. 43 (4): 601. doi:10.1145/234533.234534.
↑ M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Jordan, Camille (1869). "Sur les assemblages de lignes". Journal für die reine und angewandte Mathematik (in French). 70 (2): 185–190.

[2] Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics, 155 (18): 2456–2470, doi: 10.1016/j.dam.2007.06.015 , MR 2365057 .

[3] Robbins, H. E. (1939). "A theorem on graphs, with an application to a problem on traffic control". American Mathematical Monthly . 46: 281–283. doi:10.2307/2303897. JSTOR 2303897.

[4] Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259–273, 1995.

[5] Karger, David R.; Stein, Clifford (1996). "A new approach to the minimum cut problem" (PDF). Journal of the ACM. 43 (4): 601. doi:10.1145/234533.234534.

[6] M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.

[1]

[2]

[3]

[4]

[5]

[6]