Informatik

Was ist das Vertex-Cover-Problem?

Gegeben ein Graph $G$ und $k$ : Gibt es höchstens $k$ Knoten, die jede Kante berühren?

Das Entscheidungsproblem ist NP-vollständig.