Introduction

Imagine a map of cities connected by roads. You want to assign a patrol to some roads so that every city has at least one patrolled road leading out of it. Use as few patrols as possible. That is the minimum edge cover problem: choose a set of edges so every vertex is touched by at least one chosen edge, using the fewest edges you can.

It sounds almost identical to a famous hard problem. Vertex cover asks the mirror question: pick the fewest vertices so that every edge is touched. Swap two words — "edge" for "vertex" — and you seem to get the same kind of puzzle.

But the two problems could not be more different in difficulty. Vertex cover is NP-hard: nobody knows a fast algorithm, and finding one would settle P vs NP. Edge cover, its twin, is easy — solvable quickly, every time. This article is about that razor-thin line and why it falls exactly where it does.

Build a Cover

Here is a small graph. Each dot is a vertex, each line is an edge. Click edges to add them to your cover. Your goal: make sure every vertex is touched by at least one selected edge — using as few edges as possible.

<p class="hint">Each dot is a <b>vertex</b>; each line is an <b>edge</b>. Click edges to add them to your cover. The goal: make sure <b>every vertex</b> is touched by at least one selected edge, using as few edges as possible. Then let the computer find the minimum.</p>
<svg id="graph" viewBox="0 0 360 240" aria-label="graph"></svg>
<div class="status" id="status">Click edges to cover every vertex.</div>
<div class="btns">
  <button id="solve" type="button">Solve (minimum)</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#graph { width: 100%; max-width: 420px; height: auto; display: block; margin: 0 auto; }
.edge { stroke: #b9c2cc; stroke-width: 5; cursor: pointer; transition: stroke .12s; }
.edge:hover { stroke: #8a97a6; }
.edge.on { stroke: #1d3557; }
.vtx { fill: #c9ccd1; stroke: #9aa0a8; stroke-width: 1.5; }
.vtx.covered { fill: #2a9d8f; stroke: #1f7a70; }
.vlabel { font: 700 12px ui-monospace, monospace; fill: #fff; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; text-align: center; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; justify-content: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Minimum edge cover: pick the fewest edges so every vertex is touched.
// It is solvable in polynomial time. Recipe (Gallai, 1959):
//   1. find a MAXIMUM MATCHING (edges sharing no vertex),
//   2. for every still-uncovered vertex, add one edge to any neighbor.
// The result has size n - |matching|, which is provably minimum.
const V = [
  { id: 0, x: 60,  y: 60,  label: 'A' },
  { id: 1, x: 180, y: 40,  label: 'B' },
  { id: 2, x: 300, y: 60,  label: 'C' },
  { id: 3, x: 60,  y: 180, label: 'D' },
  { id: 4, x: 180, y: 200, label: 'E' },
  { id: 5, x: 300, y: 180, label: 'F' },
];
const E = [
  [0,1],[1,2],[0,3],[1,4],[2,5],[3,4],[4,5],[1,3],[2,4],
];
const n = V.length;
const selected = new Set(); // indices into E

function coveredVertices(sel){
  const cov = new Set();
  sel.forEach(i => { cov.add(E[i][0]); cov.add(E[i][1]); });
  return cov;
}

// Greedy maximum matching is NOT always maximum; use proper augmenting-path
// matching for general graphs (small here, so a simple augmenting search works).
function maximumMatching(){
  const adj = Array.from({length:n}, ()=>[]);
  E.forEach(([a,b])=>{ adj[a].push(b); adj[b].push(a); });
  const match = new Array(n).fill(-1);
  // Try to augment from each free vertex via a simple alternating DFS.
  function tryAugment(u, seen){
    for(const w of adj[u]){
      if(seen.has(w)) continue; seen.add(w);
      if(match[w] === -1 || tryAugment(match[w], seen)){
        match[u] = w; match[w] = u; return true;
      }
    }
    return false;
  }
  for(let u=0; u<n; u++){
    if(match[u] === -1) tryAugment(u, new Set([u]));
  }
  // Collect matched edges as index list into E.
  const edgeIdx = [];
  const used = new Set();
  for(let u=0; u<n; u++){
    const w = match[u];
    if(w !== -1 && !used.has(u) && !used.has(w)){
      used.add(u); used.add(w);
      const k = E.findIndex(([a,b]) => (a===u&&b===w)||(a===w&&b===u));
      if(k>=0) edgeIdx.push(k);
    }
  }
  return edgeIdx;
}

function minimumEdgeCover(){
  const matchEdges = maximumMatching();
  const cover = new Set(matchEdges);
  let cov = coveredVertices(cover);
  // Patch each uncovered vertex with one incident edge.
  for(let v=0; v<n; v++){
    if(!cov.has(v)){
      const k = E.findIndex(([a,b]) => a===v || b===v);
      if(k>=0){ cover.add(k); cov = coveredVertices(cover); }
    }
  }
  return cover;
}

function render(){
  const svg = document.getElementById('graph');
  svg.innerHTML = '';
  const cov = coveredVertices(selected);
  const NS = 'http://www.w3.org/2000/svg';
  E.forEach(([a,b], i) => {
    const ln = document.createElementNS(NS,'line');
    ln.setAttribute('x1',V[a].x); ln.setAttribute('y1',V[a].y);
    ln.setAttribute('x2',V[b].x); ln.setAttribute('y2',V[b].y);
    ln.setAttribute('class','edge'+(selected.has(i)?' on':''));
    ln.addEventListener('click',()=>{ selected.has(i)?selected.delete(i):selected.add(i); update(); });
    svg.appendChild(ln);
  });
  V.forEach(v => {
    const c = document.createElementNS(NS,'circle');
    c.setAttribute('cx',v.x); c.setAttribute('cy',v.y); c.setAttribute('r',15);
    c.setAttribute('class','vtx'+(cov.has(v.id)?' covered':''));
    svg.appendChild(c);
    const t = document.createElementNS(NS,'text');
    t.setAttribute('x',v.x); t.setAttribute('y',v.y);
    t.setAttribute('class','vlabel'); t.textContent = v.label;
    svg.appendChild(t);
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function update(){
  render();
  const cov = coveredVertices(selected);
  if(cov.size === n) setStatus(fmt('All %n% vertices covered with %size% edges. Minimum is %size2%.', { n: n, size: selected.size, size2: minimumEdgeCover().size }), cov.size===n && selected.size<=minimumEdgeCover().size ? 'ok' : '');
  else setStatus(fmt('%v% vertex/vertices still uncovered.', { v: n-cov.size }), 'bad');
}
function solve(){
  const cover = minimumEdgeCover();
  selected.clear(); cover.forEach(i=>selected.add(i));
  render();
  setStatus(fmt('Minimum edge cover: %size% edges (n − matching = %n% − %length%).', { size: cover.size, n: n, length: maximumMatching().length }),'ok');
  console.log('Minimum edge cover size:', cover.size, '| matching size:', maximumMatching().length, '| n =', n);
}
document.getElementById('solve').addEventListener('click',solve);
document.getElementById('reset').addEventListener('click',()=>{ selected.clear(); update(); });
update();
Result
Console

Try to beat the computer. When you press Solve (minimum), it does something clever: it first finds a maximum matching — the largest set of edges that share no vertex — and then patches up the leftover vertices with one extra edge each. That recipe always yields a provably smallest edge cover, and it runs fast no matter how big the graph gets.

The Real Complexity

Here is the precise status, and it is a happy one for edge cover.

  • Minimum edge cover is in P — solved. On any graph with no isolated vertex, a minimum edge cover can be found in polynomial time. The classical route is through maximum matching, which itself is solvable in polynomial time (Jack Edmonds' Blossom algorithm, 1965).
  • Gallai's theorem (Tibor Gallai, 1959). In a graph with n vertices and no isolated vertex, the size of a maximum matching plus the size of a minimum edge cover equals exactly n. So once you have a maximum matching of size m, the minimum edge cover has size n − m — no search required.
  • The recipe. Take a maximum matching (each matched edge covers two vertices). Every still-uncovered vertex gets one extra edge to a neighbor. The result is optimal, by Gallai's identity.
  • The twin is NP-hard. Vertex cover — pick fewest vertices to touch every edge — is NP-complete, one of Karp's original 21 problems (1972). No polynomial algorithm is known, and finding one would resolve P vs NP.

That contrast is the whole story: two problems, one word apart, sitting on opposite sides of the great divide of computer science. Edge cover landed on the easy side because matching — its hidden engine — is itself easy.

Where It Matters

Because edge cover reduces to matching, it inherits one of the most useful toolkits in all of algorithms:

  • Assignment and pairing: matching workers to tasks, organs to recipients, or partners in a tournament are all "pick edges that share no endpoint" problems.
  • Coverage with redundancy: in a wireless or sensor network, you may want every node to be served by at least one active link while spending as few links as possible — an edge cover by another name.
  • Scheduling: pairing compatible jobs, time-slots or rooms so that nothing is left unserved maps cleanly onto cover and matching.
  • Chemistry and structure: perfect matchings count how molecules pair up (Kekulé structures), and edge covers describe minimal "every-atom-bonded" configurations.

The bigger lesson is strategic: when a problem looks NP-hard, check whether it secretly reduces to matching. If it does — as edge cover does — you get a fast, exact answer. Compare its harder relatives vertex cover and maximum matching.

Conclusion

Edge cover is a gift to anyone learning complexity theory: a problem that looks exactly as hard as the notorious vertex cover, yet quietly slips onto the easy side of the map. The secret is maximum matching, and Gallai's theorem turns a matching into a minimum cover with a single line of arithmetic.

So the next time you meet a graph problem that smells NP-hard, pause and ask the edge-cover question: is there a matching hiding inside? If there is, you may be holding an easy problem dressed up as a hard one — the cheerful opposite of P vs NP, where the disguise runs the other way.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/edge-cover/Content licensed under CC BY-NC 4.0.