Parameterized Complexity

В 2014 году Margaret Reid-Miller из Google описала, как parameterized complexity изменила подход к анализу социальных графов: вместо отчаяния перед NP-трудными задачами - поиск структурного параметра, который мал на реальных данных. Facebook-граф имеет treewidth не 10^9, а порядка нескольких тысяч. Это делает точные алгоритмы возможными там, где казалось всё безнадёжно.

• **Биоинформатика**: реконструкция филогенетических деревьев с рекомбинациями - FPT-алгоритмы с параметром k = число рекомбинационных событий, который мал в реальных популяциях
• **VLSI-дизайн**: схемы чипов имеют малый treewidth (планарность), что позволяет применять FPT-алгоритмы для оптимизации размещения элементов
• **AI-планирование**: задача планирования PSPACE-трудна в общем случае, но на structured domains с малым числом взаимодействующих объектов FPT-алгоритмы дают точные планы за разумное время

Fixed-Parameter Tractability (FPT)

Сеть из 10 000 маршрутизаторов заражена вирусом. Требуется найти минимальное Vertex Cover размером k, чтобы изолировать все заражённые соединения. k оказывается маленьким - около 20. При n=10 000 и k=20 алгоритм O(2^k * n) выполняется за 2^20 * 10000 = 10^10 операций. Это много, но **не растёт с n**. Алгоритм **FPT (Fixed-Parameter Tractable)**: время работы f(k) * poly(n), где параметр k не зависит от n. Комбинаторный взрыв изолирован в f(k), а n входит полиномиально.

FPT-алгоритм для Vertex Cover с параметром k (размер покрытия): бранчинг-алгоритм O(2^k * n). Аргумент: берём любое ребро (u,v). OPT должно содержать u или v. Ветвимся: рекурсивно решаем с {u} или {v} в покрытии, уменьшая k на 1. Глубина рекурсии <= k, ветвление бинарное => 2^k листьев. Kernelization улучшает до O(1.2738^k * k * n).

W-иерархия и W[1]-трудность

FPT не всесилен. Задача Independent Set (найти независимое множество размером k) кажется похожей на Vertex Cover - но предположительно не FPT. Параметризованная теория сложности строит **W-иерархию**: FPT ⊆ W[1] ⊆ W[2] ⊆ ... ⊆ XP. Если задача W[1]-трудна, скорее всего FPT-алгоритма нет (при предположении FPT != W[1], что является параметризованным аналогом P != NP). Independent Set W[1]-трудна - именно поэтому социальные сети не находят максимальный клик точно, а используют аппроксимации.

W[1]-трудность доказывается параметризованными редукциями, сохраняющими параметр. Canonical W[1]-трудная задача: Independent Set с параметром k. W[2]-трудная: Dominating Set с параметром k. W[t] определяется через схемы булевых формул глубины t. XP: алгоритмы вида n^f(k) (полиномиальные для фиксированного k, но степень растёт). Грань FPT vs W[1] - главная открытая проблема параметризованной сложности.

Ядризация (Kernelization)

Умный способ ускорить FPT-алгоритм: перед запуском **сжать задачу**. Ядризация (kernelization) - полиномиальный алгоритм, который преобразует экземпляр (G, k) в меньший экземпляр (G', k') так, что: |G'| <= g(k) (ядро ограничено функцией от k), k' <= k, и ответ сохраняется. Для Vertex Cover с параметром k: вершины степени > k можно сразу включить в покрытие (они обязаны быть там), вершины степени 0 можно удалить. Ядро имеет <= k^2 рёбер и <= 2k вершин.

Правила редукции для ядра Vertex Cover: 1) Isolated vertices: удалить (не нужны в OPT). 2) High-degree vertices: если deg(v) > k, то v обязан быть в OPT (иначе нужно > k вершин для покрытия его рёбер) - добавляем v, уменьшаем k. 3) После правил 1-2: если рёбер > k^2 или вершин > 2k, то решения с размером k нет. Линейное ядро для Vertex Cover дал алгоритм Crown Decomposition: O(k) вершин.

Ширина дерева (Treewidth)

Многие NP-трудные задачи становятся полиномиальными на деревьях. Ширина дерева (treewidth) измеряет, насколько граф «похож на дерево»: treewidth=1 - это дерево, treewidth=n-1 - полный граф. На графах с малым treewidth k тысячи NP-трудных задач решаются за f(k) * n время. Bayesian networks в машинном обучении - это графические модели, и вывод (inference) на них полиномиален при малом treewidth: именно поэтому tree-structured BN-модели вычислимы, а общие NP-трудны.

Tree decomposition графа G - это дерево T, где каждый узел содержит множество (bag) вершин G, удовлетворяющее: каждая вершина G в хотя бы одном bag; каждое ребро G покрыто каким-то bag; для каждой вершины v G - узлы T, содержащие v, образуют связное поддерево. Treewidth = max|bag| - 1. Алгоритм Courcelle (1990): любое свойство графа, выразимое в MSO_2 логике, разрешимо за f(tw) * n на графах с treewidth tw.

Ключевые идеи

• **FPT** изолирует комбинаторный взрыв в параметре k: время f(k)*poly(n) практично при малом k, даже если f(k) большая
• **W-иерархия** разделяет FPT и вероятно не-FPT задачи: Independent Set W[1]-трудна, Vertex Cover - FPT; параметризованные редукции доказывают W[1]-трудность
• **Ядризация** сжимает задачу до ядра размера g(k) за полиномиальное время; **treewidth** делает тысячи NP-трудных задач FPT на «почти-деревьях»

Связанные темы

Параметризованная сложность дополняет классическую NP-теорию и аппроксимацию:

• Аппроксимация и inapproximability — Аппроксимация vs параметризация - две стратегии для NP-трудных задач: аппроксимация жертвует точностью, FPT - ограничивает параметр
• NP и NP-полнота — W[1]-трудность - параметризованный аналог NP-полноты; FPT-редукции аналогичны полиномиальным редукциям в классической теории

Вопросы для размышления

• Vertex Cover FPT, Independent Set вероятно W[1]-трудна - при этом эти задачи дополняют друг друга (VC = V \ IS для оптимальных решений). Как объяснить асимметрию их параметризованной сложности?
• Treewidth дорожной сети маленький, а treewidth социальной сети - большой. Какие структурные свойства реальных графов определяют treewidth - и почему это важно для практических алгоритмов?
• Ядризация полиномиально сжимает задачу до ядра g(k). Существуют ли FPT-алгоритмы без полиномиального ядра - и что это говорит о структуре FPT-класса?

Связанные уроки

• alg-01-big-o