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

Параметрическая редукция — это техника для разработки эффективных алгоритмов, которые достигают своей эффективности путём препроцессорного шага, в котором вход алгоритма заменяется на меньший вход, называемый «ядром». Результат решения задачи на ядре должен быть либо тем же самым, что и при исходных данных, либо выход решения для ядра должен легко преобразовываться в желаемый выход исходной задачи.

Параметрическая редукция часто достигается путём применения набора правил редукции, которые отсекают часть конкретной задачи, с которой легко справиться. В теории параметризованной сложности^[англ.] часто можно доказать, что ядро с гарантированными границами, зависящими от размера ядра (как функции некоторых параметров, связанных с задачей), могут быть найдены за полиномиальное время. Если это возможно, результатом будет фиксированно-параметрически разрешимый^[англ.] алгоритм, время работы которого является суммой шага (полиномиального времени) параметрической редукции и (неполиномиального, но ограниченного параметром) времени для решения ядра. Более того, любая задача, которую можно решить фиксированно-параметрически разрешимым алгоритмом, может быть решена алгоритмом параметрической редукции этого типа.

Пример: покрытие вершин

Стандартный пример алгоритма параметрической редукции — параметрическая редукция задачи о вершинном покрытии С. Басса[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].

Определение

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

Обозначение Дауни — Феллоуза

В обозначениях Дауни — Феллоуза[6] параметризованная задача — это подмножество ${\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }$, описывающее задачу разрешимости.

Параметрическая редукция параметризованной задачи ${\displaystyle L}$ — это алгоритм, который берёт представителя ${\displaystyle (x,k)}$ и отображает его за время, полиномиально зависящее от ${\displaystyle |x|}$ и ${\displaystyle k}$, в представителя ${\displaystyle (x',k')}$, так что

• ${\displaystyle (x,k)}$ входит в ${\displaystyle L}$ тогда и только тогда, когда ${\displaystyle (x',k')}$ входит ${\displaystyle L}$,
• размер ${\displaystyle x'}$ ограничен вычислимой функцией ${\displaystyle f}$ от ${\displaystyle k}$
• ${\displaystyle k'}$ ограничено вычислимой функцией от ${\displaystyle k}$.

Выход ${\displaystyle (x',k')}$ параметрической редукции называется ядром. В этом общем контексте размер строки ${\displaystyle x'}$ часто называется её длиной. Некоторые авторы предпочитают число вершин или число рёбер в качестве размера в контексте задач на графах.

Обозначение Флама — Гроэ

В обозначениях Флама — Гроэ[7] параметризованная задача состоит из задачи приятия решения ${\displaystyle L\subseteq \Sigma ^{*}}$ и функции ${\displaystyle \kappa :\Sigma ^{*}\to \mathbb {N} }$, собственно параметризации. Параметр представителя задачи ${\displaystyle x}$ — число ${\displaystyle \kappa (x)}$.

Параметрическая редукция для параметризованной задачи ${\displaystyle L}$ является алгоритмом, который берёт представителя ${\displaystyle x}$ с параметром ${\displaystyle k}$ и отображает его за полиномиальное время в представителя ${\displaystyle y}$ так, что

• ${\displaystyle x}$ входит в ${\displaystyle L}$ тогда и только тогда, когда ${\displaystyle y}$ входит в ${\displaystyle L}$
• размер ${\displaystyle y}$ ограничен вычислимой функцией ${\displaystyle f}$ от ${\displaystyle k}$.

Заметим, что в этих обозначениях граница размера ${\displaystyle y}$ подразумевает, что параметр ${\displaystyle y}$ также ограничен функцией от ${\displaystyle k}$.

Функцию ${\displaystyle f}$ часто называют размером ядра. Если ${\displaystyle f=k^{O(1)}}$ говорят, что ${\displaystyle L}$ допускает полиномиальное ядро. Подобным образом для ${\displaystyle f={O(k)}}$ задача допускает линейное ядро.

Параметрическая редуцируемость и фиксированно-параметрическая разрешимость эквивалентны

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

То, что параметрически редуцируемая и разрешимая задача является фиксированно-параметрически разрешимой, можно видеть из определения выше: алгоритм параметрической редукции, который работает за время ${\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].

См. также

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

Примечания

1. Это неопубликованное наблюдение было констатировано в статье Басса и Голдсмита (Buss, Goldsmith 1993)
2. Flum, Grohe, 2006.
3. Флам и Гроэ (Flum, Grohe 2006) дают ядро, основанное на коронной редукции, которое имеет ${\displaystyle 3k}$ вершин. Граница ${\displaystyle 2k}$ вершин чуть более сложна.
4. Lampis, 2011.
5. Dell, van Melkebeek, 2010.
6. Downey, Fellows, 1999.
7. Flum, Grohe, 2006, p. 4.
8. Chen, Kanj, Jia, 2001.
9. Thomassé, 2010.
10. Bodlaender, Downey, Fellows, Hermelin, 2009.
11. Fomin, Lokshtanov, Saurabh, Thilikos, 2010.

Литература

• Faisal N. Abu-Khzam, Rebecca L. Collins, Michael R. Fellows, Michael A. Langston, W. Henry Suters, Chris T. Symons. Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments. — University of Tennessee, 2004.
• Hans L. Bodlaender, Rod G. Downey, Michael R. Fellows, Danny Hermelin. On problems without polynomial kernels // Journal of Computer and System Sciences. — 2009. — Т. 75, вып. 8. — С. 423—434. — doi:10.1016/j.jcss.2009.04.001.
• Jonathan F. Buss, Judy Goldsmith. Nondeterminism within P // SIAM Journal on Computing. — 1993. — Т. 22, вып. 3. — С. 560—572. — doi:10.1137/0222038.
• Jianer Chen, Iyad A. Kanj, Weijia Jia. Vertex cover: Further observations and further improvements // Journal of Algorithms. — 2001. — Т. 41, вып. 2. — С. 280—301. — doi:10.1006/jagm.2001.1186.
• Holger Dell, Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses // Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010). — 2010. — С. 251—260. — doi:10.1145/1806689.1806725.
• R. G. Downey, M. R. Fellows. Parameterized Complexity. — Springer, 1999. — ISBN 0-387-94883-X. — doi:10.1007/978-1-4612-0515-9.
• Jörg Flum, Martin Grohe. Parameterized Complexity Theory. — Springer, 2006. — ISBN 978-3-540-29952-3.
• Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos. Bidimensionality and kernels // Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). — 2010. — С. 503—510.
• Michael Lampis. A kernel of order 2k − c log k for vertex cover // Information Processing Letters. — 2011. — Т. 111, вып. 23—24. — С. 1089—1091. — doi:10.1016/j.ipl.2011.09.003.
• Stéphan Thomassé. A 4k^2 kernel for feedback vertex set // ACM Transactions on Algorithms. — 2010. — Т. 6, вып. 2.
• Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms (англ.). — Oxford University Press, 2006. — ISBN 0-19-856607-7..