Edge cover

Edge coverMain

Community hub

Edge cover

7 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Edge cover

View on Wikipedia

from Wikipedia

In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is an endpoint of at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time.

Covering problems	Packing problems
Minimum set cover	Maximum set packing
Minimum edge cover	Maximum matching
Minimum vertex cover	Maximum independent set
Bin covering	Bin packing
Polygon covering	Rectangle packing

Definition

[edit]

Formally, an edge cover of a graph $G$ is a set of edges $C$ such that each vertex in $G$ is incident with at least one edge in $C$ . The set $C$ is said to cover the vertices of $G$ . The following figure shows examples of edge coverings in two graphs (the set $C$ is marked with red).

A minimum edge covering is an edge covering of smallest possible size. The edge covering number $ρ (G)$ is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings (again, the set $C$ is marked with red).

Note that the figure on the right is not only an edge cover but also a matching. In particular, it is a perfect matching: a matching $M$ in which every vertex is incident with exactly one edge in $M$ . A perfect matching (if it exists) is always a minimum edge covering.

Examples

[edit]

The set of all edges is an edge cover, assuming that there are no degree-0 vertices.
The complete bipartite graph $K m,n$ has edge covering number $max(m, n)$ .

Algorithms

[edit]

A smallest edge cover can be found in polynomial time by finding a maximum matching and extending it greedily so that all vertices are covered.^[1]^[2] In the following figure, a maximum matching is marked with red; the extra edges that were added to cover unmatched nodes are marked with blue. (The figure on the right shows a graph in which a maximum matching is a perfect matching; hence it already covers all vertices and no extra edges were needed.)

On the other hand, the related problem of finding a smallest vertex cover is an NP-hard problem.^[1]

Looking at the image it already becomes obvious why, for a given minimum edge cover $C$ and maximum matching $M$ , letting $c$ and $m$ be the number of edges in $C$ and $M$ respectively, we have:^[3] $|V|=c+m$ . Indeed, $C$ contains a maximum matching, so the edges of $C$ can be decomposed between the $m$ edges of a maximum matching, covering $2m$ vertices, and the $c-m$ other edges that each cover one other vertex. Thus, as $C$ covers all of the $|V|$ vertices, we have $|V|=2m+(c-m)$ giving the desired equality.

Notes

[edit]

^ ^a ^b Garey & Johnson (1979), p. 79, uses edge cover and vertex cover as one example of a pair of similar problems, one of which can be solved in polynomial time while the other one is NP-hard. See also p. 190.
^ Lawler, Eugene L. (2001), Combinatorial optimization: networks and matroids, Dover Publications, pp. 222–223, ISBN 978-0-486-41453-9.
^ "Prove that the sum of minimum edge cover and maximum matching is the vertex count". Mathematics Stack Exchange. Retrieved 2024-02-18.

References

[edit]

Weisstein, Eric W. "Edge Cover". MathWorld.
Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5.

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

In graph theory, an edge cover of an undirected graph

G = (V, E)

is a subset

C \subseteq E

of edges such that every vertex in

V

is incident to at least one edge in

C

.^[1] This concept is dual to that of a vertex cover, where vertices rather than edges are selected to "cover" all edges of the graph.^[2] The minimum edge cover is the edge cover of smallest cardinality, and its size, denoted

\rho(G)

, plays a central role in matching theory.^[3] For a graph

G

with no isolated vertices, Gallai's identities establish that

\rho(G) = |V| - \nu(G)

, where

\nu(G)

is the size of a maximum matching in

G

.^[4] This relation implies that a minimum edge cover can be constructed by taking a maximum matching and adding, for each unmatched vertex, an arbitrary incident edge; the resulting set has the minimal size.^[5] Finding a minimum edge cover is computationally tractable, as it reduces to computing a maximum matching, which can be solved in polynomial time using algorithms such as the Blossom algorithm for general graphs or Hopcroft-Karp for bipartite graphs.^[4] Edge covers have been generalized to weighted, directed, and temporal graphs, where optimization problems like minimum weighted edge cover arise in applications such as resource allocation and network design.^[6] Variants, including total edge covers (which exclude isolated edges) and bounded-degree edge covers, introduce additional constraints and are studied for their structural properties in extremal graph theory.^[7]

Definition and Properties

Formal Definition

An undirected graph

G = (V, E)

consists of a finite set

V

of vertices and a set

E

of edges, where each edge is an unordered pair of distinct vertices from

V

. A vertex

v \in V

is incident to an edge

e \in E

v

is one of the endpoints of

e

. An edge cover of an undirected graph

G = (V, E)

is a subset

C \subseteq E

such that every vertex

v \in V

is incident to at least one edge in

C

. Graphs containing isolated vertices (vertices with degree zero) admit no edge cover, as an isolated vertex cannot be incident to any edge. In graphs without isolated vertices, edge covers always exist; the full edge set

E

serves as a trivial edge cover. The size of a minimum edge cover of

G

is called the edge covering number and is denoted by

\rho(G)

. This concept is related to but distinct from a maximum matching, which is a set of edges with no two sharing a vertex.

Key Properties

An edge cover of a graph is minimal if no proper subset of its edges forms an edge cover, meaning the removal of any single edge leaves at least one vertex uncovered. This property ensures that each edge in the set is essential for covering some vertex that would otherwise remain isolated in the subgraph formed by the remaining edges. Minimal edge covers differ from minimum edge covers in that the former emphasize irreducibility under subset removal, while the latter focus on achieving the smallest possible cardinality; every minimum edge cover is minimal, but not every minimal edge cover is minimum.^[8]^[9] Every edge cover contains at least one minimal edge cover as a subset, obtained by iteratively removing redundant edges until no further removal is possible without violating the covering property; since the graph is finite, this process terminates. The union of any two edge covers is also an edge cover, as every vertex incident to an edge in either set remains covered in the combined set.^[8]^[10] For any edge cover

C

in a graph

G = (V, E)

with

|V| = n

vertices, the cardinality satisfies

|C| \geq \lceil n/2 \rceil

. The bound

\lceil n/2 \rceil

follows from the pigeonhole principle: each edge in

C

is incident to at most two vertices, so at least

\lceil n/2 \rceil

edges are required to cover all

n

vertices, with equality possible in graphs admitting a perfect matching. Edge covers exist in a graph if and only if the graph has no isolated vertices, as an isolated vertex cannot be incident to any edge and thus cannot be covered. The edges of an edge cover induce a spanning subgraph of the original graph in which the minimum degree is at least 1, since every vertex is incident to at least one selected edge by definition.^[10]

Illustrative Examples

To illustrate the concept of an edge cover, consider simple graphs without isolated vertices, where an edge cover is a set of edges incident to every vertex.^[9] In the path graph

P_3

with vertices labeled 1, 2, 3 and edges {1-2, 2-3}, the set {1-2, 2-3} forms a minimum edge cover of size 2.^[11] However, the single edge {1-2} is not an edge cover, as vertex 3 has no incident edge in the set.^[9] For the cycle graph

C_4

with vertices 1, 2, 3, 4 and edges {1-2, 2-3, 3-4, 4-1}, a minimum edge cover consists of any two non-adjacent edges, such as {1-2, 3-4}, while the full set of four edges is an edge cover but not minimal. In the complete graph

K_3

with vertices 1, 2, 3 and all three possible edges, any two edges form a minimum edge cover. By Gallai's identity, the edge covering number equals the number of vertices minus the matching number (which is 1 for

K_3

), yielding size 2. The complete bipartite graph

K_{2,3}

has partitions of sizes 2 and 3, with edge covering number 3 (the maximum partition size). This follows from Gallai's identity, as the maximum matching size is 2 and the graph has 5 vertices. As a non-example, a graph consisting of a single isolated vertex has no edge cover, since no edges exist to incident to the vertex.^[9]

Minimum Edge Cover

Edge Cover Number

The edge cover number of a graph

G

, denoted

\rho(G)

, is the cardinality of a minimum edge cover in

G

, that is, the smallest number of edges whose union covers all vertices of

G

.^[12]^[13] This parameter is defined only for graphs without isolated vertices, as isolated vertices cannot be covered by any edge. Trivially,

\rho(G) \leq |E(G)|

, since the full edge set is an edge cover.^[13] For a graph

G

with

n = |V(G)|

vertices,

\rho(G) \geq \lceil n/2 \rceil

. This lower bound arises because each edge in an edge cover can incident at most two vertices, so at least

\lceil n/2 \rceil

edges are needed to cover all

n

vertices. Equality holds if and only if

\nu(G) = \lfloor n/2 \rfloor

, i.e.,

G

has a maximum matching covering all vertices (perfect matching) when

n

is even or all but one vertex when

n

is odd. In the even case, a maximum matching serves as a minimum edge cover of size

n/2

.^[13]^[3] In any graph

G

without isolated vertices, the edge cover number satisfies the Gallai identity

\rho(G) + \nu(G) = n

, where

\nu(G)

is the matching number (size of a maximum matching).^[12]^[13]^[3] This equality provides a computation-independent characterization:

\rho(G) = n - \nu(G)

. For example, in a cycle graph

C_4

(which has a perfect matching),

\nu(C_4) = 2

and

\rho(C_4) = 2

; in a path graph

P_3

\nu(P_3) = 1

and

\rho(P_3) = 2 = \lceil 3/2 \rceil

.^[13]

Relation to Matchings

In any graph

G

without isolated vertices, the edge cover number

\rho(G)

equals the number of vertices minus the matching number

\nu(G)

, that is,

\rho(G) = |V| - \nu(G)

.^[4] This relation, part of the Gallai identities, provides an exact formula for the size of a minimum edge cover in terms of the maximum matching size.^[14] A minimum edge cover can be constructed from a maximum matching

M

by adding, for each unsaturated vertex (one not incident to any edge in

M

), an arbitrary edge incident to that vertex; this process yields an edge cover of size exactly

\rho(G)

.^[15] The added edges ensure all vertices are covered without introducing redundancy beyond the minimum required.^[14] To see why this holds, consider that a maximum matching

M

covers

2\nu(G)

vertices, leaving

|V| - 2\nu(G)

unsaturated vertices, each of which requires at least one additional edge in any edge cover, implying

\rho(G) \geq \nu(G) + (|V| - 2\nu(G)) = |V| - \nu(G)

.^[14] The construction achieves equality by adding precisely one edge per unsaturated vertex, covering them without overlap since the added edges connect to already-covered vertices in

M

.^[4] This connection implies that if

G

has a perfect matching (where

\nu(G) = |V|/2

), then

\rho(G) = |V|/2

, meaning the minimum edge cover coincides with a perfect matching.^[14] More generally, the matching deficiency

|V| - 2\nu(G)

directly determines the excess edges needed beyond the matching size, highlighting how structural gaps in matchings inflate the edge cover size.^[4] The relation was established by Tibor Gallai in 1959 as part of his identities on extremal point and edge sets in graphs.^[4]

Algorithms and Complexity

Computing Minimum Edge Covers

A minimum edge cover in a graph without isolated vertices can be computed efficiently by first obtaining a maximum matching and then extending it to cover all remaining vertices. This approach leverages the structural relation between matchings and edge covers, where the size of a minimum edge cover equals the number of vertices minus the size of a maximum matching, denoted

\rho(G) = |V| - \nu(G)

.^[5] The process begins by computing a maximum matching

M

using Edmonds' blossom algorithm, which finds a maximum cardinality matching in general graphs in polynomial time.^[16] For each vertex unsaturated by

M

, an arbitrary incident edge is added to the set, ensuring every vertex is covered while maintaining minimality.^[5] The algorithm proceeds in the following steps:

Compute a maximum matching $M$ in the graph $G = (V, E)$ .
Identify the set $U \subseteq V$ of unsaturated vertices, i.e., those not incident to any edge in $M$ .
For each $u \in U$ , select an arbitrary incident edge $\{u, v\} \in E$ , where $v$ is saturated (since unsaturated vertices form an independent set).
Form the edge cover $C = M \cup \{\{u, v\} \mid u \in U\}$ ; this $C$ is a minimum edge cover with $|C| = |V| - |M|$ .^[5]

If the graph contains isolated vertices, no edge cover exists, as such vertices cannot be incident to any edge. In practice, algorithms may first detect and report isolated vertices, or preprocess by removing them, though the resulting structure would not constitute a valid edge cover for the original graph.^[17] In implementation, this method integrates seamlessly with established maximum matching solvers in libraries like NetworkX, where the extension step is a simple greedy augmentation over unsaturated vertices. Added edges connect unsaturated vertices exclusively to saturated ones, preventing overlaps or uncovered vertices and guaranteeing the cover's minimality without additional checks.^[15] For illustration, consider the path graph

P_3

on vertices

\{1, 2, 3\}

with edges

\{1,2\}

and

\{2,3\}

. A maximum matching is

M = \{\{1,2\}\}

of size 1, leaving vertex 3 unsaturated. Adding

\{2,3\}

yields

C = \{\{1,2\}, \{2,3\}\}

, a minimum edge cover of size 2, matching

|V| - |M| = 3 - 1

.^[5]

Computational Complexity

The minimum edge cover problem is solvable in polynomial time due to its close relationship with the maximum matching problem. By Gallai's identity, for any graph

G = (V, E)

without isolated vertices, the edge cover number

\rho(G)

satisfies

\rho(G) = |V| - \nu(G)

, where

\nu(G)

is the size of a maximum matching in

G

. Since the maximum matching number

\nu(G)

can be computed in polynomial time, so can

\rho(G)

. The original algorithm for maximum matching, developed by Edmonds, runs in

O(|V|^4)

time.^[18] Subsequent improvements, including an algorithm by Gabow, reduce the time complexity to

O(\sqrt{|V|} |E|)

O(∣V∣

∣E∣).^[19] Further refinements, such as the Micali-Vazirani algorithm, achieve $O(\sqrt{|V|} |E|)$

∣E∣) time, which is $O(|V|^{5/2})$ for dense graphs. In terms of parameterized complexity, the problem is fixed-parameter tractable (FPT) when parameterized by the solution size $\rho(G)$ or by the treewidth of the graph. Parameterization by solution size follows trivially from the polynomial-time solvability, with running time bounded by functions of the parameter times a polynomial in the input size. For treewidth $tw$ , dynamic programming on a tree decomposition yields an FPT algorithm. This contrasts sharply with the minimum vertex cover problem, which is NP-hard in general graphs but also benefits from matching duality in bipartite cases; however, edge cover's direct reduction to maximum matching ensures polynomial-time exact solvability without such restrictions. The decision version—determining whether $\rho(G) \leq k$ for a given integer $k$ —is also in P, as it reduces to computing a maximum matching and verifying if $\nu(G) \geq |V| - k$ . Since an exact polynomial-time algorithm exists, the optimization problem admits a trivial 1-approximation algorithm. For weighted variants, approximation results are discussed in the section on weighted edge covers.

Generalizations and Variants

Weighted Edge Covers

In a graph

G = (V, E)

with non-negative edge weights

w: E \to \mathbb{R}_{\geq 0}

, a weighted edge cover is a subset

C \subseteq E

that covers every vertex in

V

, and its weight is defined as

\sum_{e \in C} w(e)

. The minimum weight edge cover is an edge cover

C

of minimum total weight. The minimum weight edge cover problem can be reduced to the minimum weight perfect matching problem in a modified graph. This reduction allows computing a minimum weight edge cover using algorithms for minimum weight perfect matching, such as variants of the blossom algorithm. If all edge weights are equal to 1, the problem reduces to finding a minimum cardinality edge cover in the unweighted case. For example, consider the complete graph

K_3

on vertices

A, B, C

with edge weights

w(AB) = 1

w(BC) = 2

w(CA) = 3

. The minimum weight edge cover consists of edges

AB

and

BC

, with total weight 3; using

AB

and

CA

gives weight 4, and

BC

and

CA

gives 5, while a single edge covers only two vertices.

Edge Covers in Directed and Hypergraphs

In directed graphs, a directed edge cover is a set of arcs such that every vertex is incident to at least one arc in the set, either as its tail or head. The size of a minimum directed edge cover, denoted ρ^dir(G), is given by ρ^dir(G) = |V| - ν^dir(G), where ν^dir(G) is the size of a maximum matching in G—a matching being a set of vertex-disjoint arcs with no two sharing a head or tail. This formula holds assuming G has no isolated vertices, analogous to the undirected case, as a maximum matching covers 2ν^dir(G) vertices with ν^dir(G) arcs, and the remaining |V| - 2ν^dir(G) vertices can be covered by adding |V| - 2ν^dir(G) additional arcs, each connecting an unmatched vertex to a matched one without leaving new uncovered vertices. To compute ν^dir(G), construct a bipartite graph with partite sets L and R, both copies of V, and an edge from u ∈ L to v ∈ R if there is an arc u → v in G; the size of a maximum bipartite matching in this construction equals ν^dir(G) and can be found in polynomial time using algorithms such as Hopcroft-Karp.^[17]^[20] For example, consider a directed cycle on three vertices with arcs a → b, b → c, and c → a. A maximum matching has size 1 (any single arc), so ρ^dir(G) = 3 - 1 = 2. Indeed, any two arcs form a minimum directed edge cover, as they incident all three vertices, while one arc leaves one vertex uncovered. In hypergraphs, a hyperedge cover is a set of hyperedges such that every vertex is contained in at least one hyperedge in the set; the minimum hyperedge cover problem is equivalent to the set cover problem, with vertices as the universe and hyperedges as sets. This problem is NP-hard, as it is a direct generalization of set cover, which is NP-hard even for instances where sets have size at most 3.^[5] Computing a minimum hyperedge cover is NP-hard in general, but approximation algorithms exist. The greedy algorithm, which iteratively selects the hyperedge covering the most uncovered vertices, achieves an approximation ratio of H_d ≤ ln |V| + 1, where H_d is the d-th harmonic number and d is the maximum hyperedge size; for general hypergraphs, this yields an O(ln |V|)-approximation. This bound is tight, as the greedy algorithm matches the known hardness of approximating set cover within (1 - ε) ln |V| unless NP has quasi-polynomial time algorithms. For uniform hypergraphs, the same greedy approach applies.

Applications

In Combinatorial Optimization

In combinatorial optimization, the minimum edge cover problem can be modeled as a special case of the set cover problem, where the universe consists of the vertex set

V

and each edge

e \in E

corresponds to a set containing the two endpoints of

e

. An edge cover then corresponds to a collection of these sets that covers every element in

V

at least once. This makes edge cover a special case of the set cover problem restricted to sets of size at most two.^[21] The integer programming formulation for the minimum (unweighted) edge cover is given by minimizing

\sum_{e \in E} x_e

subject to

\sum_{e \ni v} x_e \geq 1

for all

v \in V

and

x_e \in \{0,1\}

for all

e \in E

. The linear programming relaxation replaces the integrality constraints with

x_e \geq 0

, and this relaxation has an integrality gap of 1, meaning the LP optimum equals the integer optimum; this follows from the strong duality between minimum edge covers and maximum matchings via Gallai's identity, which states that the size of a minimum edge cover is

|V|

minus the size of a maximum matching.^[22]^[23] The edge cover polytope, defined as the convex hull of the incidence vectors of all edge covers, is integral and can be described by the degree constraints

\sum_{e \ni v} x_e \geq 1

for all

v \in V

along with

0 \leq x_e \leq 1

for all

e \in E

; however, the full facet-defining inequalities include additional constraints of the form

x(E[U] \cup \delta(U)) \geq \lceil |U|/2 \rceil

for odd-sized subsets

U \subseteq V

, ensuring the polytope's integrity.^[23] Historically, the minimum edge cover problem appeared in early optimization texts as an example of a tractable problem in P, contrasting with NP-hard covering problems like vertex cover or set cover to illustrate the P vs. NP distinction.^[24] In the generalization to hypergraphs, where edges may cover more than two vertices, the minimum edge cover reduces to the standard set cover problem and admits an

O(\ln |V|)

-approximation via the greedy algorithm, which iteratively selects the hyperedge covering the most uncovered vertices.

In Network and Resource Allocation

In resource allocation problems, edge covers model scenarios where facilities are represented as vertices and possible assignments as edges, with a minimum edge cover identifying the smallest set of assignments that ensures every facility is utilized. This approach minimizes the number of resources needed while covering all entities, as explored in cooperative game theory frameworks where edge cover games allocate costs fairly among participants. For instance, in cooperative settings, the core of an edge cover game provides stable allocations that prevent coalitions from deviating, computed via star decompositions of the minimum edge cover to approximate fair divisions.^[25] In network design for communication systems, weighted edge covers are applied to minimize infrastructure costs, such as cable usage, while ensuring every node maintains at least one connection, thereby guaranteeing basic connectivity. This is particularly useful in designing robust topologies where the objective is to cover all vertices with edges of minimal total weight, avoiding over-provisioning in sparse networks. Seminal work on network design covering problems employs decomposition techniques to solve variants where partial demands must be met, adapting edge cover principles to balance coverage and cost in telecommunication infrastructures.^[26] Directed edge covers find application in scheduling tasks modeled as directed graphs, where arcs represent dependencies or resource flows, and a minimum directed edge cover ensures every job receives necessary inputs and produces outputs without excess assignments. In dynamic environments, this translates to assigning resources to nodes over time to minimize makespan, with approximation algorithms providing near-optimal schedules for time-sensitive operations. For example, in production scheduling, directed variants prioritize precedence constraints, using edge covers to cover all tasks efficiently.^[27] In bioinformatics, edge covers in protein-protein interaction (PPI) graphs identify minimal sets of interactions that cover all proteins, aiding in the detection of essential complexes or pathways by selecting a smallest subset of edges incident to every vertex. This is crucial for understanding biological networks where not all interactions need activation; quasi-clique-based edge covers extend this to denser substructures, revealing functional modules in PPI data. Research demonstrates that approximating minimum edge covers by quasi-cliques is APX-complete even in restricted cases, yet heuristic solutions effectively pinpoint core interactions in large-scale PPI networks.^[28] In economics, particularly auction theory, edge covers model scenarios where bidders (vertices) must be assigned at least one item (edges) at minimal cost, framing combinatorial auctions as edge cover problems to ensure truthful mechanisms with low frugality ratios. Multi-agent systems use approximation algorithms for edge covers to design auctions that approximate optimal social welfare, balancing bidder coverage and payment efficiency in resource distribution. Influential studies highlight how edge cover auctions achieve constant-factor approximations, influencing mechanism design for spectrum auctions and ad allocations.^[29]^[30] A notable case study from the 2000s involves wireless sensor networks (WSNs), where edge covers optimize connectivity by selecting minimal transmissions to cover all sensors, reducing energy consumption in monitoring applications. Heuristic algorithms based on edge weights approximate minimum edge covers to form clusters that maintain network coverage while minimizing relay overhead, as demonstrated in deployments for environmental sensing. Further advancements approximate minimum-power edge covers to enhance 2-3 connectivity in WSNs, ensuring fault-tolerant topologies with bounded approximation ratios.^[31]^[32]

History

Edge cover

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Edge cover

Definition

Examples

Algorithms

See also

Notes

References

Edge cover

Definition and Properties

Formal Definition

Key Properties

Illustrative Examples

Minimum Edge Cover

Edge Cover Number

Relation to Matchings

Algorithms and Complexity

Computing Minimum Edge Covers

Computational Complexity

Add your contribution

Related Hubs

Contribute something