Трансверсализация нечетного цикла

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

Связь с вершинным покрытием

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

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

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

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

См. также

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

Ссылки

^ Jump up to: ^а ^б ^с Циган, Марек; Фомин Федор Владимирович; Ковалик, Лукаш; Локштанов Даниил; Маркс, Дэниел; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015), Параметризованные алгоритмы , Springer, стр. 64–65, номер домена : 10.1007/978-3-319-21275-3 , ISBN. 978-3-319-21274-6 , МР 3380745
^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), «GT21: Индуцированный подграф со свойством Π», Компьютеры и трудноразрешимость: Руководство по теории NP-полноты , WH Freeman, p. 195
^ Яннакакис, Михалис (1978), «NP-полные задачи с удалением узлов и ребер», Труды 10-го симпозиума ACM по теории вычислений (STOC '78) , стр. 253–264, doi : 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
^ Локштанов Даниил; Нараянасвами, Н.С.; Раман, Венкатеш; Рамануджан, М.С.; Саураб, Сакет (2014), «Более быстрые параметризованные алгоритмы с использованием линейного программирования», Транзакции ACM в алгоритмах , 11 (2): Ст. 15, 31, arXiv : 1203.0833 , doi : 10.1145/2566616 , MR 3283570
^ Локштанов Даниил; Рамануджан, М.С.; Саураб, Сакет; Зехави, Мейрав (2017), Параметризованная сложность и аппроксимируемость направленного трансверсального нечетного цикла , arXiv : 1704.04249 , Bibcode : 2017arXiv170404249L

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

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

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

[kr-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

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

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

[1]

[2]

[3]

[4]

[5]

[6]