Codificação de cores para obter um algoritmo de FPT para triângulos de $ K $ Disjoint

Question

Considere o seguinte problema:

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

Saída : estão lá $ k $ triângulos de vertex-disjuntos na $ g $ < / span>?

Suponha que desejemos usar codificação de cores para desenvolver um algoritmo de FPT para isso, como feito Aqui (partindo do slide 60). O material de referência propõe o seguinte método:

.
1. Escolha uma coloração aleatória $ v \ rightarrow [3k] $
2. Verifique se há uma solução colorida onde a $ 3K $ vértices da $ k $ triângulos Use cores distintas.

para 2. Propõe isto, entre outros, este método:

tente cada permutação $ \ pi $ de $ [3k] $ e verifique se há triângulos com cores $ (\ Pi (1), \ Pi (2), \ Pi (3)), (\ Pi (4), \ Pi (5), \ Pi (6 ), \ pontos) $

Eu não entendo porque temos que verificar todas as permutação $ \ pi $ das cores. Não seria suficiente apenas verificar cada triplo de vértices, ver se há um triângulo e, em caso afirmativo, contar apenas este triângulo se ele usa apenas cores que não vimos antes? Então, assim:

.

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

2. se $ x, y, z $ formam um triângulo e cores $ {c (x), c (y), c (z)} $ não em cores_seen_so_far:

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

   2.2 num_triangles += 1

onde nós inicializamos cores_seen_so_far= $ \ vazio $ e num_triangles= $ 0 $

Answer 1

Não, isso não está correto.

Como um contraexemplo, suponha que tenhamos um gráfico consistindo de um triângulo central, juntamente com 3 triângulos externos, de modo que cada triângulo externo seja unido ao triângulo central por um vértice compartilhado (ou seja, cada vértice do triângulo central é identificadocom um vértice de um dos triângulos externos).

Claramente, uma solução para $ k= 3 $ levaria os três triângulos externos e não levaram o triângulo interno.

Suponha que a coloração aleatória atribui uma cor distinta a cada vértice (caso contrário, não há solução colorida).

Se o seu algoritmo ganancioso considera o triângulo central primeiro, ele sempre o levará, mas isso está incorreto.