Нечетный цикл трансверсальный

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

В теории графов нечетный цикл трансверсаль неориентированного графа — это множество вершин графа, которое имеет непустое пересечение с каждым нечетным циклом в графе. Удаление вершин нечетного цикла трансверсаль из графа оставляет двудольный граф как оставшийся индуцированный подграф . ^[1]

Отношение к вершинному покрытию

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

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

Задача нахождения наименьшего трансверсального нечетного цикла или, что эквивалентно, наибольшего двудольного индуцированного подграфа также называется трансверсальным нечетным циклом и сокращенно обозначается как OCT. Она является NP-трудной , как частный случай задачи нахождения наибольшего индуцированного подграфа с наследственным свойством (поскольку свойство быть двудольным является наследственным). Все такие задачи для нетривиальных свойств являются NP-трудными. ^{[2] [3]}

Эквивалентность между задачами трансверсали нечетного цикла и вершинного покрытия была использована для разработки фиксированно-параметрических разрешимых алгоритмов для нечетно-параметрической трансверсали, что означает, что существует алгоритм, время выполнения которого может быть ограничено полиномиальной функцией размера графа, умноженного на большую функцию . Разработка этих алгоритмов привела к методу итеративного сжатия , более общему инструменту для многих других параметризованных алгоритмов. ^[1] Известные параметризованные алгоритмы для этих задач требуют почти линейного времени для любого фиксированного значения . ^[4] В качестве альтернативы, при полиномиальной зависимости от размера графа, зависимость от может быть сделана столь же малой, как . ^[5] Напротив, аналогичная задача для ориентированных графов не допускает фиксированно-параметрического разрешимого алгоритма при стандартных предположениях теории сложности. ^[6] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2.3146^{k}}$

Смотрите также

• Максимальный разрез , эквивалентный запросу минимального набора ребер, удаление которых оставляет двудольный граф

Ссылки

1. Cygan, Марек; Фомин Федор Владимирович; Ковалик, Лукаш; Локштанов Даниил; Маркс, Даниэль; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015), Параметризованные алгоритмы , Springer, стр. 64–65, номер документа : 10.1007/978-3-319-21275-3, ISBN 978-3-319-21274-6, МР  3380745
2. Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), «GT21: Индуцированный подграф со свойством Π», Компьютеры и неразрешимость: Руководство по теории NP-полноты , WH Freeman, стр. 195
3. Яннакакис, Михалис (1978), «NP-полные задачи удаления узлов и ребер», Труды 10-го симпозиума ACM по теории вычислений (STOC '78) , стр. 253–264, doi : 10.1145/800133.804355
4. Каварабаяси, Кен-ичи ; Рид, Брюс (2010), «(Почти) линейный алгоритм времени для трансверсальных нечетных циклов», Труды двадцать первого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Филадельфия, Пенсильвания: SIAM, стр. 365–378, CiteSeerX 10.1.1.215.2581 , doi : 10.1137/1.9781611973075.31, ISBN  978-0-89871-701-3, г-н  2809682
5. Локштанов, Даниэль; Нараянасвами, Н.С.; Раман, Венкатеш; Рамануджан, М.С.; Саурабх, Сакет (2014), «Более быстрые параметризованные алгоритмы с использованием линейного программирования», ACM Transactions on Algorithms , 11 (2): Art. 15, 31, arXiv : 1203.0833 , doi : 10.1145/2566616, MR  3283570
6. Локштанов, Даниэль; Рамануджан, М.С.; Саурабх, Сакет; Зехави, Мейрав (2017), Параметризованная сложность и аппроксимируемость направленного нечетного цикла трансверсали , arXiv : 1704.04249 , Bibcode : 2017arXiv170404249L