Подсолнухи и корона: почему часть ограничений можно выбросить

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

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

Нужно поставить не больше двух датчиков. Есть требования: хотя бы один датчик в каждом из наборов {a,x}, {a,y}, {a,z}. Взять x,y,z нельзя: это три датчика. Значит, любое допустимое решение обязано содержать a. Здесь три похожих ограничения можно заменить одним {a} не по сходству текста, а по доказанному расходу бюджета.

Теперь два требования {a,x}, {a,y} при том же бюджете два. Замена на {a} уже неверна: решение {x,y} допустимо исходно и исчезнет после такой замены. Граница числа лепестков зависит от бюджета, а не от того, насколько наглядно выглядит рисунок.

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

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

Механизм: подсолнух для d-Hitting Set

В задаче пересечения множеств, Hitting Set, выбирается набор элементов X, пересекающий каждый входной набор. В отличие от упаковки, здесь выбирают элементы, а не совместимые наборы. В d-Hitting Set размер каждого входного набора не больше фиксированного d, а бюджет выбранных элементов равен k.

Подсолнух S₁,…,S_r имеет S_i ∩ S_j = Y для всех разных i,j. Если r = k+1 и X не пересекает Y, для каждого лепестка понадобится отдельный элемент: лепестки не пересекаются. Получается не меньше k+1 элементов, что запрещено. Поэтому все k+1 наборов можно заменить сердцевиной Y: любое решение исходной задачи размера не больше k пересекает её, а любой набор, пересекающий Y, пересекает удалённые наборы. Если сердцевина пуста, сразу получаем ответ «нет»: один элемент не заденет два разных лепестка.

Классическая лемма Эрдёша-Радо говорит: если семейство различных наборов размера ровно d содержит больше d!·(r−1)^d наборов, в нём есть подсолнух с r лепестками. Здесь факториал и степень измеряют, сколько разных ограничений может оставаться без такой повторяющейся структуры. Для наборов не больше d применяют соответствующее дополнение уникальными элементами или версии леммы для ограниченного размера. Последовательное применение редукций даёт число оставшихся наборов, полиномиальное по k при фиксированном d; в указанной конструкции - не больше d!·k^d. Уникальные дополнения используются только для обоснования поиска, их нельзя объявлять свободными полезными датчиками исходной задачи.

Механизм: корона для вершинного покрытия

Разбиваем вершины на C,H,R. Набор C независим, из C нет рёбер в R, а паросочетание между H и C насыщает каждую вершину H. Поэтому любому покрытию надо потратить хотя бы |H| вершин на непересекающиеся рёбра паросочетания. Если в каком-то покрытии выбрана часть C, можно заменить все выбранные в C ∪ H на целое H: цена не возрастёт, все рёбра из C будут покрыты, а рёбра внутри H и из H в R тоже. Редукция сохраняет существование покрытия размера k: удалить C ∪ H, заменить k на k − |H|.

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

Правило

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

Разбор: три лепестка и два датчика

Программа перечисляет все короткие решения задачи пересечения и сравнивает их с заменой подсолнуха сердцевиной. Потом показывает, что при недостаточном числе лепестков такая замена теряет решение.

from itertools import combinations


def popadaet(x, semeistvo):
    return all(x & s for s in semeistvo)


def varianty(vselennaya, k):
    for r in range(k + 1):
        for x in combinations(sorted(vselennaya), r):
            yield set(x)


def sravnit(semeistvo, k):
    y = set.intersection(*semeistvo)
    u = set.union(*semeistvo)
    razlichiya = []
    for x in varianty(u, k):
        if popadaet(x, semeistvo) != popadaet(x, [y]):
            razlichiya.append(''.join(sorted(x)))
    return y, razlichiya


a = [set('ax'), set('ay'), set('az')]
b = a[:2]
print('три лепестка:', sravnit(a, 2))
print('два лепестка:', sravnit(b, 2))
print('пустая сердцевина:', sravnit([set('x'), set('y')], 1))

три лепестка: ({'a'}, [])
два лепестка: ({'a'}, ['xy'])
пустая сердцевина: (set(), [])

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

Разбор: маленькая корона с явной ценой

Пусть C = {c₁,c₂,c₃}, H = {h₁,h₂}. Есть рёбра h₁c₁, h₁c₂, h₂c₂, h₂c₃, а из H идут произвольные рёбра к остальному графу. Внутри C и между C,R рёбер нет. Паросочетание h₁c₁, h₂c₃ требует двух вершин любого покрытия. Выбрать h₁,h₂ достаточно для всех рёбер, касающихся C ∪ H, кроме рёбер внутри R, которые остаются в остатке. При бюджете четыре остаточный бюджет два. Восстановление просто добавляет обе h к решению остатка.

Без насыщения головы редукция может стать неверной. Возьми другой граф: C = {a}, H = {x,y}, R пусто, рёбра ax и ay. Все условия независимости и отсутствия связей с остатком выполнены, но обе вершины головы нельзя сопоставить разным вершинам C. Покрытие {a} стоит одну вершину; принудительный выбор {x,y} стоит две и теряет оптимум. Нельзя применять редукцию лишь по рисунку «много листьев возле нескольких вершин»: нужно проверить насыщающее паросочетание и отсутствие связей C,R.

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

Подсолнух с k лепестками вместо k+1 не заставляет выбрать сердцевину. Случайное удаление похожего ограничения может сменить ответ. В короне рёбра из независимой части в остаток нарушают замену: выбор всей головы их не покроет. Отрицательный остаточный бюджет означает «нет», а не разрешение взять меньше обязательных вершин головы.

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

В задачах диагностики, отключения конфликтов и покрытия требований ядро сокращает вход перед дорогим поиском. Вместе с уменьшенным экземпляром нужно хранить журнал восстановления: какие головы корон уже оплачены, какие ограничения заменены. Для решения «да/нет» достаточно эквивалентности, но для выдачи исходного набора объектов требуется вернуть выполненные преобразования в обратном порядке.

Теперь сам

Бюджет k=3, требования {a,b,x₁}, {a,b,x₂}, {a,b,x₃}, {a,b,x₄}. Чем их можно заменить? Обязательно ли выбрать и a, и b?