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

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

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

Пример: крышка вершины [ править ]

Стандартный пример для алгоритма керриризации - это керилизация проблемы вершинного покрытия, предложенная С. Буссом. ^[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 О (2 ^ {2k ^ {2}} + п + м)}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle m}$

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

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

Определение [ править ]

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

Обозначение Дауни-Феллоуз [ править ]

В обозначениях Downey & Fellows (1999) , A параметризованная проблема является подмножеством , описывающее задачу принятия решения .${\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }$

Kernelization для параметризованных задач является алгоритмом , который принимает экземпляр и отображает его в полиномиальное время в и к примеру такому , что${\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)}$

Kernelization для параметризованных задач является алгоритмом , который принимает экземпляр с параметром и отображает его в полиномиальное время к экземпляру такому , что${\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}}}$
• k-путь: Задача k-пути состоит в том, чтобы решить, имеет ли данный граф путь как минимум длины . В этой задаче есть ядра экспоненциального размера по in и нет ядер с полиномиальным размером от if . ^[7]${\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}$

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Абу-Хзам, Фейсал Н .; Коллинз, Ребекка Л .; Товарищи, Майкл Р .; Лэнгстон, Майкл А .; Сутерс, У. Генри; Саймонс, Крис Т. (2004), Алгоритмы кернелизации для проблемы вершинного покрытия: теория и эксперименты (PDF) , Университет Теннесси.
• Bodlaender, Hans L .; Дауни, Род Г .; Товарищи, Майкл Р .; Hermelin, Дэнни (2009), "О задачах без полиномиальных ядер", журнал компьютерных и системных наук , 75 (8): 423-434, DOI : 10.1016 / j.jcss.2009.04.001.
• Басс, Джонатан Ф .; Голдсмит, Джуди (1993), "Недетерминизм в пределах " P ∗ {\displaystyle P^{*}} , SIAM журнал по вычислениям , 22 (3): 560-572, DOI : 10,1137 / 0222038 , S2CID  43081484.
• Чен, Цзианэр; Kanj, Iyad A .; Цзя, Weijia (2001), «Покрытие вершины: дальнейшие наблюдения и дальнейшие улучшения» , журнал алгоритмов , 41 (2): 280–301, doi : 10.1006 / jagm.2001.1186  , S2CID 13557005.
• Делл, Хольгер; ван Мелкебек, Дитер (2010), «Выполнимость не допускает нетривиального разбиения, если иерархия полиномиального времени не разрушается» (PDF) , Труды 42-го симпозиума ACM по теории вычислений (STOC 2010) , стр. 251–260, doi : 10.1145 /1806689.1806725 , S2CID  1117711.
• Дауни, Р.Г .; Стипендиаты, MR (1999), параметризованная сложность , монографии в области компьютерных наук, Springer, DOI : 10.1007 / 978-1-4612-0515-9 , ISBN 0-387-94883-X, Руководство по ремонту  1656112 , S2CID  15271852.
• Флум, Йорг; Grohe, Мартин (2006), параметризованная теория сложности , Springer, ISBN 978-3-540-29952-3, дата обращения 05.03.2010.
• Фомин, Федор В .; Локштанов Даниил; Саураб, Сакет; Тиликос, Димитриос М. (2010), «Двумерность и ядра», Труды 21-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2010) , стр. 503–510.
• Янсен, член парламента Барта; Бодлендер, Ханс Л. (2013), «Возвращение к ядру вершинного покрытия - верхняя и нижняя границы для уточненного параметра», Theory Comput. Syst. , 53 (2): 263-299, DOI : 10.1007 / s00224-012-9393-4,
• Лэмпис, Майкл (2011), «Ядро порядка 2 k  -  c  log  k для вершинного покрытия», Письма об обработке информации , 111 (23–24): 1089–1091, DOI : 10.1016 / j.ipl.2011.09.003.
• Thomasse, Stéphan (2010), "A 4 к ² ядра для множества вершин обратной", ACM Сделки по алгоритмам , 6 (2): 1-8, DOI : 10,1145 / 1721837,1721848 , S2CID  7510317.
• Нидермайер, Рольф (2006), Приглашение к использованию алгоритмов с фиксированными параметрами , Oxford University Press, ISBN 0-19-856607-7, заархивировано из оригинала 24 сентября 2008 г. , получено 01 июня 2017 г..

Дальнейшее чтение [ править ]

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