Codage de couleur pour obtenir un algorithme FPT pour $ K $ Disjoint triangles

Question

Considérez le problème suivant:

entrée : un graphique $ g= (v, e) $ et un entier $ k \ in \ mathbb {n} $

sortie : y a-t-il $ k $ triangles de vertex-disjoint dans $ g $ < / span>?

Supposons que nous souhaitons utiliser le codage de couleur pour développer un algorithme FPT pour cela, comme cela fait ici (à partir de la diapositive 60). Le matériau de référence propose la méthode suivante:

1. Choisissez une coloration aléatoire $ v \ researrow [3k] $
2. Vérifiez s'il y a une solution colorée où la $ 3K $ Les sommets de la $ K $ Triangles utiliser des couleurs distinctes.

pour 2. Il propose cela, entre autres, cette méthode:

Essayez chaque permutation $ \ pi $ de $ [3k] $ et vérifier s'il y a des triangles avec des couleurs $ (\ pi (1), \ pi (2), \ pi (3), (\ pi (4), \ pi (5), \ PI (6 ), \ points) $

Je ne comprends pas pourquoi nous devons vérifier chaque permutation $ \ pi $ des couleurs. Ne serait-il pas suffisant pour vérifier chaque triangle de sommets, voir s'il y a un triangle et, si oui, ne comptez que ce triangle s'il utilise uniquement des couleurs que nous n'avons pas vues auparavant? Donc comme si:

1. pour chaque triple $ x, y, z \ in v $ :

2. si $ x, y, z $ formule un triangle et des couleurs $ {c (x), c (y), c (z)} $ pas dans couleurs_seen_so_far:

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

   2.2 num_triangles += 1

où nous initialisons les couleurs_seen_so_far= $ \ videtyset $ et num_triangles= $ 0 $

Answer 1

Non, ce n'est pas correct.

En tant que contre-exemple, supposons que nous disposions d'un graphique constitué d'un triangle central, ainsi que de 3 triangles extérieurs, de sorte que chaque triangle extérieur soit joint au triangle central par un sommet partagé (c'est-à-dire que chaque sommet du triangle central est identifié.avec un sommet de l'un des triangles extérieurs).

Clairement, une solution pour $ k= 3 $ prendrait les trois triangles extérieurs et ne prenez pas le triangle intérieur.

suppose que la coloration aléatoire assigne une couleur distincte à chaque sommet (sinon il n'y a pas de solution colorée).

Si votre algorithme gourmand prend en premier lieu le triangle central, il le prendra toujours, mais cela est incorrect.