Vertex Cover Problem

A vertex cover $V^{\prime }$ of an undirected graph $G=(V,E)$ is a subset of the vertices $V$ that includes at least one endpoint of every edge of the graph.

Formally:

$$V^{\prime }\subseteq V\text{ s.t. }(u,v)\in E\Rightarrow u\in V^{\prime }\vee v\in V^{\prime }$$

Example of vertex covers: A minimum vertex cover is a vertex cover of the smallest possible size. Example of minimum vertex covers:

---

tags: computation-theory resources: Vertex cover - Wikipedia