Разрывающее множество вершин: сжать решение размера k+1

Если понимаешь, зачем известное решение делают защищённым - переходи к «Теперь сам».

Как думаешь: чем плох выбор одной вершины цикла?

Есть цикл длины тысяча. Известно, что хотя бы одну его вершину надо удалить. Ветвление по тысяче вариантам на каждом из k уровней даёт до 1000^k ветвей, а в общем виде n^k. Для каждого фиксированного k это полином, но показатель зависит от параметра. FPT требует f(k)·n^c, где c постоянно.

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

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

Представь ремонт сети, где уже отключены k+1 узлов и петель связи больше нет. Нужно вернуть хотя бы один узел в работу, возможно отключив вместо него другие. Искать хороший набор с нуля трудно. Зато известный набор разбивает задачу на маленькую защищённую часть и большой лес; циклы могут появляться только через защищённые узлы. Это ограничение и используется в поиске.

Механизм: угадать пересечение и защищать оставшееся

Рассматриваем индуцированные графы на первых i вершинах. Пусть для предыдущего графа найден набор S размера не больше k. После добавления новой вершины v набор Z = S ∪ {v} снова разрывает все циклы: старый граф без S был лесом, а v удалена. Если размер Z не превышает k, ничего сжимать не надо. Иначе ищем решение размера k; если его нет в текущем подграфе, нет и во всём графе, потому что удаление дополнительных вершин вне подграфа не разрушит внутренний цикл.

Переберём Y ⊆ Z, предполагая, что это ровно пересечение нового решения со старым. Удалим Y, уменьшим бюджет до k − |Y|, а W = Z \ Y объявим защищённым: его вершины больше удалять нельзя. Обозначим граф после удаления Y через G′ = G − Y. Незащищённая часть H = G′ − W = G − Z - лес, поскольку Z было разрывающим множеством исходного графа. Далее для непересекающейся задачи буквой G снова обозначаем уже уменьшенный граф G′. Получилась непересекающаяся FVS, disjoint FVS. Если G[W] содержит цикл, догадка сразу невозможна: его вершины защищены.

Для непересекающейся задачи применяются три редукции. Вершины степени ноль или один не лежат на цикле и удаляются из текущего экземпляра без расхода бюджета. Если добавление незащищённой вершины x к G[W] уже создаёт цикл, x обязательно входит в удаляемый набор. Наконец, незащищённую вершину степени два, имеющую незащищённого соседа, можно подавить: удалить и соединить её соседей. Параллельные рёбра при этом сохраняются, поскольку два таких ребра образуют цикл; сведение к простому графу здесь ошибочно.

После редукций у леса H берём лист или изолированную вершину x. Если H непуст, у x есть хотя бы два соседа в разных компонентах G[W]: иначе сработала бы одна из редукций. Ветвимся: удалить x с уменьшением бюджета на один либо оставить навсегда, перенеся в W. Во второй ветви её соседи соединяют хотя бы две защищённые компоненты. Мера μ = k + число компонент G[W] уменьшается хотя бы на единицу в каждой ветви. Изначально μ ≤ 2k+1, значит дерево поиска имеет O(4^k) узлов с точностью до постоянного множителя. Редукции меру не увеличивают.

Перебор Y вместе с поиском даёт сумму биномиальных коэффициентов: выбор i удалённых старых вершин оставляет бюджет k−i; суммируются C(k+1,i)4^(k−i), что ограничено константой на 5^k. Множитель числа добавляемых вершин полиномиален. Это доказательство FPT, а не просто название метода.

Правило

В итеративном сжатии старое решение имеет размер k+1; после угадывания пересечения оставшаяся его часть защищена от удаления. Время FPT обеспечивается мерой, ограниченной функцией k, а не длиной произвольного цикла.

Разбор: два треугольника с общей вершиной

Программа демонстрирует рамку сжатия на маленьком графе. Внутри шага стоит полный перебор незащищённых наборов, поэтому сам этот учебный код не имеет доказанной границы 5^k; быстрый подалгоритм описан выше. Такая явная граница отделяет проверку логики сжатия от промышленной реализации FPT.

from itertools import combinations


def les(vershiny, rebra, udaleno):
    roditel = {v: v for v in vershiny if v not in udaleno}

    def koren(v):
        while roditel[v] != v:
            v = roditel[v]
        return v

    for u, v in rebra:
        if u not in roditel or v not in roditel:
            continue
        a, b = koren(u), koren(v)
        if a == b:
            return False
        roditel[a] = b
    return True


def podmnozhestva(s, limit):
    s = sorted(s)
    for k in range(min(limit, len(s)) + 1):
        for p in combinations(s, k):
            yield set(p)


def szhat(v, rebra, z, k):
    for y in podmnozhestva(z, k):
        w = z - y
        if not les(w, rebra, set()):
            continue
        ostalnye = set(v) - z
        for x in podmnozhestva(ostalnye, k - len(y)):
            if les(v, rebra, x | y):
                return x | y
    return None


rebra = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)]
s = set()
for i in range(1, 6):
    v = set(range(i))
    e = [(a, b) for a, b in rebra if a in v and b in v]
    z = s | {i - 1}
    s = szhat(v, e, z, 1)
    assert s is not None and les(v, e, s)
    print('вершин', i, 'удаляем', sorted(s))
print('итоговый размер:', len(s))

вершин 1 удаляем []
вершин 2 удаляем []
вершин 3 удаляем [0]
вершин 4 удаляем [1]
вершин 5 удаляем [2]
итоговый размер: 1

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

Разбор: два непересекающихся треугольника

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

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

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

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

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

Теперь сам

Известный разрывающий набор Z = {a,b,c}, бюджет два. В догадке Y = {b} что удаляется сразу, какие вершины защищены и сколько новых вершин вне Z ещё можно удалить?