Jump to content

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

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

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

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

[ редактировать ]

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

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

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

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

В этой задаче невозможно найти ядро ​​размера , если только P = NP, поскольку такое ядро ​​приведет к полиномиальному алгоритму для NP-трудной задачи вершинного покрытия. Однако в этом случае можно доказать гораздо более строгие ограничения на размер ядра: если только coNP NP/poly ( теоретики сложности считают это маловероятным ), для каждого невозможно за полиномиальное время найти ядра с края. [4] Для вершинного покрытия неизвестно, существуют ли ядра с вершины для некоторых будет иметь какие-либо маловероятные последствия с точки зрения теории сложности.

Определение

[ редактировать ]

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

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

[ редактировать ]

В обозначениях Дауни и Феллоуз (1999) параметризованная задача представляет собой подмножество описание проблемы решения .

Кернеризация для параметризованной задачи это алгоритм, который принимает экземпляр и отображает его во времени, полиномиальном по и к экземпляру такой, что

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

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

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

[ редактировать ]

В обозначениях Flum & Grohe (2006 , стр. 4) параметризованная задача состоит из задачи решения и функция , параметризация. Параметр экземпляра это число .

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

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

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

Функция часто называют размеромядро. Если , сказано, что допускает полиномиальное ядро. Аналогично, для , задача допускает линейное ядро.

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

[ редактировать ]

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

То, что кернелизируемая и разрешимая проблема решается с фиксированными параметрами, можно видеть из приведенного выше определения:Сначала алгоритм кернеризации, который работает во времени. для некоторого c вызывается для генерации ядра размера .Затем ядро ​​решается с помощью алгоритма, который доказывает, что проблема разрешима.Общее время выполнения этой процедуры составляет , где — время работы алгоритма, используемого для решения ядер.С вычислимо, например, используя предположение, что является вычислимым и проверяет все возможные входные данные длины , это означает, что проблема разрешима при фиксированных параметрах.

Другое направление, заключающееся в том, что разрешимая задача с фиксированным параметром является ядром и разрешима, немного сложнее. Предположим, что вопрос нетривиален, то есть в языке существует хотя бы один экземпляр, называемый и по крайней мере один экземпляр, которого нет в языке, называемый ; в противном случае замена любого экземпляра пустой строкой является допустимой кернеризацией. Предположим также, что задача разрешима с фиксированными параметрами, т. е. у нее есть алгоритм, который работает не более чем за шаги по экземплярам , для некоторой константы и некоторая функция . Чтобы использовать ядро ​​для ввода, запустите этот алгоритм для данного ввода не более шаги. Если он заканчивается ответом, используйте этот ответ, чтобы выбрать либо или как ядро. Если вместо этого оно превышает ограничено количеством шагов без завершения, затем вернитесь себя как ядро. Потому что возвращается как ядро ​​только для входных данных с , то размер полученного таким образом ядра не превосходит . Эта граница размера вычислима на основании предположения, исходя из управляемости с фиксированными параметрами, что является вычислимым.

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

[ редактировать ]
  • Вершинное покрытие, параметризованное размером вершинного покрытия: Задача вершинного покрытия имеет ядра с не более чем вершины и края. [5] Более того, для любого , вершинное покрытие не имеет ядер с края, если только . [4] Проблемы вершинного покрытия в -однородные гиперграфы имеют ядра с ребер, используя лемму о подсолнечнике , и у него нет ядер размером пока не . [4]
  • Набор вершин обратной связи, параметризованный размером набора вершин обратной связи: Задача набора вершин обратной связи имеет ядра с вершины и края. [6] Кроме того, у него нет ядер с края, если только . [4]
  • : -путь Задача -пути состоит в том, чтобы решить, имеет ли данный граф путь длиной не менее . Эта задача имеет ядра экспоненциального размера в , и у него нет ядер полиномиального размера по пока не . [7]
  • Двумерные задачи. Многие параметризованные версии двумерных задач имеют линейные ядра на плоских графах и, в более общем смысле, на графах, исключая некоторый фиксированный граф в качестве второстепенного . [8]

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

[ редактировать ]

В то время как параметр в приведенных выше примерах выбран размер искомого решения, в этом нет необходимости. Также можно выбрать меру структурной сложности входных данных в качестве значения параметра, что приводит к так называемым структурным параметризациям. Этот подход полезен для случаев, размер решения которых велик, но для которых ограничена какая-либо другая мера сложности. Например, номер вершины обратной связи неориентированного графа. определяется как минимальная мощность множества вершин, удаление которых приводит к ациклический. Задача вершинного покрытия , параметризованная числом вершин обратной связи входного графа, имеет полиномиальную кернеризацию: [9] Существует алгоритм с полиномиальным временем, который по заданному графу номер вершины обратной связи которого равен , выводит график на вершины такие, что минимальное покрытие вершин в можно преобразовать в минимальное вершинное покрытие для за полиномиальное время. Таким образом, алгоритм кернеризации гарантирует, что экземпляры с небольшим числом вершин обратной связи сводятся к мелким экземплярам.

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. Это неопубликованное наблюдение подтверждается в статье Buss & Goldsmith (1993).
  2. ^ Флум и Гроэ (2006)
  3. ^ Flum & Grohe (2006) дают ядро, основанное на уменьшении кроны, которое имеет вершины. Vertexbound — это немного более сложный и фольклорный подход.
  4. ^ Jump up to: а б с д Делл и ван Мелкебек (2010)
  5. ^ Чен, Кандж и Цзя (2001)
  6. ^ Томассе (2010)
  7. ^ Бодлендер и др. (2009)
  8. ^ Fomin et al. (2010)
  9. ^ Янсен и Бодлендер (2013)

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

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e39d300992dcec777e6b96cab796a38a__1717310640
URL1:https://arc.ask3.ru/arc/aa/e3/8a/e39d300992dcec777e6b96cab796a38a.html
Заголовок, (Title) документа по адресу, URL1:
Kernelization - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)