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

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

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

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

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

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

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

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