In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, an edge cover of a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 is a set of edges such that every vertex of the graph is incident to at least one edge of the set.
In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem

Optimization problem

In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...

 that belongs to the class of covering problem

Covering problem

In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that....

s and can be solved in polynomial time.

Definition

Formally, an edge cover of a graph G is a set of edges C such that each vertex 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.

A minimum edge covering is an edge covering of smallest possible size. The edge covering number is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings.

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 each vertex is incident with exactly one edge in M. A perfect matching is always a minimum edge covering.

Examples

• The set of all edges is an edge cover, assuming that there are no degree-0 vertices.

• The complete bipartite graph
  Complete bipartite graph
  In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
  
   K_m,n has edge covering number max(m, n).

Algorithms

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. 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

Vertex cover

In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....

 is an NP-hard

NP-hard

NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

 problem.

See also

• Vertex cover
  Vertex cover
  In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
  
  
• Set cover – the edge cover problem is a special case of the set cover problem: the elements of the universe are vertices, and each subset covers exactly two elements.