Codifica del colore per ottenere un algoritmo FPT per $ k $ triangoli disgiunti

Question

Considera il seguente problema:

Ingresso : un grafico $ g= (v, e) $ e un intero $ k \ in \ mathbb {n} $

output : ci sono $ k $ triangoli vertice-disgiunti in $ G $ <> $ G $ <> $ G $ <> $ G $ < / span>?

Supponiamo che vogliamo utilizzare la codifica dei colori per sviluppare un algoritmo FPT per quello, come fatto qui (partendo dalla diapositiva 60). Il materiale di riferimento propone il seguente metodo:

.
1. Scegli una colorazione casuale $ v \ raggi [3k] $
2. Verifica se c'è una soluzione colorata in cui la classe $ 3K $ Vertici della $ k $ triangoli usa colori distinti.

per 2. Propone questo, tra gli altri, questo metodo:

Prova ogni permutazione $ \ PI $ di $ [3k] $ e controllare se ci sono triangoli con colori $ (\ PI (1), \ pi (2), \ pi (3)), (\ pi (4), \ pi (5), \ pi (6 ), \ punti) $

Non capisco perché dobbiamo controllare ogni permutazione $ \ PI $ dei colori. Non sarebbe abbastanza per controllare ogni triplo vertici, vedere se ci sono un triangolo e se sì, conta solo questo triangolo se usa solo i colori che non abbiamo visto prima? Così come così:

.

1. per ogni triplo $ x, y, z \ in V $ :

2. Se $ x, y, z $ forma un triangolo e colori $ {c (x), c (y), c (z)} $ non in colori_seen_so_far:

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

   2.2 NUM_TRIANGLES += 1

Dove inizializzano i colori_seen_so_far= $ \ vuotyset $ e num_triangles= $ 0 $

Answer 1

No, questo non è corretto.

Come controesempio, supponiamo di avere un grafico costituito da un triangolo centrale, insieme a 3 triangoli esterni, in modo tale che ciascun triangolo esterno sia unificato al triangolo centrale da un vertice comune (cioè, ogni vertice del triangolo centrale è identificatocon un vertice di uno dei triangoli esterni).

Chiaramente, una soluzione per $ k= 3 $ prendere i tre triangoli esterni e non prendere il triangolo interno.

Assumere la colorazione casuale assegna un colore distinto ad ogni vertice (altrimenti non c'è soluzione colorata).

Se il tuo algoritmo Greedy considera il triangolo centrale prima che lo prenderà sempre, ma questo non è corretto.