Конспект: параметризованные алгоритмы

Понятия

Параметр - число во входе, которое мало на практике. FPT - решается за f(k) · n^c с постоянным c.

Дерево поиска - ветвление, где каждая ветка уменьшает параметр. Вектор ветвления - на сколько уменьшается параметр в каждой ветке; основа - корень 1 = Σ x^(−dᵢ).

Ядро - полиномиальное сжатие до равносильного входа размера g(k).

Параметрическое сведение - новый параметр не больше функции от старого. W[1] - задачи, параметрически сводящиеся к клике; при FPT ≠ W[1] они не FPT.

Что унести

ВЕРШИННОЕ ПОКРЫТИЕ ИЗ k ВЕРШИН
перебор наборов  C(n, k) ~ nᵏ / k!       не FPT
по ребру:        одна из u, v в покрытии,  (1, 1)  2ᵏ · m
по вершине:      v  или все её соседи,     (1, d)
    степень >= 2 - 1,618ᵏ;  >= 3 - 1,4656ᵏ (пути и циклы формулой)
    лучшее известное - 1,25284ᵏ (2024)
n = 60, k = 9: наборов 1,5 · 10¹⁰, дерево «нет» - 511 вызовов
k = 6: 63 вызова и на 20, и на 160 вершинах
концентраторы: по ребру 511, по степени 17

ЯДРО
Басс: изолированные - вон; степень > k - взять, k − 1;
      затем рёбер > k² - «нет»;  итог <= k² рёбер, <= k² + k вершин
лист: соседа листа брать всегда (дерево - без ветвлений)
ЛП (Немхаузер-Троттер): единицы взять, нули выбросить,
    половинки - ядро из <= 2k вершин
400 вершин, 6 концентраторов, k = 16: взято 6, осталось 10 рёбер

ВЕКТОРЫ ВЕТВЛЕНИЯ
(1,1) 2      (1,2) 1,618    (1,3) 1,4656    (1,4) 1,3803
(2,2) 1,4142 (2,3) 1,3247   (1,1,1) 3       (2,2,2) 1,732
меньше веток, и каждая тратит побольше

W[1]
клика (k), независимое множество (k) - W[1]-полны;
    доминирующее множество (k) - W[2]
независимое (G, k) → клика (дополнение G, k)       параметрическое
покрытие (G, k)   → независимое (G, n − k)          не параметрическое
клики: 20 → 40 вершин - работа ×6 при l = 3, ×11,5 при l = 5
независимое из 54 при покрытии из 6: 7 вызовов против 5 · 10⁷ наборов

Ловушки джокера

Перебрал наборы из k вершин. nᵏ - не FPT.

Ветвился так, что ветка не тратит параметр. Глубина n.

Применил правило k² до правила высокой степени. Концентратор закрывает сотню рёбер одной вершиной.

Взял и лист, и соседа. Лист не нужен никогда.

Оценил ветвление на глаз. (2, 2, 2) хуже (1, 3) - видно только по корням.

Сделал вывод о FPT по обычному сведению. Параметр должен сохраниться.

Искал FPT для клики по размеру. При FPT ≠ W[1] его нет - нужен другой параметр.

Проверь себя

Чем 2ᵏ · n отличается от nᵏ и что такое FPT? Почему дерево поиска по ребру не глубже k? Найди основу для вектора (1, 3) и объясни, откуда он у ветвления «v или её соседи». Сформулируй правила Басса и объясни оценку k². Почему вершинное покрытие FPT, а независимое множество W[1]-трудно?

FVS удаляет вершины до леса. Итеративное сжатие: решение k+1, догадка о пересечении, защищённое W. Мера остаточного бюджета плюс компоненты G[W] даёт FPT-ветвление.

Подсолнух: k+1 непересекающихся лепестков заставляют бюджет k попасть в сердцевину. Корона: независимое C, N(C)=H, паросочетание насыщает H; удалить C∪H и оплатить |H|. Ядро покрытия ≤3k.