Begründung bei a) ausreichend?

Question

wieso reicht bei Aufgabenteil a diese Begründung aus? nur weil ich bei eine geratenen Knotenmenge in polynomieller Zeit sagen kann ob alle Kanten einen Knoten in C haben? Damit ist doch die Frage ob es eine Knotenabdeckung einer bestimmten Größe gibt nicht gelöst? oder wo ist da mein Denkfehler?

Answer 1

Na doch, wenn man eine Knotenteilmenge C rät, in der sich k Knoten befinden, dann  muss man nur noch prüfen, ob jede Kante des Graphen mindestens einen ihrer Knoten in C hat. Wenn das der Fall ist, ist C eine Knotenüberdeckung der Größe k - so ist es ja definiert.

Das Raten geht in linearer Zeit, das Verifizieren in polynomieller Zeit, also haben wir insgesamt (nichtdeterministische) Polynomialzeit verbraucht und befinden uns in NP.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen