Заданный <math>n</math>-вершинный граф <math>G</math> имеет сечение нечётных циклов размера <math>k</math> тогда и только тогда, когда прямое произведение графов <math>G\square K_2</math> (граф, состоящий из двух копий <math>G</math>, с соответствующими вершинами каждой копии, соединёнными рёбрами совершенного паросочетания) имеет вершинное покрытие размера <math>n+k</math>. Сечение нечётных циклов может быть преобразовано в вершинное покрытие путём включения обеих копий каждой вершины из сечения и одной копии каждой оставшейся вершины, выбранных из двух копий согласно тому, какой доле разбиения она принадлежит. В другом направлении вершинное покрытие графа <math>G\square K_2</math> может быть преобразовано в сечение нечётных циклов путём сохранения только вершин, для которых обе копии содержатся в покрытии. Вершины вне результирующего сечения могут быть разбиты на две части согласно тому, какая копия вершины использовалась в покрытииШаблон:R.
Алгоритмы и сложность
Задача нахождения наименьшего сечения нечётных циклов, или, эквивалентно, наибольшего двудольного порождённого подграфа, называется задачей сечения нечётных циклов (Шаблон:Lang-en, OCT). Задача NP-трудна, так как является специальным случаем нахождения наибольшего порождённого подграфа с наследственным свойством (так как свойство двудольности наследуется). Все такие задачи для нетривиальных свойств NP-трудныШаблон:R.
Эквивалентность между задачей сечения нечётных циклов и задачей вершинного покрытия может быть использована для разработки Шаблон:Не переведено 5 алгоритмов для сечения нечётных циклов, это означает, что существует алгоритм, время работы которого может быть ограничено полиномиальной функцией от размера графа, умноженной на (бо́льшую) функцию от <math>k</math>. Разработка этих алгоритмов приводит к методу итеративного сжатия, более общий метод для многих других параметризованных алгоритмовШаблон:R. Параметризованные алгоритмы известны для этих задач, которые работают за почти линейное время для любого фиксированного значения <math>k</math>Шаблон:R. Альтернативно, с полиномиальной зависимостью от размера, зависимость от <math>k</math> может быть сведена к <math>2{,}3146^k</math>Шаблон:R.
Для контраста, аналогичная задача для ориентированных графов не допускает фиксированно-параметрически разрешимых алгоритмов при стандартных предположениях теоретической сложности Шаблон:R.
