頂点被覆
グラフ理論において、グラフGの頂点からなるある集合VがGの頂点被覆(ちょうてんひふく、英: vertex cover)であるとは、Gのどの辺をとってもその端点のどちらかがVに含まれるという意味である。最小頂点被覆を求める問題は計算機科学における古典的な最適化問題であり、近似アルゴリズムのある典型的なNP困難な問題でもある。その決定問題版である頂点被覆問題は計算複雑性理論における古典的なNP完全問題である。さらに頂点被覆問題には固定パラメータ容易性 (fixed-parameter tractability) があり、パラメータ化計算量理論の中心問題の1つである。
最小頂点被覆問題は、整数計画問題に定式化でき、その双対問題は最大マッチング問題である。
グラフ G の頂点被覆とは頂点の集合 C であり、G の各辺は C 内の少なくとも1つの頂点と接合する。このとき集合 C は G の辺を「被覆 (cover)」すると言う。次の図は2つのグラフの頂点被覆の例を表したものである(集合 C は赤で示されている)。

最小頂点被覆 (minimum vertex cover) は、最も小さい大きさの頂点被覆である。頂点被覆数 (vertex cover number) τ {\displaystyle \tau } は最小頂点被覆の大きさである。次の図は2つのグラフの最小頂点被覆の例を表したものである。
SIAM Journal on Applied Mathematics 32 (4): 826–834. doi:10.1137/0132071.
1 2 Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0
↑ Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), Combinatorial Optimization: Algorithms and Complexity, Dover , p. 432, mentions both Gavril and Yannakakis. Garey, Michael R.; Johnson, David S. (1979 [2003]), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.