[Parametrisierte Algorithmen] DOMSET \in FPT?

[Stasik]

Hi,

es kursieren Gerüchte, Dominating Set liege nicht in FPT. Nun stimmt das und wenn ja warum? Kann man das Problem nicht durch das Färben von k Knoten mit k Farben lösen?

Grüße

[ibogi]

Dominating Set ist nicht mit Parameter k in FPT, aber mit Parameter t es ist andere Geschichte. Versuch mal zu erfinden, gibt es eine Beschränkung für die Anzahl der Nachbarn (und es gibt)!

[Stasik]

Nachbarn von? wenn ich fragen darf?

[Tommytb]

Mit Baumweite als Parameter ist doch sogut wie alles in fpt...
Das mit dem Färben kann ja nur schiefgehen, weil du die Anzahl aller möglichen Färbungen nicht in k beschränken kannst. Warum das jetzt so ist, da denk ich um die Uhrzeit nicht mehr drüber nach

[Stasik]

unser Graph ist ja nicht planar also nix mit Baumweite *betrunken denken*

[ibogi]

Ein Knoten kann mit höchstens t-1 Kanten verbunden sein. Wenn es wäre größer als das, dann kann man die Lösung in poly-Zeit finden (der Knoten dominiert t-1 Nachbarn und ihn selbst).

[Stasik]

t-1 oder, aber das hilft irgendwie nicht, dachte man macht einfach bounded tree search..... aber das geht nicht, weil das dominating set ja beliebig zerstreut sein kann


hmmm.... oder ist die Baumweite in dem Höchstgrad des Graphen begrenzt?

[Tommytb]

hmmm.... oder ist die Baumweite in dem Höchstgrad des Graphen begrenzt?

Höchstens die minimale Baumweite
Hmm... also ausser ner Clique wüsste ich jetzt auch nicht was die Baumweite noch in die Höhe treiben kann... also, könnte schon sein...

[Tommytb]

hmmm.... oder ist die Baumweite in dem Höchstgrad des Graphen begrenzt?

Höchstens die minimale Baumweite
Hmm... also ausser ner Clique wüsste ich jetzt auch nicht was die Baumweite noch in die Höhe treiben kann... also, könnte schon sein...

Ich nehm alles zurück und behaupte das Gegenteil Bei nem Gitter haben wir mal gesehen, dass bw groß wird, grad aber klein ist.