[Par Alg] Reduktion von Hitting set auf Dominating set

[ibogi]

Ich habe Problem mit letzter Hausaufagebe. Ich habe versucht eine Reduktion von Hitting Set auf Dominating Set zu bilden, aber ohne Erfolg. Zwar hat es mir gelungen, mit gerichteten Graphen statt ungerichteter fur Dominating Set eine Reduktion zu bauen, aber dass reicht doch nicht.

[Tommytb]

ich denke es haut hin wenn du für jede Menge in der Familie nen neuen Teilgraph einführst und diese dann irgendwie geschickt verbindest

Edit: Wobei ich meine Lösung auch nochmal neu überdenken muss grade Edit2: Ich denke es geht wenn du knoten für alle vi und knoten für jede menge nimmst und diese geschickt verbindest

[Stasik]

mit dem gerichteten Graphen geht es imho auch, auch wenn zu umständlich.

man simuliert einfach gerichtete Graphen durch ungerichtete:

o
|
\|/
o

wird zu

o-o
/|
o-o

[ibogi]

Danke, das war der entscheidende Schritt, den ich vermisste!