Набор, доминирующий на краю

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

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

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

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

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

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

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

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

Chlebík & Chlebíková (2006) показывают, что нахождение приближения, лучшего, чем (7/6), является NP-трудным. Schmied & Viehmann доказали, что задачу UGC-трудно приблизить с точностью до любой константы, лучшей, чем 3/2.

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

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

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

• Хлебик, Мирослав; Хлебикова, Янка (2006), «Твердость аппроксимации задач множества с доминирующим ребром», Journal of Combinatorial Optimization , 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), «Алгоритм 2-приближения для задачи о минимальном весе доминирования множества ребер», Дискретная прикладная математика , 118 (3): 199–207, doi :10.1016/S0166-218X(00)00383-8.
• Парех, Оджас (2002), «Наборы с доминирующими ребрами и гипосовпадающими множествами», Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 287–291.
• Ричард Шмид и Клаус Виманн (2012), «Аппроксимация множества доминирующих ребер в плотных графах», Теор. вычисл. науки 414(1), стр. 92-99.

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

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

Минимально-максимальное соответствие.