Параметрическая редукция

Стандартный пример алгоритма параметрической редукции — параметрическая редукция задачи о вершинном покрытии С. Басса[1]. В этой задаче входом является неориентированный граф ${\displaystyle G}$ вместе с числом ${\displaystyle k}$. Выходом является множество максимум ${\displaystyle k}$ вершин, которое включает конечную вершину каждого графа, если такое множество существует, либо исключение неудачи, если такого множества не существует. Эта задача является NP-трудной. Однако следующие правила могут быть использованы для её параметрической редукции:

1. Если ${\displaystyle k>0}$ и ${\displaystyle v}$ является вершиной степени, большей ${\displaystyle k}$, удаляем ${\displaystyle v}$ из графа и уменьшаем ${\displaystyle k}$ на единицу. Любая задача о вершинном покрытии размера ${\displaystyle k}$ должна содержать ${\displaystyle v}$, поскольку в другом случае слишком много её соседей было бы выбрано для покрытия инцидентных рёбер. Таким образом, оптимальное вершинное покрытие для исходного графа может быть образовано из покрытия редуцированной задачи путём добавления ${\displaystyle v}$ обратно в покрытие.
2. Если ${\displaystyle v}$ является изолированной вершиной, удаляем её. Изолированная вершина не может покрыть какое-либо ребро, так что в этом случае ${\displaystyle v}$ не может быть частью любого минимального покрытия.
3. Если больше чем ${\displaystyle k^{2}}$ рёбер остаётся в графе, и никакие предыдущих два правила не могут быть применены, то граф не может содержать вершинное покрытие размера ${\displaystyle k}$. После удаления всех вершин степени большей ${\displaystyle k}$, каждая оставшаяся вершина может покрыть не более ${\displaystyle k}$ рёбер и множество из ${\displaystyle k}$ вершин может покрыть не более ${\displaystyle k^{2}}$ рёбер. В этом случае вход задачи может быть заменён графом двумя вершинами, одним ребром, а значение ${\displaystyle k=0}$, и эта задача также не имеет решения.

Алгоритм, который применяет эти правила повторно, пока не могут быть сделаны дальнейшие редукции, обязательно обрывается с ядром, которое имеет не более ${\displaystyle k^{2}}$ рёбер и (поскольку каждое ребро имеет максимум две конечные вершины и нет изолированных вершин) не более ${\displaystyle 2k^{2}}$ вершин. Эта параметрическая редукция может быть осуществлена за линейное время. Когда ядро построено, задача о вершинном покрытии может быть решена алгоритмом полного перебора, который проверяет, что каждое подмножество ядра является покрытием ядра. Таким образом, задача о вершинном покрытии может быть решена за время ${\displaystyle O(2^{2k^{2}}+n+m)}$ для графа с ${\displaystyle n}$ вершинами и ${\displaystyle m}$ рёбрами, что позволяет решить их эффективно, когда ${\displaystyle k}$ мало, даже если ${\displaystyle n}$ и ${\displaystyle m}$ велики.

Хотя эта граница является фиксированно-параметрически разрешимой, её зависимость от параметра выше, чем можно пожелать. Более сложные процедуры параметрической редукции могут улучшить эту границу путём нахождения более маленьких ядер за счёт большего времени работы на шаге параметрической редукции. Известны алгоритмы для задачи о вершинном покрытии параметрической редукции, которые дают ядра максимум с ${\displaystyle 2k}$ вершинами. Алгоритм, на котором достигается эта улучшенная граница, использует полуцелочисленность релаксации задачи о вершинном покрытии задачей линейного программирования согласно Джорджу Немхаузеру и Троттеру[2]. Другой алгоритм параметрической редукции, достигающий эту границу, основывается на приёме, который называется правилом коронной редукции и использует доводы альтернирования пути[3]. В настоящее время лучший известный алгоритм параметрической редукции в терминах числа вершин принадлежит Лампису[4] и достигает ${\displaystyle 2k-c\log k}$ вершин для любой константы ${\displaystyle c}$.

Невозможно для этой задачи найти ядро размера ${\displaystyle O(\log k)}$, если только не P=NP, в этом случае ядро привело бы к полиномиальному алгоритму для NP-трудной задачи о вершинном покрытии. Однако более строгие границы для размера ядра могут быть доказаны в этом случае — если только не coNP ${\displaystyle \subseteq }$ NP/poly (что теоретики сложности вычислений считают маловероятным), для любого ${\displaystyle \epsilon >0}$ невозможно за полиномиальное время найти ядра с ${\displaystyle O(k^{2-\epsilon })}$ рёбрами[5].

В литературе нет ясного общего мнения, как следовало бы определить параметрическую редукцию формально и имеется тонкая разница в использовании таких выражений.

Задача является фиксированно-параметрически разрешимой тогда и только тогда, когда её можно параметрически редуцировать и она разрешима.

То, что параметрически редуцируемая и разрешимая задача является фиксированно-параметрически разрешимой, можно видеть из определения выше: алгоритм параметрической редукции, который работает за время ${\displaystyle O(|x|^{c})}$ для некоторого c, привлекается для получения ядра размера ${\displaystyle f(k)}$. Затем ядро решается алгоритмом, который проверяет, что задача разрешима. Полное время работы этой процедуры равно ${\displaystyle g(f(k))+O(|x|^{c})}$, где ${\displaystyle g(n)}$ — время работы алгоритма, используемого для решения ядер. Поскольку ${\displaystyle g(f(k))}$ вычислимо, например, при предположении, что ${\displaystyle f(k)}$ вычислимо, а ${\displaystyle g(f(k))}$ можно вычислить путём перебора всех возможных входов длины ${\displaystyle f(k)}$, отсюда вытекает, что задача фиксированно-параметрически разрешима.

Доказательство в другом направлении, что фиксированно-параметрически разрешимая задача является параметрически редуцируемой и разрешимой, чуть более трудно. Предположим, что вопрос нетривиален, что означает, что имеется по меньшей мере один представитель задачи с именем ${\displaystyle I_{yes}}$, принадлежащий языку, и по меньшей мере один представитель задачи, не принадлежащий языку, с именем ${\displaystyle I_{no}}$. В противном случае замена любого представителя пустой строкой является допустимой параметрической редукцией. Предположим также, что задача является фиксированно-параметрически разрешимой, то есть она имеет алгоритм, работающий максимум за ${\displaystyle f(k)\cdot |x|^{c}}$ шагов на представителях задачи ${\displaystyle (x,k)}$ для некоторой константы ${\displaystyle c}$ и некоторой функции ${\displaystyle f(k)}$. Для осуществления параметрической редукции входа применяем алгоритм на заданном входе за максимум ${\displaystyle |x|^{c+1}}$ шагов. Если алгоритм завершается ответом, используем ответ для выбора либо ${\displaystyle I_{yes}}$, либо ${\displaystyle I_{no}}$ в качестве ядра. Если, вместо этого, достигаем границы число шагов ${\displaystyle |x|^{c+1}}$ без прерывания, возвращаем саму задачу ${\displaystyle (x,k)}$ в качестве ядра. Поскольку ${\displaystyle (x,k)}$ возвращается в качестве ядра для входа с${\displaystyle f(k)\cdot |x|^{c}>|x|^{c+1}}$, отсюда следует, что размер полученного таким образом ядра не превосходит ${\displaystyle \max\{|I_{yes}|,|I_{no}|,f(k)\}}$. Граница размера вычислима в предположениях фиксированно-параметрической разрешимости, что ${\displaystyle f(k)}$ вычислима.

• Вершинное покрытие: Задача о вершинном покрытии имеет ядра с максимум ${\displaystyle 2k}$ вершинами и ${\displaystyle O(k^{2})}$ рёбрами[8]. Более того, для любого ${\displaystyle \varepsilon >0}$ задача о вершинном покрытии не имеет ядер с ${\displaystyle O(k^{2-\varepsilon })}$ рёбрами, если только не {coNP} ${\displaystyle \subseteq }$ {NP/poly} [5]. Задачи о вершинном покрытии в ${\displaystyle d}$-однородных гиперграфах имеет ядра с ${\displaystyle O(k^{d})}$ рёбрами, если использовать лемму о подсолнечнике, и не имеет ядер размера ${\displaystyle O(k^{d-\varepsilon })}$, если только не coNP ${\displaystyle \subseteq }$NP/poly[5].
• Разрезающее циклы множество вершин: Задача о разрезающем циклы множестве вершин имеет ядра с ${\displaystyle 4k^{2}}$ вершинами и ${\displaystyle O(k^{2})}$ рёбрами[9]. Более того, задача не имеет ядер с ${\displaystyle O(k^{2-\varepsilon })}$ вершинами, если только не coNP${\displaystyle \subseteq }$NP/poly [5].
• k-Путь: Задача о k-путях заключается в решении, имеет ли заданный граф путь длиной не меньшей ${\displaystyle k}$. Эта задача имеет ядро размера, экспоненциально зависящего от ${\displaystyle k}$, и не имеет ядер размера, полиномиально зависящего от ${\displaystyle k}$, если только не coNP${\displaystyle \subseteq }$NP/poly[10].
• Двумерные задачи: Многие параметризованные версии двумерных задач имеют линейные ядра на планарных графах, и в более общем случае, на графах, не содержащих некоторые фиксированные графы в качестве минора[11].

• Итеративное сжатие, другая техника разработки фиксированно-параметрически разрешимых алгоритмов