頂点被覆
係数が2の近似アルゴリズムがあり、辺を選んでその両端の頂点を頂点被覆に入れ、グラフからそれらを削除するということを繰り返す。あるいは、力まかせアルゴリズムで極大マッチング M を求め、M に属する全端点から頂点被覆 C を構築するという方法もある。次の図では、極大マッチング M を赤で示し、頂点被覆 C を青で示している。

このように構築した集合 C は頂点被覆である。辺 e が C によって被覆されていないとする。すると、M ∪ {e} がマッチングであり、かつ e ∉ M ということになり、M が極大マッチングであるという前提と矛盾する。さらに e = {u,v} ∈ M とすると、任意の頂点被覆(最小頂点被覆も含む)は u か v(または両方)を含まなければならず、さもなくば e が被覆されない。したがって最小頂点被覆は、M の各辺の両端の少なくとも一方を含む。まとめると、集合 C は最小頂点被覆に対して高々2倍の大きさに収まる。
この単純なアルゴリズムは、Fanica Gavril と Mihalis Yannakakis が発見した。
より複雑な技法を使うと、近似係数が若干よい近似アルゴリズムがあることが示される。例えば、近似係数 2 − Θ ( 1 / log  | V | ) {\displaystyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)} の近似アルゴリズムが知られている。
グラフの頂点数は、頂点被覆数と最大独立集合の大きさの総和に等しい。