В теории графов , нечетное цикл трансверсально из неориентированного графа представляет собой набор вершин графа , который имеет непустое пересечение с каждым нечетным циклом в графе. Удаление вершин нечетного цикла, трансверсали графа, оставляет двудольный граф как оставшийся индуцированный подграф . [1]
Отношение к вершинному покрытию
Данный -вершинный граф имеет нечетный цикл трансверсали размера , тогда и только тогда, когда декартово произведение графов (граф, состоящий из двух копий , с соответствующими вершинами каждой копии, соединенными ребрами совершенного паросочетания ) имеет вершинное покрытие размера. Трансверсаль нечетного цикла может быть преобразована в покрытие вершины путем включения обеих копий каждой вершины трансверсали и одной копии каждой оставшейся вершины, выбранной из двух копий в соответствии с тем, какая сторона двудольного раздела содержит ее. В другом направлении вершинное покрытиеможно преобразовать в трансверсаль нечетного цикла, оставив только те вершины, для которых обе копии находятся в обложке. Вершины за пределами получившейся трансверсали можно разделить на две части в соответствии с тем, какая копия вершины использовалась в покрытии. [1]
Алгоритмы и сложность
Проблема поиска наименьшего трансверсального нечетного цикла или, что эквивалентно, наибольшего двудольного индуцированного подграфа, также называется трансверсалию нечетного цикла и сокращенно OCT. Это NP-сложно , как частный случай проблемы поиска наибольшего индуцированного подграфа с наследственным свойством (поскольку свойство быть двудольным является наследственным). Все такие задачи для нетривиальных свойств NP-трудны. [2] [3]
Эквивалентность между задачами трансверсии нечетного цикла и вершинного покрытия была использована для разработки управляемых алгоритмов с фиксированными параметрами для трансверсальности нечетного цикла, что означает, что существует алгоритм, время работы которого может быть ограничено полиномиальной функцией от размера графа, умноженного на большая функция. Развитие этих алгоритмов привело к методу итеративного сжатия , более общему инструменту для многих других параметризованных алгоритмов. [1] Параметризованные алгоритмы, известные для этих задач, занимают почти линейное время для любого фиксированного значения. [4] В качестве альтернативы, при полиномиальной зависимости от размера графа, зависимость от можно сделать размером с . [5] Напротив, аналогичная задача для ориентированных графов не допускает управляемый алгоритм с фиксированными параметрами при стандартных предположениях теории сложности. [6]
Смотрите также
- Максимальный разрез , эквивалентный запросу минимального набора ребер, удаление которых оставляет двудольный граф
Рекомендации
- ^ a b c Циган, Марек; Фомин, Федор В .; Ковалик, Лукаш; Локштанов Даниил; Маркс, Даниэль; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015), параметризованные алгоритмы , Springer, стр. 64–65, DOI : 10.1007 / 978-3-319-21275-3 , ISBN 978-3-319-21274-6, Руководство по ремонту 3380745
- ^ Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), «GT21: индуцированный подграф со свойством Π», « Компьютеры и несговорчивость: руководство по теории NP-полноты» , WH Freeman, p. 195
- ^ Yannakakis, Михалис (1978), "Узел и края удаления NP-полных задач", Труды 10 - го симпозиума ACM по теории вычислений (STOC '78) , С. 253-264,. Дои : 10,1145 / 800133,804355
- ^ Каварабаяси, Кен-ичи ; Рид, Брюс (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
- ^ Локштанов Даниил; Narayanaswamy, NS; Раман, Венкатеш; Рамануджан, MS; Саураб, Сакет (2014), «Более быстрые параметризованные алгоритмы с использованием линейного программирования», Транзакции ACM по алгоритмам , 11 (2): ст. 15, 31, Arxiv : 1203,0833 , DOI : 10,1145 / 2566616 , МР 3283570
- ^ Локштанов Даниил; Рамануджан, MS; Саураб, Сакет; Зехави, Мейрав (2017), Параметризованная сложность и аппроксимируемость направленного трансверсального нечетного цикла , arXiv : 1704.04249 , Bibcode : 2017arXiv170404249L