Набор доминирующих краев

В теории графов для доминирующим множеством ребер графа G = ( V , E ) является подмножество D ⊆ E такое, что каждое ребро, не входящее в D смежно хотя бы с одним ребром в D. , Множество с доминирующим ребром также известно как множество с доминирующим ребром . Рисунки (a)–(d) представляют собой примеры множеств с доминирующим ребром (толстые красные линии).

Минимальный набор с доминирующим ребром — это наименьший набор с доминирующим ребром. Рисунки (a) и (b) являются примерами минимальных множеств с доминирующим ребром (можно проверить, что для этого графа не существует множества с доминирующим ребром размера 2).

Характеристики

Множество с доминирующим ребром для G является доминирующим множеством для его линейного графа L ( G ), и наоборот.

Любое максимальное паросочетание всегда является множеством с доминирующим ребром. Рисунки (б) и (г) являются примерами максимальных паросочетаний.

Более того, размер минимального доминирующего набора ребер равен размеру минимального максимального паросочетания . Минимальное максимальное паросочетание — это минимальное множество с доминирующим ребром; Рисунок (b) представляет собой пример минимального максимального паросочетания. Минимальный набор с доминирующим ребром не обязательно является минимальным максимальным паросочетанием, как показано на рисунке (a); однако, учитывая минимальный набор D с доминирующим ребром , легко найти минимальное максимальное паросочетание с | Д | края (см., например, Яннакакис и Гаврил 1980 ).

Алгоритмы и вычислительная сложность

Определение того, существует ли набор с доминирующим ребром заданного размера для данного графа, является NP-полной проблемой (и, следовательно, поиск минимального набора с доминирующим ребром является NP-трудной проблемой). Яннакакис и Гаврил (1980) показывают, что проблема является NP-полной даже в случае двудольного графа с максимальной степенью 3, а также в случае плоского графа с максимальной степенью 3.

Существует простой алгоритм аппроксимации за полиномиальное время с коэффициентом аппроксимации 2: найти любое максимальное паросочетание. Максимальное паросочетание — это множество с доминирующим ребром; более того, максимальное паросочетание M может быть в худшем случае в 2 раза больше, чем наименьшее максимальное паросочетание, а наименьшее максимальное паросочетание имеет тот же размер, что и наименьшее множество с доминирующим ребром.

Также взвешенную по ребрам версию задачи можно аппроксимировать с коэффициентом 2, но алгоритм значительно сложнее ( Fujito & Nagamochi 2002 ; Parekh 2002 ).

Хлебик и Хлебикова (2006) показывают, что найти приближение лучше, чем (7/6), NP-трудно. Шмид и Виманн доказали, что задачу UGC сложно аппроксимировать с точностью до любой константы лучше 3/2.

Ссылки

Аузиелло, Джорджо; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации , Springer .

Минимальный набор с доминирующим ребром (версия оптимизации) — это задача GT3 в Приложении B (стр. 370).

Минимальное максимальное соответствие (версия оптимизации) — это задача GT10 в Приложении B (стр. 374).

Хлебик, Мирослав; Хлебикова, Янка (2006), «Трудность аппроксимации задач множества с доминирующим краем» , Журнал комбинаторной оптимизации , 11 (3): 279–290, doi : 10.1007/s10878-006-7908-0 , S2CID 8024435 .
Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5 .

Множество с доминирующим ребром (версия решения) обсуждается в рамках проблемы доминирующего множества, которая представляет собой проблему GT2 в Приложении A1.1.

Минимально-максимальное сопоставление (вариант решения) — это задача GT10 в Приложении A1.1.

Яннакакис, Михалис ; Гаврил, Фаника (1980), «Множества с доминирующими краями в графах», SIAM Journal on Applied Mathematics , 38 (3): 364–372, CiteSeerX 10.1.1.477.4278 , doi : 10.1137/0138030 , JSTOR 2100648 .
Фудзито, Тошихиро; Нагамоти, Хироши (2002), «Алгоритм двух приближений для задачи о доминирующем множестве с минимальным весом», Discrete Applied Mathematics , 118 (3): 199–207, doi : 10.1016/S0166-218X(00)00383-8 .
Парех, Оджас (2002), «Множества с доминирующим краем и гипосовпадающие множества» , Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 287–291 .
Ричард Шмид и Клаус Виманн (2012), «Аппроксимация множества с доминирующим ребром в плотных графах», Theor. Вычислить. наук. 414(1), стр. 92-99.

Внешние ссылки

Пьерлуиджи Крещенци, Вигго Канн, Магнус Халлдорссон, Марек Карпински, Герхард Вегингер (2000), «Сборник задач оптимизации NP» :

Минимальный набор доминирующих ребер ,

Минимальное максимальное совпадение .