Ядеризация

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

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

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

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

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}$

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

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

Определение

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

Нотация Дауни–Феллоуза

В обозначении Дауни и Феллоуз (1999) параметризованная задача — это подмножество, описывающее задачу принятия решения . ${\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'}$

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

В нотации Флума и Гроэ (2006, стр. 4) параметризованная задача состоит из задачи принятия решения и функции , параметризации. Параметром экземпляра является число . ${\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)}}$

Ядерность и трактуемость с фиксированными параметрами эквивалентны

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

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

Еще примеры

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

Ядеризация для структурных параметризаций

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

Смотрите также

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

Примечания

1. Это неопубликованное наблюдение подтверждено в статье Басса и Голдсмита (1993)
2. Флум и Гроэ (2006)
3. Флум и Гроэ (2006) дают ядро, основанное на редукции короны, которая имеет вершины. Граница вершин немного сложнее и фольклорнее. ${\displaystyle 3k}$ ${\displaystyle 2k}$
4. Делл и ван Мелкебек (2010)
5. Чэнь, Кань и Цзя (2001)
6. Томассе (2010)
7. Бодлендер и др. (2009)
8. Фомин и др. (2010)
9. Янсен и Бодлендер (2013)

Ссылки

• Абу-Хзам, Фейсал Н.; Коллинз, Ребекка Л.; Феллоуз, Майкл Р .; Лэнгстон, Майкл А .; Сутерс, У. Генри; Саймонс, Крис Т. (2004), Алгоритмы кернелизации для задачи покрытия вершин: теория и эксперименты (PDF) , Университет Теннесси.
• Bodlaender, Hans L .; Downey, Rod G .; Fellows, Michael R .; Hermelin, Danny (2009), «О проблемах без полиномиальных ядер», Journal of Computer and System Sciences , 75 (8): 423–434, doi : 10.1016/j.jcss.2009.04.001.
• Басс, Джонатан Ф.; Голдсмит, Джуди (1993), «Недетерминизм внутри », SIAM Journal on Computing , 22 (3): 560–572, doi :10.1137/0222038, S2CID  43081484 ${\displaystyle P^{*}}$.
• Чен, Цзянер; Кандж, Ияд А.; Цзя, Вейцзя (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, doi :10.1145/1806689.1806725, ISBN 978-1-4503-0050-6, S2CID  1117711.
• Дауни, Р. Г.; Феллоуз , М. Р. (1999), Параметризованная сложность , Монографии по информатике, Springer, doi : 10.1007/978-1-4612-0515-9, ISBN 0-387-94883-X, MR  1656112, S2CID  15271852.
• Флум, Йорг; Гроэ, Мартин (2006), Параметризованная теория сложности, Springer, ISBN 978-3-540-29952-3, получено 2010-03-05.
• Фомин, Федор В.; Локштанов, Даниэль; Саурабх, Сакет; Тиликос, Димитриос М. (2010), «Двумерность и ядра», Труды 21-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2010) , стр. 503–510.
• Янсен, Барт МП; Бодлендер, Ханс Л. (2013), «Повторный взгляд на кернелизацию вершинного покрытия — верхние и нижние границы для уточненного параметра», Theory Comput. Syst. , 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), « Ядро 4k2 для ^набора вершин обратной связи», 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, архивировано из оригинала 2008-09-24 , извлечено 2017-06-01.

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

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