Домінівна множина ребер

У теорії графів домінівна́ множина́ ре́бер (або реберна домінівна́ множина́) графа G = (V, E) — це підмножина D ⊆ E, така, що будь-яке ребро не з D суміжне щонайменше одному ребру з D. На рисунках (a)–(d) наведено приклади домінівних множин ребер (червоні ребра).

Приклади домінівних множин ребер.

Найме́нша домінівна́ множина́ ре́бер — це домінівна множина ребер найменшого розміру. На рисунках (a) і (b) наведено приклади найменших домінівних множин ребер (можна перевірити, що для даного графа не існує домінівної множини з двох ребер).

Властивості

Домінівна множина ребер для графа G є домінівною множиною реберного графа L(G), і навпаки.

Будь-яке максимальне парування завжди є реберною домінівною множиною. На рисунках (b) та (d) наведено приклади максимальних паросочетань.

Більше того, розмір найменшої домінівної множини ребер дорівнює розміру найменшого максимального парування. Найменше максимальне парування — це найменша домінівна множина ребер. Малюнок (b) дає приклад найменшого максимального парування. Найменша домінівна множина ребер не обов'язково є найменшим максимальним паруванням, що ілюструє малюнок (a). Однак, якщо задано найменшу домінівну множину ребер D, легко знайти найменше максимальне парування з |D| ребрами (див., наприклад, статтю Міхаліса Яннакакіса і Фаніци Гаврила).

Алгоритми та обчислювальна складність

Визначення, чи існує домінівна множина ребер даного розміру для даного графа, є NP-повною задачею (а тому знаходження найменшої домінівної множини ребер є NP-складною задачею). (Міхаліс Яннакакіс) і Фаніца Гаврил показали, що задача є NP-повною навіть для двочасткового графа з найбільшим степенем вершин 3, а також для планарного графа з найбільшим степенем вершин 3.

Існує простий апроксимаційний алгоритм поліноміального часу з коефіцієнтом апроксимації 2 — знаходимо будь-яке максимальне парування. Максимальне парування є домінівною множиною ребер. Більш того, максимальне парування M може бути вдвічі більшим за розміром від найменшого максимального парівання, а найменше максимальне парування має такий самий розмір, що й найменша домінівна множина ребер.

Можна також апроксимувати з коефіцієнтом 2 реберно-зважену версію задачі, але алгоритм значно складніший.

Хлєбіков і Хлєбікова показали, що пошук з коефіцієнтом, кращим ніж (7/6), є NP-складною задачею.

Примітки

1. Yannakakis, Gavril, 1980.
2. Fujito, Nagamochi, 2002.
3. Chlebík, Chlebíková, 2006.

Література

• Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. — 2nd. — Berin, Heidelberg, New York : Springer-Verlag, 2003. — ..

Найменша домінівна множина ребер (оптимізаційна версія) — задача GT3 в Додатку B (стор. 370).

Найменше максимальне парування (оптимізаційна версія) — задача GT10 у Додатку B (стор. 374).

• Miroslav Chlebík, Janka Chlebíková. Approximation hardness of edge dominating set problems // Journal of Combinatorial Optimization. — 2006. — Vol. 11, iss. 3 (16 June). — P. 279–290. — DOI:10.1007/s10878-006-7908-0..
• Michael R. Garey, David S. Johnson. . — W.H. Freeman, 1979. — ..

Домінівна множина ребер (у версії розв'язності) обговорюється в задачі про домінівну множину, задачі GT2 в Додатку A1.1.

Найменше максимальне парування (у версії розв'язності) — задача GT10 у Додатку A1.1.

• Mihalis Yannakakis, Fanica Gavril. Edge dominating sets in graphs // SIAM Journal on Applied Mathematics. — 1980. — Vol. 38, iss. 3 (16 June). — P. 364–372. — DOI:10.1137/0138030..
• Toshihiro Fujito, Hiroshi Nagamochi. A 2-approximation algorithm for the minimum weight edge dominating set problem // Discrete Applied Mathematics. — 2002. — Vol. 118, iss. 3 (16 June). — P. 199–207. — DOI:10.1016/S0166-218X(00)00383-8.

Посилання

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), «A compendium of NP optimization problems»:

Найменша домінівна множина ребер,

Найменше максимальне парування.