Курсель и двумерность: когда структура обещает алгоритм

Если проверяешь зависимость от формулы и ширины отдельно - переходи к «Теперь сам».

Как думаешь: «время линейно» означает пригодность для миллиона вершин?

Есть утверждение: любую задачу некоторого логического вида на графе ширины пять можно проверить за линейное время. Можно ли сразу заменить специализированную динамику универсальным решателем? Нет: коэффициент перед n зависит и от логической формулы. Очень длинное условие или большая ширина могут сделать универсальное построение непрактичным.

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

На что это похоже

Представь конструктор отчётов, где запрос записывается на специальном языке, а данные имеют известную древовидную структуру. Универсальный механизм компилирует запрос в автомат и проходит дерево. Размер автомата зависит от самого запроса. Маленькая таблица данных не спасает от гигантского скомпилированного условия; зато для одного фиксированного условия дальнейший проход может расти лишь пропорционально данным.

Механизм: что разрешено говорить в MSO₂

В обычной логике первого порядка переменные обозначают вершины или рёбра. Можно писать равенство, смежность вершин или инцидентность вершины ребру, соединять условия «и», «или», «не» и использовать «существует» и «для всех». В монадической логике второго порядка добавляются переменные, обозначающие множества. Слово «монадическая» означает, что квантифицируют наборы отдельных объектов, а не произвольные отношения между парами. Версия MSO₁ разрешает множества вершин; MSO₂ также множества рёбер.

Например, трёхцветность выражается существованием трёх множеств вершин R,G,B. Каждая вершина принадлежит ровно одному, и у каждого ребра концы принадлежат разным множествам. Длина этой формулы постоянна: в неё не выписывают все вершины входа. Для гамильтонова цикла можно выбрать множество рёбер, потребовать степень два у каждой вершины и связность выбранного подграфа; MSO₂ умеет формулировать и связность через запрет отделённого непустого подмножества.

Теорема даёт f(|φ|,t)·n, когда разложение ширины t предоставлено вместе с графом; построение разложения - отдельная алгоритмическая задача, для фиксированной ширины также имеющая подходящие параметризованные алгоритмы. Важная ловушка: если для покрытия размера k записать «существуют k вершин» перечислением k переменных, длина формулы растёт с k. Получится зависимость f(k,t), а не только f(t). Оптимизационная версия теоремы позволяет вместо этого выбрать множество X, потребовать покрытие и минимизировать |X| при формуле фиксированного размера.

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

Механизм: почему решётка связывает два измерения

Минор графа получается удалением вершин, удалением рёбер и стягиванием рёбер; стягивание сливает два конца в одну вершину. У подходящей minor-bidimensional задачи оптимум не увеличивается при переходе к минору и на решётке r×r растёт хотя бы как c·r². Квадратный рост и объясняет название «двумерность». Для планарного графа ширины t теорема о решётке-миноре даёт сторону r = Ω(t): существует фиксированная положительная константа, так что при достаточно большой ширине можно взять r ≥ c·t. Поэтому квадратичный рост оптимума на решётке даёт нижнюю границу Ω(t²) для оптимума исходного графа. Если допустимо решение размера не больше k, получаем t² = O(k), то есть t = O(sqrt(k)).

Для вершинного покрытия оба условия выполняются. Покрытие решётки содержит не меньше размера её паросочетания: при чётном r это r²/2, достигаемое выбором одной шахматной доли. Если граф содержит такую решётку-минор с требуемым покрытием больше k, ответ для бюджета k отрицателен. Иначе структура планарного графа ограничивает древесную ширину величиной O(sqrt(k)). Динамика для покрытия с зависимостью 2^O(t) превращается в 2^O(sqrt(k))·n^O(1).

Это не следует из одной теоремы Курселя: её произвольная f может быть гораздо хуже экспоненты. Подэкспоненциальный результат использует конкретный алгоритм по ширине. И не всякая задача на планарном графе двумерна: надо отдельно проверить монотонность при минорах и рост оптимума на решётке.

Правило

Теорема Курселя требует ограничить и длину формулы, и древесную ширину. Двумерность требует структурных условий задачи и класса графов; подэкспонента получается после подстановки ширины O(sqrt(k)) в подходящую динамику.

Разбор: покрытие квадратной решётки

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

from itertools import combinations


def reshetka(r):
    v = [(i, j) for i in range(r) for j in range(r)]
    e = []
    for i, j in v:
        if i + 1 < r:
            e.append(((i, j), (i + 1, j)))
        if j + 1 < r:
            e.append(((i, j), (i, j + 1)))
    return v, e


def pokrytie(e, s):
    return all(a in s or b in s for a, b in e)


for r in [2, 4, 6]:
    v, e = reshetka(r)
    s = {p for p in v if sum(p) % 2 == 0}
    matching = [((i, j), (i, j + 1))
                for i in range(r) for j in range(0, r, 2)]
    koncy = [p for para in matching for p in para]
    assert len(set(koncy)) == len(koncy)
    assert all(para in e for para in matching)
    assert pokrytie(e, s)
    print('размер', r, 'покрытие', len(s),
          'нижняя граница', len(matching))
print('решётка 4x4 исключает бюджет 7:', 4 * 4 // 2 > 7)

размер 2 покрытие 2 нижняя граница 2
размер 4 покрытие 8 нижняя граница 8
размер 6 покрытие 18 нижняя граница 18
решётка 4x4 исключает бюджет 7: True

Один сертификат даёт верхнюю границу, второй нижнюю. Их равенство доказывает точный оптимум на решётке, не требуя перебора 2^(r²) наборов. Код не проверяет теорему о решётке-миноре и не находит минор произвольного графа: здесь проверяется конкретное звено цепочки, рост параметра на решётке.

Разбор: формула, растущая вместе с входом

Если в формулу вписать «существуют v₁,…,v_k» и затем перечислить все неравенства их различности, размер записи зависит от k. При k = n/2 это уже не фиксированная формула. Из обозначения f(|φ|,t)·n нельзя выкинуть первый аргумент и объявить алгоритм линейным по входу. Для оптимизации покрытия вместо перечисления вершин используют одну переменную-множество и оптимизационную версию метатеоремы либо явную динамику.

Что ломается без этого

Общий граф большой ширины не становится простым от того, что условие записали красиво. Планарность сама по себе не обещает малую ширину: у большой решётки ширина растёт с её стороной. FPT по ширине не даёт автоматически подэкспоненту по размеру решения. В доказательстве надо явно указать, какое свойство ограничивает ширину и какая зависимость динамики от ширины используется.

Зачем это в работе

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

Теперь сам

Дана планарная задача с шириной t ≤ c sqrt(k). Один алгоритм работает за 2^(a t)·n², другой известен только как f(t)·n. Какой из них немедленно даёт доказанную зависимость 2^O(sqrt(k))?