Codificación de colores para obtener un algoritmo FPT por $ k $ disjoint triangles

Question

Considere el siguiente problema:

entrada : un gráfico $ g= (v, e) $ y un entero $ k \ in \ mathbb {n} $

Salida : están ahí $ k $ vértice-disjoint triangles en $ g $ < / span>?

Supongamos que queremos usar la codificación de colores para desarrollar un algoritmo FPT para eso, como se hace aquí (a partir de la diapositiva 60). El material de referencia propone el siguiente método:

1. Elija un colorante aleatorio $ v \ judowarrow [3k] $
2. Compruebe si hay una solución colorida donde el $ 3k $ vértices del $ k $ triangles Usa colores distintos.

Para 2. Propone esto, entre otros, este método:

Pruebe cada permutación $ \ pi $ de $ [3k] $ y compruebe si hay triángulos con colores $ (\ pi (1), \ pi (2), \ pi (3)), (\ pi (4), \ pi (5), \ pi (6 ), \ puntos) $

No entiendo por qué tenemos que revisar cada permutación $ \ pi $ de los colores. ¿No sería suficiente para comprobar cada triple de vértices, ver si hay un triángulo y, de ser así, solo contar este triángulo si solo usa colores que no hemos visto antes? Así que así:

1. para cada triple $ x, y, z \ in v $ :

2. Si $ x, y, z $ forman un triángulo y colores $ {C (x), C (y), C (Z)} $ no en Colors_seen_so_far:

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

   2.2 num_triangles += 1

Dónde inicializamos COLOR_SEEN_SO_FAR= $ \ vacioset $ y num_triangles= $ 0 $

Answer 1

No, esto no es correcto.

Como contraejemplo, supongamos que tenemos un gráfico que consiste en un triángulo central, junto con 3 triángulos exteriores, de modo que cada triángulo externo se une al triángulo central mediante un vértice compartido (es decir, cada vértice del triángulo central se identificacon un vértice de uno de los triángulos exteriores).

Claramente, una solución para $ k= 3 $ tomaría los tres triángulos exteriores y no tomaría el triángulo interno.

Supongamos que la coloración aleatoria asigna un color distinto a cada vértice (de lo contrario, no hay una solución colorida).

Si su álgano de codicioso considera el triángulo central primero, siempre lo tomará, pero esto es incorrecto.