Сечение нечётных циклов

Граф с сечением нечётных циклов размера 2 — удаление двух синих нижних вершин оставляет двудольный граф.

Сечение нечётных циклов неориентированного графа — это набор вершин графа, который имеет непустое пресечение с любым нечётным циклом в графе. Удаление вершин сечения нечётных циклов из графа оставляет двудольный граф в качестве порождённого подграфаШаблон:R.

Связь с вершинным покрытием

Заданный $n$-вершинный граф $G$ имеет сечение нечётных циклов размера $k$ тогда и только тогда, когда прямое произведение графов $G◻K_2$ (граф, состоящий из двух копий $G$, с соответствующими вершинами каждой копии, соединёнными рёбрами совершенного паросочетания) имеет вершинное покрытие размера $n+k$. Сечение нечётных циклов может быть преобразовано в вершинное покрытие путём включения обеих копий каждой вершины из сечения и одной копии каждой оставшейся вершины, выбранных из двух копий согласно тому, какой доле разбиения она принадлежит. В другом направлении вершинное покрытие графа $G◻K_2$ может быть преобразовано в сечение нечётных циклов путём сохранения только вершин, для которых обе копии содержатся в покрытии. Вершины вне результирующего сечения могут быть разбиты на две части согласно тому, какая копия вершины использовалась в покрытииШаблон:R.

Алгоритмы и сложность

Задача нахождения наименьшего сечения нечётных циклов, или, эквивалентно, наибольшего двудольного порождённого подграфа, называется задачей сечения нечётных циклов (Шаблон:Lang-en, OCT). Задача NP-трудна, так как является специальным случаем нахождения наибольшего порождённого подграфа с наследственным свойством (так как свойство двудольности наследуется). Все такие задачи для нетривиальных свойств NP-трудныШаблон:R.

Эквивалентность между задачей сечения нечётных циклов и задачей вершинного покрытия может быть использована для разработки Шаблон:Не переведено 5 алгоритмов для сечения нечётных циклов, это означает, что существует алгоритм, время работы которого может быть ограничено полиномиальной функцией от размера графа, умноженной на (бо́льшую) функцию от $k$. Разработка этих алгоритмов приводит к методу итеративного сжатия, более общий метод для многих других параметризованных алгоритмовШаблон:R. Параметризованные алгоритмы известны для этих задач, которые работают за почти линейное время для любого фиксированного значения $k$Шаблон:R. Альтернативно, с полиномиальной зависимостью от размера, зависимость от $k$ может быть сведена к $2,3146^k$Шаблон:R. Для контраста, аналогичная задача для ориентированных графов не допускает фиксированно-параметрически разрешимых алгоритмов при стандартных предположениях теоретической сложности Шаблон:R.