Lösung P-30

Dateiinhalt

Musterloesung P-30
------------------

Da die Problemstellung sehr aehnlich zu VERTEX COVER ist,
reduzieren wir VERTEX COVER auf DOMINATING SET.

Erste Beobachtung: ein Vertex Cover U in einem Graphen ist auch immer
dominierend. Denn ist v in V nicht selbst in U, dann gibt es
mindestens eine Kante e = {u,v}, die mit v inzidiert. Dann muss aber
das andere Ende u in U sein, damit e ueberdeckt ist, also ist v von u
dominiert.  (ObdA gibt es keine isolierten Knoten.)

Die Umkehrung gilt aber nicht: in einem Dreieck {u,v} {u,w} {v,w} ist
zB {u} dominierend, aber kein Vertex Cover.

Daher macht man die folgende Konstruktion: Bilde G', indem fuer jede
Kante e={u,u'} in G ein neuer Knoten v_e hinzu, mit Kanten {u,v_e} und
{v_e,u'} hinzugefuegt wird.

Ist nun U ein Vertex Cover in G, so ist U eine dominierende Menge in
G', denn U dominiert jeden Knoten in G, und ein neuer Knoten v_e wird
von demjenigen Knoten dominiert, der die Kante e ueberdeckt.

Also: hat G ein Vertex Cover mit k Knoten, dann hat G' eine
dominierende Menge mit k Knoten. Bleibt die Umkehrung zu zeigen. 

Ist U eine dominierende Menge in G', die nur Knoten aus G enthaelt,
so ist diese auch ein Vertex Cover in G: jeder neue Knoten v_e muss 
dominiert sein, und der Knoten, der ihn dominiert, ueberdeckt e. 

Bleibt als letztes zu beobachten, dass die neuen Knoten aus einer
dominierenden Menge eliminiert werden koennen. Enthaelt aber eine 
dominierende Menge U den neuen Knoten v_e mit e={u,v}, dann 
dominiert dieser die Knoten u,v und v_e. Dann kann ich ihn aber 
genauso gut durch u oder v ersetzen, dann sind diese Knoten immer 
noch dominiert, und die Menge ist nicht groesser geworden. 

Also: hat G' eine dominierende Menge der Groesse k, dann auch eine,
die nur Knoten aus V enthaelt, und diese ist dann auch ein Vertex
Cover in G, also hat G ein Vertex Cover der Groesse k.

Insgesamt gilt: die Abbildung (G,k) |-> (G',k) ist eine 
polynomielle Reduktion von Vertex Cover auf Dominating Set.