Ядро: сжать вход до размера, зависящего только от k

Если ты знаешь правила Басса и почему после них остаётся не больше k² рёбер, почему соседа листа можно брать всегда и откуда ядро из 2k вершин, листай до «Теперь сам».

Как думаешь, что можно решить до поиска

Граф связей из 400 серверов: шесть концентраторов, к каждому подключено по шесть-семь десятков серверов, и десяток связей между обычными серверами. Бюджет - 16 датчиков. Дерево поиска из прошлых уроков сработает, но каждый его вызов просматривает все 404 ребра.

Ответь себе до чтения: какие решения можно принять, ещё не начав перебор? Концентратор с семьюдесятью связями: если не ставить на него датчик, понадобятся датчики на всех семидесяти соседях - больше бюджета. Значит, датчик на нём обязателен. Таких решений здесь шесть, и после них от графа остаются десять рёбер.

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

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

Ядро - такая подготовка для алгоритма: решения, которые вынуждены, принимаются сразу, лишнее выбрасывается, и в перебор попадает задача размера, зависящего только от k.

Механизм: правила сокращения

Определение. Ядро - алгоритм, который за полиномиальное время превращает вход (G, k) в равносильный (G', k') (ответы совпадают) с размером G' не больше g(k). Если ядро есть, задача FPT: сжать за полином, потом решить остаток за любое время от g(k). Верно и обратное - любая разрешимая FPT-задача имеет ядро.

Правила Басса для вершинного покрытия:

1. вершина без рёбер                →  выбросить
2. вершина степени больше k         →  взять в покрытие, k = k − 1
   (граф без кратных рёбер)
                                       (без неё нужны все её > k соседей)
3. правила 1-2 не применимы,        →  ответ «нет»
   а рёбер больше k² или вершин        (k вершин степени <= k
   больше k² + k
                                        закрывают не больше k² рёбер)
итог: ядро из <= k² рёбер и <= k² + k вершин

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

Ядро из 2k вершин. Из главы об округлении: у релаксации вершинного покрытия есть оптимум из 0, 1/2 и 1. Немхаузер и Троттер показали больше: существует наименьшее покрытие, содержащее все вершины с единицей и ни одной с нулём. Вершины с единицей берут, с нулём - выбрасывают, остаются вершины с половиной. Их сумма - не больше LP, а LP не больше k, иначе ответ «нет», - значит, вершин с половиной не больше 2k.

Правило

Ядро - полиномиальное сжатие входа до размера g(k) с тем же ответом. Для вершинного покрытия: выбросить изолированные вершины, взять вершины степени больше k; если после этого рёбер больше k² - ответ «нет». Остаётся не больше k² рёбер. Соседа листа берут всегда. Через ЛП-релаксацию ядро сжимается до 2k вершин.

Разбор: шесть концентраторов

Граф: вершины 0-5 - концентраторы, каждый из остальных 394 серверов привязан к случайному из них, плюс десяток связей между обычными серверами. yadro_bassa применяет правило 2, пока может, и правило 3. Три бюджета: 16, 12, 8.

import random

def stepeni(ryobra):
    st = {}
    for r in ryobra:
        st[r[0]] = st.get(r[0], 0) + 1
        st[r[1]] = st.get(r[1], 0) + 1
    return st

def bez(ryobra, v):
    ostalis = []
    for r in ryobra:
        if r[0] != v and r[1] != v:
            ostalis.append(r)
    return ostalis

def yadro_bassa(ryobra, k):
    vzyato = []
    menyalos = True
    while menyalos:
        menyalos = False
        st = stepeni(ryobra)
        for v in st:
            if not menyalos and st[v] > k:
                vzyato.append(v)
                ryobra = bez(ryobra, v)
                k = k - 1
                menyalos = True
    if k < 0 or len(ryobra) > k * k:
        return ["нет", vzyato, k, len(ryobra)]
    return ["ядро", vzyato, k, len(ryobra)]

random.seed(8)
ryobra = []
for v in range(1, 400):
    centr = random.randrange(6)
    if v > 5 and [centr, v] not in ryobra:
        ryobra.append([centr, v])
for i in range(10):
    a = random.randrange(6, 400)
    b = random.randrange(6, 400)
    if a != b:
        ryobra.append([a, b])
print(len(ryobra), len(stepeni(ryobra)))
for k in [16, 12, 8]:
    print(k, yadro_bassa(ryobra, k))

404 400
16 ['ядро', [5, 0, 1, 4, 3, 2], 10, 10]
12 ['ядро', [5, 0, 1, 4, 3, 2], 6, 10]
8 ['нет', [5, 0, 1, 4, 3, 2], 2, 10]

Столбцы: бюджет, итог, взятые вершины, оставшийся бюджет, оставшиеся рёбра. При бюджете 16 все шесть концентраторов взяты (у каждого больше 16 соседей), осталось 10 рёбер и бюджет 10 - крошечная задача для дерева поиска. При 12 - то же, бюджет 6, а 6² = 36 ≥ 10, так что ответ пока не ясен. При 8 - бюджет 2, 2² = 4 < 10: ответ «нет» найден без единого ветвления.

Ни на одном шаге правила не смотрели на 394 «обычных» сервера по отдельности: они исчезли вместе с рёбрами концентраторов. Работа ядра полиномиальная (показанная программа пересчитывает степени после каждого взятия; аккуратная реализация - линейная), работа поиска - только по ядру.

Разбор: дерево решается одними листьями

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

import random

def pravilo_lista(ryobra):
    # пока есть вершина степени 1, её соседа берём в покрытие
    vzyato = []
    menyalos = True
    while menyalos:
        menyalos = False
        st = {}
        sosed = {}
        for r in ryobra:
            st[r[0]] = st.get(r[0], 0) + 1
            st[r[1]] = st.get(r[1], 0) + 1
            sosed[r[0]] = r[1]
            sosed[r[1]] = r[0]
        for v in st:
            if not menyalos and st[v] == 1:
                u = sosed[v]
                vzyato.append(u)
                ostalis = []
                for r in ryobra:
                    if r[0] != u and r[1] != u:
                        ostalis.append(r)
                ryobra = ostalis
                menyalos = True
    return [len(vzyato), len(ryobra)]

random.seed(12)
derevo = []
for v in range(1, 120):
    derevo.append([random.randrange(v), v])
print(pravilo_lista(derevo))
s_ciklami = derevo[:]
for i in range(5):
    s_ciklami.append([120 + i, 120 + (i + 1) % 5])
s_ciklami.append([0, 120])
print(pravilo_lista(s_ciklami))

[46, 0]
[46, 5]

Дерево: 46 вершин, рёбер не осталось - найдено наименьшее покрытие, и ни одного ветвления. У дерева всегда есть лист, и правило применяется до конца. С пятиугольником: те же 46 вершин, и остаётся сам пятиугольник - 5 рёбер, у всех вершин степень 2, листьев нет. Это остаток после правила листа - в нём нужна настоящая работа, а ядром по определению его делают вместе с правилами Басса, которые ограничивают размер через k. Здесь она тривиальна - цикл из пяти требует трёх вершин, - а в общем случае ядро отдают дереву поиска.

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

Ветвятся по всему графу. Каждый вызов дерева поиска платит за все рёбра; на 404 рёбрах это в сорок раз дороже, чем на ядре из десяти.

Применяют правило 3 до правил 1-2. Граф с концентратором степени 100 при k = 5 - рёбер больше 25, но ответ может быть «да»: концентратор закрывает их одной вершиной. Оценка k² верна только когда все степени не больше k.

Берут обоих: лист и соседа. Лист не нужен никогда: его единственное ребро закрывает сосед.

Доверяют ядру без проверки равносильности. Правило, которое иногда меняет ответ, - не правило ядра, а эвристика. Каждое правило требует доказательства «ответы до и после совпадают».

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

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

Теперь сам

1. k = 3. После правил Басса осталось 12 рёбер. Каков ответ?
2. Звезда с центром и 50 лучами, k = 1. Что сделают правила Басса?
3. Почему после правила 2 каждая вершина имеет степень не больше k, а не k − 1?