Farbkodierung, um einen FPT-Algorithmus für disjunkte Dreiecke von $ K $ zu erhalten

Question

Betrachten Sie das folgende Problem:

input : ein Diagramm $ g= (v, e) $ und eine ganze Zahl $ k \ in \ mathbb {n} $

Ausgabe : Gibt es $ K $ Vertex-disjunkte Dreiecke in $ g $ < / span>?

Nehmen Sie an, wir möchten die Farbcodierung verwenden, um einen FPT-Algorithmus dafür zu entwickeln, da dies getan hier (ausgehend von der Folie 60). Das Referenzmaterial schlägt das folgende Verfahren vor:

.
1. Wählen Sie eine zufällige Farbgebung $ v \ Rightarrow [3k] $
2. Prüfen Sie, ob es eine farbenfrohe Lösung gibt, in der der $ 3K $ Scheitelpunkte der $ K $ Dreiecke Verwenden Sie verschiedene Farben.

für 2. Es schlägt dies vor, unter anderem diese Methode:

versuchen Sie jede Permutation $ \ pi $ von $ [3K] $ und prüfen Sie, ob Dreiecke vorhanden sind mit Farben $ (\ pi (1), \ pi (2), \ pi (3)), (\ pi (4), \ pi (5), \ pi (6 ), \ Punkte) $

Ich verstehe nicht, warum wir jede Permutation $ \ pi $ der Farben überprüfen müssen. Wäre es nicht genug, um nur jedes Dreifach von Scheitelpunkten zu überprüfen, ob es ein Dreieck gibt, und wenn ja, zählen Sie dieses Dreieck nur, wenn es nur Farben verwendet, die wir noch nicht gesehen haben? So wie so:

.

1. Für jeden Triple $ x, y, z \ in v $ :

2. wenn $ x, y, z $ ein Dreieck und Farben $ {c (x), c (y), c (z)} $ nicht in colors_seen_so_far:

   2.1 colors_seen_so_far += $ \ {c (x), c (y), c (z) \} $

   2.2 num_triantles += 1

wo wir colors_seen_so_far= $ \ emesyset $ und num_triantles= $ 0 $

Answer 1

nein, das ist nicht korrekt.

Angenommen, wir haben angenommen, dass wir eine Grafik, bestehend aus einem zentralen Dreieck, zusammen mit 3 äußeren Dreiecke, so dass jedes äußere Dreieck, das mit einem gemeinsamen Scheitelpunkt mit dem zentralen Dreieck verbunden ist, mit dem zentralen Dreieck verbunden ist (dh jeder Scheitelpunkt des zentralen Dreiecks ist identifiziertmit einem Scheitelpunkt eines der äußeren Dreiecke).

eindeutig, eine Lösung für $ k= 3 $ würde die drei äußeren Dreiecke nehmen und nicht das innere Dreieck nehmen.

Angenommen, die zufällige Färbung weist jedem Scheitelpunkt eine bestimmte Farbe zu (sonst gibt es keine farbenfrohe Lösung).

Wenn Ihr gierig Algorithmus das zentrale Dreieck zuerst betrachtet, wird es immer dauern, aber das ist falsch.