Домінівна множина ребер
У теорії графів домінівна́ множина́ ре́бер (або реберна домінівна́ множина́) графа G = (V, E) — це підмножина D ⊆ E, така, що будь-яке ребро не з D суміжне щонайменше одному ребру з D. На рисунках (a)–(d) наведено приклади домінівних множин ребер (червоні ребра).
Найме́нша домінівна́ множина́ ре́бер — це домінівна множина ребер найменшого розміру. На рисунках (a) і (b) наведено приклади найменших домінівних множин ребер (можна перевірити, що для даного графа не існує домінівної множини з двох ребер).
Домінівна множина ребер для графа G є домінівною множиною реберного графа L(G), і навпаки.
Будь-яке максимальне парування завжди є реберною домінівною множиною. На рисунках (b) та (d) наведено приклади максимальних паросочетань.
Більше того, розмір найменшої домінівної множини ребер дорівнює розміру найменшого максимального парування. Найменше максимальне парування — це найменша домінівна множина ребер. Малюнок (b) дає приклад найменшого максимального парування. Найменша домінівна множина ребер не обов'язково є найменшим максимальним паруванням, що ілюструє малюнок (a). Однак, якщо задано найменшу домінівну множину ребер D, легко знайти найменше максимальне парування з |D| ребрами (див., наприклад, статтю Міхаліса Яннакакіса і Фаніци Гаврила[1]).
Визначення, чи існує домінівна множина ребер даного розміру для даного графа, є NP-повною задачею (а тому знаходження найменшої домінівної множини ребер є NP-складною задачею). Міхаліс Яннакакіс і Фаніца Гаврил[1] показали, що задача є NP-повною навіть для двочасткового графа з найбільшим степенем вершин 3, а також для планарного графа з найбільшим степенем вершин 3.
Існує простий апроксимаційний алгоритм поліноміального часу з коефіцієнтом апроксимації 2 — знаходимо будь-яке максимальне парування. Максимальне парування є домінівною множиною ребер. Більш того, максимальне парування M може бути вдвічі більшим за розміром від найменшого максимального парівання, а найменше максимальне парування має такий самий розмір, що й найменша домінівна множина ребер.
Можна також апроксимувати з коефіцієнтом 2 реберно-зважену версію задачі, але алгоритм значно складніший[2].
Хлєбіков і Хлєбікова[3] показали, що пошук з коефіцієнтом, кращим ніж (7/6), є NP-складною задачею.
- 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. — ISBN 3-540-65431-3..
- Найменша домінівна множина ребер (оптимізаційна версія) — задача 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 (5 November). — P. 279–290. — DOI:..
- Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W.H. Freeman, 1979. — ISBN 0-7167-1045-5..
- Домінівна множина ребер (у версії розв'язності) обговорюється в задачі про домінівну множину, задачі 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 (5 November). — P. 364–372. — DOI:..
- Toshihiro Fujito, Hiroshi Nagamochi. A 2-approximation algorithm for the minimum weight edge dominating set problem // Discrete Applied Mathematics. — 2002. — Vol. 118, iss. 3 (5 November). — P. 199–207. — DOI:.
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), «A compendium of NP optimization problems»: