Нечетный цикл поперечный - Odd cycle transversal

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

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

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

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

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

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

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

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

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

Рекомендации

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

[pa-1] а ^б ^c Циган, Марек; Фомин, Федор В .; Ковалик, Лукаш; Локштанов Даниил; Маркс, Даниэль; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015), Параметризованные алгоритмы, Springer, стр. 64–65, Дои:10.1007/978-3-319-21275-3, ISBN 978-3-319-21274-6, МИСТЕР 3380745

[gt21-2] Гарей, Майкл Р.; Джонсон, Дэвид С. (1979), "GT21: Индуцированный подграф со свойством Π", Компьютеры и непреодолимость: руководство по теории NP-полноты, В. Х. Фриман, стр. 195

[yan-3] Яннакакис, Михалис (1978), "NP-полные проблемы с удалением узлов и ребер", Труды 10-го симпозиума ACM по теории вычислений (STOC '78), стр. 253–264, Дои:10.1145/800133.804355

[kr-4] Каварабаяси, Кен-ичи; Рид, Брюс (2010), «(Почти) линейный алгоритм времени для трансверсальных нечетных циклов», Материалы двадцать первого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, Филадельфия, Пенсильвания: SIAM, стр. 365–378, CiteSeerX 10.1.1.215.2581, Дои:10.1137/1.9781611973075.31, ISBN 978-0-89871-701-3, МИСТЕР 2809682

[lnrrs-5] Локштанов Даниил; Narayanaswamy, N.S .; Раман, Венкатеш; Ramanujan, M. S .; Саураб, Сакет (2014), «Более быстрые параметризованные алгоритмы с использованием линейного программирования», ACM-транзакции на алгоритмах, 11 (2): Ст. 15, 31, arXiv:1203.0833, Дои:10.1145/2566616, МИСТЕР 3283570

[doct-6] Локштанов Даниил; Ramanujan, M. S .; Саураб, Сакет; Зехави, Мейрав (2017), Параметризованная сложность и аппроксимируемость направленной трансверсали нечетного цикла, arXiv:1704.04249, Bibcode:2017arXiv170404249L

[1]

[2]

[3]

[4]

[5]

[6]