Сечение нечётных циклов неориентированного графа — набор вершин графа, который имеет непустое пересечение с любым нечётным циклом в графе. Удаление вершин сечения нечётных циклов из графа оставляет двудольный граф в качестве порождённого подграфа.
Связь с вершинным покрытием Заданный -вершинный граф имеет сечение нечётных циклов размера тогда и только тогда, когда прямое произведение графов (граф, состоящий из двух копий , с соответствующими вершинами каждой копии, соединёнными рёбрами совершенного паросочетания) имеет вершинное покрытие размера . Сечение нечётных циклов может быть преобразовано в вершинное покрытие путём включения обеих копий каждой вершины из сечения и одной копии каждой оставшейся вершины, выбранных из двух копий согласно тому, какой доле разбиения она принадлежит. В другом направлении вершинное покрытие графа может быть преобразовано в сечение нечётных циклов путём сохранения только вершин, для которых обе копии содержатся в покрытии. Вершины вне результирующего сечения могут быть разбиты на две части согласно тому, какая копия вершины использовалась в покрытии.
Алгоритмы и сложность Задача нахождения наименьшего сечения нечётных циклов, или, эквивалентно, наибольшего двудольного порождённого подграфа, называется задачей сечения нечётных циклов (, OCT). Задача NP-трудна, так как является специальным случаем нахождения наибольшего порождённого подграфа с наследственным свойством (так как свойство двудольности наследуется). Все такие задачи для нетривиальных свойств NP-трудны.
Эквивалентность между задачей сечения нечётных циклов и задачей вершинного покрытия может быть использована для разработки алгоритмов для сечения нечётных циклов, это означает, что существует алгоритм, время работы которого может быть ограничено полиномиальной функцией от размера графа, умноженной на (бо́льшую) функцию от . Разработка этих алгоритмов приводит к методу итеративного сжатия, более общий метод для многих других параметризованных алгоритмов. Параметризованные алгоритмы известны для этих задач, которые работают за почти линейное время для любого фиксированного значения . Альтернативно, с полиномиальной зависимостью от размера, зависимость от может быть сведена к . Для контраста, аналогичная задача для ориентированных графов не допускает фиксированно-параметрически разрешимых алгоритмов при стандартных предположениях теоретической сложности .
Примечания
Категория:Объекты теории графов Категория:Вычислительные задачи теории графов