Хабрахабр

Как решать NP-трудные задачи с помощью параметризованных алгоритмов

Научно-исследовательская работа, пожалуй, самая интересная часть нашего обучения. Идея в том, чтобы ещё в университете попробовать себя в выбранном направлении. Например, студенты с направлений Software Engineering и Machine Learning часто идут делать НИРы в компании (в основном, JetBrains или Яндекс, но не только).

В рамках работы я изучил и реализовал на практике подходы к решению одной из самых известных NP-трудных задач: задаче о вершинном покрытии. В этом посте я расскажу о своём проекте по направлению Computer Science.

Я постараюсь ввести вас в курс дела, рассказать несколько простых параметризованных алгоритмов и описать один мощный метод, который очень мне помог. Сейчас очень быстро развивается интересный подход к NP-трудным задачам — параметризованные алгоритмы. Свой результаты я представил на соревновании PACE Challenge: по итогам открытых тестов мое решение занимает третье место, а окончательные результаты будут известны 1 июля.

О себе

Меня зовут Василий Алфёров, я сейчас заканчиваю третий курс НИУ ВШЭ — Санкт-Петербург. Алгоритмами я увлекаюсь ещё со школьных времён, когда учился в московской 179 школе и успешно участвовал в олимпиадах по информатике.

Конечное количество специалистов по параметризованным алгоритмам заходят в бар...

Пример взят из книги «Parameterized algorithms»

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

У вас есть список из n человек, которые придут сегодня вечером в бар. Так как город у вас маленький, вы точно знаете, какие пары посетителей с большой вероятностью передерутся, если попадут в бар вместе. В то же время ваше начальство не хочет терять прибыль и будет недовольно, если вы не пустите в бар больше чем k человек. Вы решаете не пустить в бар каких-нибудь горожан таким образом, чтобы никто не подрался.

Вы могли знать её как Vertex Cover, или как задачу о вершинном покрытии. К сожалению, задача, стоящая перед вами — классическая NP-трудная задача. Если быть точным, то недоказанная и довольно сильная гипотеза ETH (Exponential Time Hypothesis) говорит, что эта задача не решается за время $2^$, то есть что заметно лучше полного перебора ничего нельзя придумать. Для таких задач в общем случае неизвестны алгоритмы, работающие за приемлемое время. Тогда полный перебор составит $2^{1000}$ вариантов, что есть примерно $10^{301}$ — безумно много. Например, пусть к вам в бар собирается прийти n = 1000 человек. Это уже лучше, но всё равно не досчитается за день даже на мощном кластере.

Чтобы исключить вероятность драки при такой конфигурации натянутых отношений между посетителями бара, нужно не впускать Боба, Дэниела и Фёдора. К счастью, ваше руководство поставило вам ограничение k = 10, так что количество комбинаций, которые вам нужно перебрать, гораздо меньше: количество подмножеств из десяти элементов равно $2,63⋅10^{23}$. Решения, при котором за бортом останутся всего двое, не существует.

Рассмотрим другие варианты. Значит ли это, что пора сдаться и впустить всех? Если кто-то может подраться хотя бы с k + 1 другим человеком, то его точно пускать нельзя — иначе придётся не пустить всех k + 1 горожан, с кем он может подраться, что уже точно расстроит руководство. Ну, например, можно не впустить только тех, кто вероятно подерется с очень большим количеством народу.

Тогда все остальные могут подраться не более чем с k людьми. Пусть вы выкинули всех, кого могли, по этому принципу. Значит, если всего больше чем $2k^2$ человек участвует хотя бы в одном конфликте, то вы точно не сможете предотвратить их все. Выкинув из них k человек, вы можете предотвратить не более чем $k^2$ конфликтов. Их примерно $2,24⋅10^{16}$, а такое количество операций уже можно перебрать на кластере. Так как, понятное дело, совсем неконфликтных людей вы обязательно пустите, то вам нужно перебрать все подмножества размером десять из двухсот людей.

На самом деле, их тоже можно впустить, закрыв двери перед их оппонентом. Если можно безопасно взять совсем не конфликтных личностей, то что про тех, кто участвует лишь в одном конфликте? Тем более нам бессмысленно не пускать обоих. И правда, если Алиса конфликтует только с Бобом, то если мы впустим из них двоих Алису, мы не проиграем: у Боба могут быть другие конфликты, а у Алисы их точно нет. Значит, остаётся перебрать всего лишь $1,73⋅10^{13}$ вариантов, что вполне может посчитаться за полдня на ноутбуке. После таких операций остаётся не более $k^2$ гостей с нерешённной судьбой: всего у нас $k^2$ конфликтов, в каждом двое участников и каждый участвует хотя бы в двух.

Заметим, что нам обязательно нужно решить все споры, то есть из каждой конфликтующей пары выбрать хотя бы одного человека, которого мы не впустим. На самом деле, простыми рассуждениями можно добиться еще более привлекательных условий. Поскольку мы на каждом шаге кого-то выкидываем, дерево рекурсии такого алгоритма — бинарное дерево глубины k, поэтому суммарно алгоритм работает за $2^k⋅(n+m)$, где n — количество вершин, а m — количество ребер. Рассмотрим такой алгоритм: возьмём любой конфликт, из которого удалим одного участника и рекурсивно запустимся от остатка, потом удалим другого и тоже рекурсивно запустимся. На нашем примере это порядка десяти миллионов, что за доли секунды посчитается не только на ноутбуке, но даже на мобильном телефоне.

Параметризованные алгоритмы — это алгоритмы, которые работают за время f(k) poly(n), где p — полином, f — произвольная вычислимая функция, а k — какой-то параметр, который, вполне возможно, будет много меньше размера задачи. Приведённый выше пример — это пример параметризованного алгоритма.

Кернелизация — это уменьшение размера задачи до значения, ограниченного функцией от параметра. Все рассуждения до этого алгоритма приводят пример кернелизации — одной из общих техник для создания параметризованных алгоритмов. Так, простыми рассуждениями про степени вершин мы получили квадратичное ядро для задачи Vertex Cover, параметризованной размером ответа. Полученную задачу часто называют ядром. Существуют и другие параметры, которые можно выбрать для этой задачи (например, Vertex Cover Above LP), но мы будем обсуждать именно такой параметр.

Pace Challenge

Соревнование PACE Challenge (The Parameterized Algorithms and Computational Experiments Challenge) зародилось в 2015 году, чтобы установить связь между параметризованными алгоритмами и подходами, используемыми на практике для решения вычислительных задач. Первые три соревнования были посвящены поиску древесной ширины графа (Treewidth), поиску дерева Штейнера (Steiner Tree) и поиску множества вершин, разрезающего циклы (Feedback Vertex Set). В этом году одной из задач, в которых можно было попробовать свои силы, была описанная выше задача о вершинном покрытии.

Если верить предварительным данным, то в этом году только в соревновании по решению задачи вершинного покрытия приняло участие 24 команды. Соревнование с каждым годом набирает популярность. У команд есть возможность изучить литературу, придумать свою оригинальную идею и попытаться ее реализовать. Стоит отметить, что соревнование длится не несколько часов и даже не неделю, а несколько месяцев. Идеи самых эффективных решений и награждение победителей пройдет совместно с конференцией IPEC (International Symposium on Parameterized and Exact Computation) в рамках самого большого ежегодного алгоритмического собрания в Европе ALGO. По сути, данное соревнование представляет из себя исследовательскую работу. Более подробную информацию про само соревнование можно найти на сайте, а результаты прошлых лет лежат тут.

Схема решения

Чтобы справиться с задачей о вершинном покрытии, я попробовал применить параметризованные алгоритмы. Они, как правило, состоят из двух частей: правил упрощения (которые в идеале приводят к кернелизации) и правил расщепления. Правила упрощения — это предобработка входа за полиномиальное время. Цель применения таких правил — сведение задачи к эквивалентной задаче меньшего размера. Правила упрощения — это наиболее затратная часть алгоритма, и применение именно этой части ведет к общему времени работы $c^k⋅poly(n)$ вместо простого полиномиального времени. В нашем случае правила расщепления основаны на том, что для каждой вершины нужно взять в ответ либо её, либо её соседа.

Это мы называем расщепиться (бранчиться) по этой вершине. Общая схема такая: применяем правила упрощения, потом выбираем какую-то вершину, и делаем два рекурсивных вызова: в первом мы берём её в ответ, а в другом мы берём всех её соседей.

В эту схему будет внесено ровно одно дополнение в следующем параграфе.

Идеи для правил расщепления (бранчинга)

Давайте обсудим, как выбрать вершину, по которой будет происходить расщепление.
Основная идея очень жадная в алгоритмическом смысле: давайте возьмём вершину максимальной степени и расщепимся именно по ней. Почему кажется, что так лучше? Потому что во второй ветке рекурсивного вызова мы таким образом уберём очень много вершин. Можно рассчитывать, что останется маленький граф и на нём мы отработаем быстро.

Но, например, плохо работает для кубических графов (то есть графов, степень каждой вершины которых равна трём).
Есть ещё одна идея, основанная на достаточно простой мысли: если граф несвязный, задачу на его компонентах связности можно решать независимо, объединив ответы в конце. Этот подход с уже обсуждёнными простыми техниками кернелизации показывает себя неплохо, решает какие-то тесты размером в несколько тысяч вершин. А для ускорения бранчинга нужно превратить связный граф в несвязный. Это, кстати, и есть небольшая обещанная модификация в схеме, которая существенно ускорит решение: раньше в таком случае мы работали за произведение времён подсчёта ответов компонент, а теперь работаем за сумму.

Если в графе есть точка сочленения, нужно побранчиться именно по ней. Как это сделать? Найти в графе все точки сочленения можно классическим алгоритмом за линейное время. Точка сочленения — это такая вершина, при удалении которой граф теряет связность. Такой подход заметно ускоряет бранчинг.

При удалении любой из выделенных вершин граф распадётся на компоненты связности.

Например, искать в графе небольшие вершинные разрезы и проводить расщепление по вершинам из него. Это мы сделаем, но хочется большего. В PACE Challenge типичный размер графа — несколько тысяч вершин. Самый эффективный известный мне способ найти минимальный глобальный вершинный разрез — воспользоваться деревом Гомори-Ху, которое строится за кубическое время. Получается, что решить задачу за отведенное время просто невозможно. При таком раскладе в каждой вершине дерева рекурсии нужно выполнить миллиарды операций.

Минимальный вершинный разрез между парой вершин можно найти любым алгоритмом, строящим максимальный поток. Попробуем оптимизировать решение. У меня есть подозрение, что теоретически можно доказать оценку на время работы $mn^{1/2}$, что уже вполне приемлемо. Можно напустить на такую сеть алгоритм Диница, на практике он работает очень быстро.

К сожалению, на открытых тестах PACE Challenge это дало плохие результаты. Я пробовал несколько раз искать разрезы между парами случайных вершин и брать из них самый сбалансированный. После алгоритма, пытающегося найти разрез таким образом, оставались графы большего размера. Я сравнивал с алгоритмом, щепившимся по вершинам максимальной степени, запуская их с ограничением на глубину спуска. Это связано с тем, что разрезы получались очень несбаллансированными: удалив 5-10 вершин, удавалось отщеплять всего лишь 15-20.

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

Как применять правила упрощения

У нас уже есть идеи кернелизации. Напомню:

  1. Если есть изолированная вершина, удалить её.
  2. Если есть вершина степени 1, удалить её и взять её соседа в ответ.
  3. Если есть вершина степени хотя бы k + 1, взять её в ответ.

С первыми двумя всё понятно, с третьей есть одна хитрость. Если в шуточной задаче про бар нам было дано ограничение сверху на k, то в PACE Challenge надо просто найти вершинное покрытие минимального размера. Это типичное преобразование задач поиска (Search Problem) в задачи решения (Decision Problem), часто между двумя видами задач не делают разницы. На практике, если мы пишем решатель задачи о вершинном покрытии, разница может быть. Например, как в третьем пункте.

Первый подход называется Iterative Deepening. С точки зрения реализации, можно поступить двумя способами. Если мы нашли какой-то ответ, он гарантированно оптимальный, иначе же можно увеличить это ограничение на единичку и снова запуститься. Он состоит в следующем: мы можем начать с какого-то разумного ограничения снизу на ответ, и дальше запускать наш алгоритм, используя это ограничение как ограничение на ответ сверху, не спускаясь в рекурсии ниже, чем на это ограничение.

Другой подход — хранить какой-то текущий оптимальный ответ и искать ответ меньшего размера, при нахождении изменяя этот параметр k для большего отсечения лишних веток в поиске.

Проведя несколько ночных экспериментов, я остановился на комбинации этих двух способов: сначала я запускаю свой алгоритм с каким-то ограничением на глубину поиска (подбирая её так, чтобы это заняло ничтожное время по сравнению с основным решением) и использую лучшее найденное решение как ограничение сверху на ответ — то есть на то самое k.

Вершины степени 2

С вершинами степени 0 и 1 мы разобрались. Оказывается, что так можно сделать и с вершинами степени 2, но для этого от графа потребуются более сложные операции.

Назовём вершину степени 2 вершиной v, а её соседей — вершинами x и y. Чтобы это объяснить, надо как-то обозначить вершины. Дальше у нас будет два случая.

  1. Когда x и y — соседи. Тогда можно взять в ответ x и y, а v удалить. И правда, из этого треугольника хотя бы две вершины нужно взять в ответ и мы точно не проиграем, если возьмём x и y: у них, вероятно, есть ещё соседи, а у v их нет.
  2. Когда x и y — не соседи. Тогда утверждается, что все три вершины можно склеить в одну. Идея в том, что в таком случае есть оптимальный ответ, в который мы возьмём либо v, либо обе вершины x и y. Причём в первом случае нам придётся взять в ответ всех соседей x и y, а во втором не обязательно. Это в точности соответствует случаям, когда мы не берём склеенную вершину в ответ и когда берём. Осталось лишь заметить, что в обоих случаях ответ от такой операции уменьшается на единицу.

Склейка вершин — сложная операция, нужно скопировать списки соседей. Стоит заметить, что такой подход за честное линейное время довольно сложно аккуратно реализовать. Я остановился на поиске целых путей из вершин степени 2 и разборе кучи частных случаев, вроде циклов из таких вершин или из всех таких вершин кроме одной. Если это сделать неаккуратно, можно получить асимптотически неоптимальное время работы (например, если после каждой склейки копировать много рёбер).

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

Линейное ядро

Наконец, самая интересная часть ядра.

Для этого нужно воспользоваться алгоритмом Хопкрофта-Карпа для того, чтобы найти там максимальное паросочетание, а потом воспользоваться теоремой Кёнига-Эгервари. Для начала вспомним, что в двудольных графах минимальное вершинное покрытие можно искать за $mn^{1/2}$.

Полученный граф будет двудольным. Идея линейного ядра такова: сначала раздвоим граф, то есть вместо каждой вершины v заведём две вершины $v_L$ и $v_R$, а вместо каждого ребра u — v заведём два ребра $u_L — v_R$ и $v_L — u_R$. Какие-то вершины исходного графа попадут туда дважды, какие-то только один раз, а какие-то — ни разу. Найдём в нём минимальное вершинное покрытие. Более того, она говорит, что из оставшихся вершин (тех, что попали однажды) нужно взять в ответ хотя бы половину. Теорема Немхаузера-Троттера утверждает, что в таком случае можно удалить вершины, которые не попали ни разу и взять в ответ те, которые попали дважды.

И правда, если в остатке ответ — хотя бы половина всех вершин, то всего вершин там не больше чем 2k. Только что мы научились оставлять в графе не больше чем 2k вершин.

Понятно, что построенное таким образом ядро зависит от того, какое именно минимальное вершинное покрытие в двудольном графе мы взяли. Здесь мне удалось сделать небольшой шаг вперёд. Раньше это умели делать лишь за время $mn^{3/2}$. Хочется взять такое, чтобы количество оставшихся вершин было минимальным. Я же придумал реализацию этого алгоритма за время $mn^{1/2}$, таким образом, это ядро можно искать на графах в сотни тысяч вершин на каждом этапе бранчинга.

Результат

Практика показывает, что моё решение хорошо работает на тестах в несколько сотен вершин и несколько тысяч рёбер. На таких тестах вполне можно ожидать, что решение найдётся за полчаса. Вероятность нахождения ответа за приемлемое время в принципе возрастает если в графе достаточно много вершин большой степени, например степени 10 и выше.

Судя по представленной там табличке, моё решение на открытых тестах занимает третье место из двадцати с большим отрывом от второго. Для участия в соревновании решения нужно было отправить на optil.io. Если быть совсем честным, то не совсем понятно, как будут оцениваться решения на самом соревновании: например, моё решение проходит меньше тестов, чем решение на четвёртом месте, но на тех, которые проходит, работает быстрее.

Результаты на закрытых тестах станут известны первого июля.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть