Твердость проблем FPT

Покрытие Vertex может быть легко уменьшено до Независимого набора и наоборот.

Однако в контексте параметризованной сложности Независимый набор сложнее, чем Vertex Cover. Ядро с вершин существует для Vertex Cover, но независимое множество W 1 жестких.$2k$

Как меняется характер Независимого множества в контексте FPT и почему?

Основная идея ответа: если мы уменьшим экземпляр параметризованного независимого набора до параметризованного покрытия вершин, то параметр, который у нас получится, зависит от размера графика и зависит не только от входного параметра. Теперь немного подробнее.

Как вы знаете, параметризованная задача находится в (равномерном) FPT, если существует алгоритм, который решает, содержится ли вход ( x , k ) в Q за время f ( k ) | х | O ( 1 ) для некоторой функции f .$Q$$(x,k)$$Q$$f(k) |x|^{O(1)}$$f$

Поскольку вы можете решить, будет ли граф иметь покрытие вершин размера k , выбрав ребро и разветвление, на котором из двух его конечных точек поместить в покрытие вершин, это разветвление только углубляется на k (иначе вы положили больше k вершины в обложке) и легко проходит во времени O ( 2 k n 2 ) ; следовательно, k- Vertex Cover находится в FPT.$G$$k$$k$$k$$O(2^k n^2)$$k$

Теперь предположим, что мы хотим попробовать использовать этот алгоритм, чтобы показать, что параметризованный независимый набор находится в FPT; предположим, что нам дан граф на n вершинах, и мы хотим решить, имеет ли он независимый набор размеров ℓ . Это эквивалентно вопросу, имеет ли G покрытие вершин размера n - ℓ . Таким образом , мы используем выше алгоритм для вычисления ответа в O ( 2 н - ℓ п 2 ) времени. Для нашего алгоритма FPT экспоненциальная функция во время выполнения может зависеть от параметра, который равен ℓ , но он НЕ может зависеть от размера входа, который равен $G$$n$$\ell$$G$$n - \ell$$O(2^{n - \ell} n^2)$$\ell$$n$; но подход , который мы набросали использует время экспоненту в и поэтому не является параметром FPT по параметру л . Вот почему тот факт, что Vertex Cover находится в FPT, не означает, что Независимый набор находится в FPT.$n - \ell$$\ell$

Я бы не сказал, что «природа» проблемы меняется, что бы это ни значило. Все, что изменяется, - это параметр, то есть способ измерения сложности проблемы.

Графы, у которых размер вершины не превышает , настолько структурированы, что их можно эффективно уменьшить в размерах: мы можем жадно найти максимальное совпадение размера не более k, а остальная часть графика представляет собой, по крайней мере, независимый набор размеров. п - 2 к . Используя правила сокращения, такие как сокращение короны, количество вершин может быть уменьшено до максимум 2 k .$k$$k$$n-2k$$2k$

С другой стороны, графы, у которых вершинные покрытия имеют размер не более (или, что эквивалентно, максимальные независимые имеют размер не менее k ), по-видимому, не имеют такой простой структуры. Это можно сделать точным, как вы указали: их структура позволяет нам кодировать любую W [ 1 ] -проблему.$n-k$$k$$W[1]$

Следующее может дать некоторую интуицию для разницы. Подмножество вершин S является покрытием вершин G = (V, E) тогда и только тогда, когда VS является независимым множеством, поэтому, если MVC является размером минимального покрытия вершин, то MIS = | V | -MVC является размером максимальный независимый набор. Алгоритм FPT, параметризованный X, допускает экспоненциальное время выполнения как функцию X. Случайный граф на n вершинах с вероятностью ребра половина имеет с высокой вероятностью MIS размером около 2logn и MVC размером около n-2logn. Таким образом, по крайней мере для этих графиков алгоритм FPT, параметризованный MVC, просто позволяет гораздо больше времени, чем один, параметризованный MIS.

Хотя я согласен с тем, что сказали другие, другой способ, который я считаю полезным, думая об этих вещах, состоит в том, чтобы переформулировать проблему как проблему распознавания, то есть "принадлежит ли входной граф семейству графов, у которых покрытие вершин не больше k?" / «Принадлежит ли входной граф семейству графов с независимым множеством не менее k?».

Интуитивно понятно, что более ограниченное семейство графов должно быть легче распознать, чем более богатое, более общее. Семейство графов покрытия вершин не более k очень ограничено, фактически каждый такой граф может быть описан с использованием всего битов, что намного меньше, чем обычно требуется O ( n 2 ) бит , предполагая, что k значительно меньше, чем n. Семейство графов независимого множества, по крайней мере, k, с другой стороны, очень богато: любой граф можно отредактировать так, чтобы он принадлежал ему, удалив не более k 2 ребер.$O(k^2+2^k\log n)$$O(n^2)$$k^2$

Так что для меня это одно интуитивное объяснение, почему я ожидал бы, что будет легче распознать небольшое покрытие вершин, чем небольшое независимое множество. Конечно, должно быть очевидно, что вышеприведенные мысли не близки к формальному аргументу, и я полагаю, что в конечном итоге наиболее убедительным доказательством того, что действительно сложнее распознать независимый набор размера k, является именно W-твердость независимого устанавливать!

Это очень косвенный ответ, и он может не совсем решить вашу проблему. Но FPT и иерархия W тесно связаны с приближенностью (проблемы FPT часто имеют PTAS и т. Д.). В этом контексте обратите внимание, что для любого графа VC = n - MIS, и поэтому приближение для VC не дает приближения для MIS. Вот почему вам нужны L-сокращения для приближений. Я подозреваю, что для параметризованной сложности существует эквивалентное понятие «сохранение ядра».