Цветовое кодирование, чтобы получить алгоритм FPT для $ K $ Disjoint Trungles

Question

Рассмотрим следующую проблему:

<Сильный> ввод : график $ g= (v, e) $ и целое число $ k \ in \ mathbb {n} $

<Сильные> Выходные данные : Есть ли $ k $ Вершина-непересекающиеся треугольники в $ g $ < / span>?

Предположим, что мы хотим использовать цветное кодирование для разработки алгоритма FPT для этого, как сделано здесь (начиная с слайда 60). Справочный материал предлагает следующий метод:

1. Выберите случайную окраску $ v \ prumearrow [3k] $
2. Проверьте, есть ли красочное решение, где $ 3k $ вершины $ K $ Trungles Используйте различные цвета.

для 2. Предлагает это, среди прочего, этот метод:

Попробуйте каждую перестановку $ \ pi $ $ [3k] $ и проверьте, есть ли треугольники С цветами $ (\ pi (1), \ pi (2), \ pi (3)), (\ pi (4), \ pi (5), \ pi (6 ), \ dots) $

Я не понимаю, почему мы должны проверить каждую перестановку $ \ pi $ цветов. Разве этого не хватало, чтобы просто проверить каждую тройку вершин, посмотреть, есть ли треугольник, и если да, только посчитайте этот треугольник, если он использует только цвета, которые мы не видели раньше? Так нравится:

1. Для каждой тройки $ x, y, z \ in v $ :

2. Если $ x, y, z $ Форма треугольника и цвета $ {c (x), C (Y), C (z)} $ не в цветах_seen_so_far:

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

   2.2 NUM_TRIANGLES += 1

Откуда мы инициализируем Colours_seen_so_far= $ \ Epdyset $ и num_triangles= $ 0 $

Answer 1

Нет, это не правильно.

в качестве контрпример, предположим, что у нас есть график, состоящий из центрального треугольника, вместе с 3 внешними треугольниками, так что каждый внешний треугольник соединен с центральным треугольником одной общей вершиной (т. Е. Каждая вершина центрального треугольника идентифицированас одной вершиной одного из внешних треугольников).

четко, решение для $ k= 3 $ займет три внешних треугольника и не взять внутренний треугольник.

Предположим, что случайная окраска назначает отчетливый цвет в каждой вершине (в противном случае нет красочного решения).

Если ваш алгоритм em> Greedy учитывает центральный треугольник сначала, он всегда будет принимать его, но это неверно.