Eine Knotenüberdeckung ist in der Graphentheorie eine Teilmenge der Knoten eines Graphen, die insgesamt mit allen Kanten inzident sind.

Das Komplement einer kleinsten Knotenüberdeckung ist in jedem Graph eine größte stabilen Menge. Die Bestimmung beider Größen ist im allgemeinen NP-schwer. In bipartiten Graphen können sie über die Paarungszahl in polynomieller Zeit bestimmt werden.

siehe auch: Cliquen und stabile Mengen