Параметризации “above-guarantee”: идеи и задачи

Во многих NP-трудных задачах оптимизации можно легко построить решение некоторого качества. Например, в любом графе с m рёбрами существует разрез, содержащий хотя бы m/2 рёбер. Насколько сложно найти разрез размера хотя бы m/2+k? Можно ли построить алгоритм, время работы которого определяется величиной этого превышения?

Такие вопросы лежат в основе параметризации выше гарантии (above guarantee): параметром становится превышение k над нижней оценкой на размер оптимального решения, а целью является разработка параметризованных алгоритмов со временем работы f(k) * poly(n). Этот подход позволяет по-новому взглянуть на классические задачи и поставить новые алгоритмические вопросы.

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

В докладе мы познакомимся с основными идеями этого подхода на разнообразных примерах задач о максимальном разрезе (Max-Cut), булевой выполнимости Max-SAT, поиска длинного пути (Longest Path) и покрытия путями (Path Cover), независимого множества (Independent Set) и др. Мы обсудим, откуда берутся естественные гарантии, как их выбор влияет на сложность задачи и какие структурные идеи влекут эффективные алгоритмы. Кроме того, мы увидим и несколько открытых вопросов в этой области.

Доклад будет обзорным; необходимые понятия параметризованной сложности будут введены по ходу изложения: слушателям будет достаточно базовых знаний алгоритмов и теории графов.