Кернелизация

Эта статья о теории сложности. Информацию о методах машинного обучения с использованием ядра см. в разделе «Метод ядра» .

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

Кернелизация часто достигается путем применения набора правил сокращения, которые отсекают части экземпляра, с которыми легко работать. В параметризованной теории сложности часто можно доказать, что ядро ​​с гарантированными границами размера ядра (как функции некоторого параметра, связанного с задачей) может быть найдено за полиномиальное время . Когда это возможно, это приводит к гибкому алгоритму с фиксированными параметрами , время работы которого представляет собой сумму шага кернеризации (полиномиальное время) и времени (неполиномиального, но ограниченного параметром) для решения ядра. Действительно, каждая проблема, которая может быть решена с помощью управляемого алгоритма с фиксированным параметром, может быть решена с помощью алгоритма кернеризации этого типа. Это также верно для приблизительной кернеризации .

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

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

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

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

Хотя эта граница является приемлемой для фиксированного параметра, ее зависимость от параметра выше, чем хотелось бы. Более сложные процедуры кернеризации могут улучшить эту границу за счет поиска меньших ядер за счет увеличения времени выполнения этапа кернеризации. В примере вершинного покрытия известны алгоритмы кернеризации, которые создают ядра с не более чем $2k$ вершины.Один алгоритм, который достигает этой улучшенной границы, использует полуцелостность линейной программы релаксации вершинного покрытия, предложенную Немхаузером и Троттером. Другой алгоритм кернеризации, достигающий этой границы, основан на так называемом правиле сокращения короны и использует альтернативные аргументы пути. Самый известный в настоящее время алгоритм кернеризации с точки зрения количества вершин принадлежит Лампису (2011) и достигает $2k-c\log k$ вершины для любой фиксированной константы $c$.

В этой задаче невозможно найти ядро ​​размера $O(\log k)$, если только P = NP, поскольку такое ядро ​​приведет к полиномиальному алгоритму для NP-трудной задачи вершинного покрытия. Однако в этом случае можно доказать гораздо более строгие ограничения на размер ядра: если только coNP $\subseteq$ NP/poly ( теоретики сложности считают это маловероятным ), для каждого $\epsilon >0$ невозможно за полиномиальное время найти ядра с $O(k^{2-\epsilon })$ края. Для вершинного покрытия неизвестно, существуют ли ядра с $(2-\epsilon )k$ вершины для некоторых $\epsilon >0$ будет иметь какие-либо маловероятные последствия с точки зрения теории сложности.

Определение

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

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

В обозначениях Дауни и Феллоуз (1999) параметризованная задача представляет собой подмножество $L\subseteq \Sigma ^{*}\times \mathbb {N}$ описание проблемы решения .

Кернеризация для параметризованной задачи $L$ это алгоритм, который принимает экземпляр $(x,k)$ и отображает его во времени, полиномиальном по $|x|$ и $k$ к экземпляру $(x',k')$ такой, что

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

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

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

В обозначениях Flum & Grohe (2006 , стр. 4) параметризованная задача состоит из задачи решения $L\subseteq \Sigma ^{*}$ и функция $\kappa :\Sigma ^{*}\to \mathbb {N}$, параметризация. Параметр ​ экземпляра $x$ это число $\kappa (x)$.

Кернеризация для параметризованной задачи $L$ это алгоритм, который принимает экземпляр $x$ с параметром $k$ и сопоставляет его за полиномиальное время с экземпляром $y$ такой, что

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

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

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

Возможность ядра и управляемость с фиксированными параметрами эквивалентны.

Проблема разрешима с фиксированными параметрами тогда и только тогда, когда она кернеризуема и разрешима .

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

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

Больше примеров

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

Кернелизация для структурной параметризации

В то время как параметр $k$ в приведенных выше примерах выбран размер искомого решения, в этом нет необходимости. Также можно выбрать меру структурной сложности входных данных в качестве значения параметра, что приводит к так называемым структурным параметризациям. Этот подход полезен для случаев, размер решения которых велик, но для которых ограничена какая-либо другая мера сложности. Например, номер вершины обратной связи неориентированного графа. $G$ определяется как минимальная мощность множества вершин, удаление которых приводит к $G$ ациклический. Задача вершинного покрытия , параметризованная числом вершин обратной связи входного графа, имеет полиномиальную кернеризацию: Существует алгоритм с полиномиальным временем, который по заданному графу $G$ номер вершины обратной связи которого равен $k$, выводит график $G'$ на $O(k^{3})$ вершины такие, что минимальное покрытие вершин в $G'$ можно преобразовать в минимальное вершинное покрытие для $G$ за полиномиальное время. Таким образом, алгоритм кернеризации гарантирует, что экземпляры с небольшим числом вершин обратной связи $k$ сводятся к мелким экземплярам.

См. также

• Итеративное сжатие , другой метод проектирования управляемых алгоритмов с фиксированными параметрами.
• Приблизительная кернеризация , для задач оптимизации ядро ​​может потерять заданный коэффициент качества решения.

Ссылки

• Абу-Хзам, Фейсал Н.; Коллинз, Ребекка Л.; Товарищи, Майкл Р .; Лэнгстон, Майкл А .; Сатерс, В. Генри; Саймонс, Крис Т. (2004), Алгоритмы кернелизации для задачи вершинного покрытия: теория и эксперименты (PDF) , Университет Теннесси .
• Бодлендер, Ганс Л .; Дауни, Род Г .; Товарищи, Майкл Р .; Хермелин, Дэнни (2009), «О задачах без полиномиальных ядер», Журнал компьютерных и системных наук , 75 (8): 423–434, doi : 10.1016/j.jcss.2009.04.001 .
• Басс, Джонатан Ф.; Голдсмит, Джуди (1993), «Недетерминизм внутри $P^{*}$", SIAM Journal on Computing , 22 (3): 560–572, doi : 10.1137/0222038 , S2CID   43081484 .
• Чен, Цзянер; Кандж, Ияд А.; Цзя, Вейцзя (2001), «Покрытие вершин: дальнейшие наблюдения и дальнейшие улучшения» , Journal of Algorithms , 41 (2): 280–301, doi : 10.1006/jagm.2001.1186 , S2CID   13557005 .
• Делл, Хольгер; ван Мелькебек, Дитер (2010), «Выполнимость не допускает нетривиальной разреженности, если только иерархия полиномиального времени не рухнет» (PDF) , Труды 42-го симпозиума ACM по теории вычислений (STOC 2010) (PDF) , стр. 251–260, дои : 10.1145/1806689.1806725 , ISBN  978-1-4503-0050-6 , S2CID   1117711 .
• Дауни, РД ; Товарищи, MR (1999), Параметризованная сложность , Монографии по информатике, Springer, doi : 10.1007/978-1-4612-0515-9 , ISBN  0-387-94883-Х , МР   1656112 , S2CID   15271852 .
• Флум, Йорг; Гроэ, Мартин (2006), Параметризованная теория сложности , Springer, ISBN  978-3-540-29952-3 , получено 5 марта 2010 г.
• Фомин Федор Владимирович; Локштанов Даниил; Саураб, Сакет; Тиликос, Димитриос М. (2010), «Двумерность и ядра», Материалы 21-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2010) , стр. 503–510 .
• Янсен, член парламента от Барта; Бодлендер, Ханс Л. (2013), «Возврат к кернелизации вершинного покрытия - верхняя и нижняя границы уточненного параметра», Theory Comput. Сист. , 53 (2): 263–299, arXiv : 1012.4701 , doi : 10.1007/s00224-012-9393-4 ,
• Лампис, Майкл (2011), «Ядро порядка 2 k - c log k для вершинного покрытия», Information Processing Letters , 111 (23–24): 1089–1091, doi : 10.1016/j.ipl.2011.09.003 .
• Томассе, Стефан (2010), «A 4 k ² ядро для набора вершин обратной связи», ACM Transactions on Algorithms , 6 (2): 1–8, doi : 10.1145/1721837.1721848 , S2CID   7510317 .
• Нидермайер, Рольф (2006), Приглашение к алгоритмам с фиксированными параметрами , Oxford University Press, CiteSeerX   10.1.1.2.9618 , ISBN  0-19-856607-7 , заархивировано из оригинала 24 сентября 2008 г. , получено г. 1 июня 2017

Дальнейшее чтение

• Фомин Федор Владимирович; Локштанов Даниил; Саураб, Сакет; Зехави, Мейрав (2019), Кернелизация: теория параметризованной предварительной обработки , Cambridge University Press, стр. 528, номер домена : 10.1017/9781107415157 , ISBN  978-1107057760
• Нидермайер, Рольф (2006), Приглашение к алгоритмам с фиксированными параметрами , Oxford University Press, глава 7, ISBN  0-19-856607-7 , заархивировано из оригинала 29 сентября 2007 г. , получено 1 июня 2017 г.
• Сайган, Марк; Фомин Федор Владимирович; Ковалик, Лукаш; Локштанов Даниил; Маркс, Дэниел; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015), Параметризованные алгоритмы , Springer, главы 2 и 9, ISBN  978-3-319-21274-6