У теорії графів домінівна́ множина́ ре́бер (або реберна домінівна́ множина́) графа 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-складною задачею.
Примітки
Література
.
Найменша домінівна множина ребер (оптимізаційна версія) — задача GT3 в Додатку B (стор. 370). Найменше максимальне парування (оптимізаційна версія) — задача GT10 у Додатку B (стор. 374).
. .
Домінівна множина ребер (у версії розв'язності) обговорюється в задачі про домінівну множину, задачі GT2 в Додатку A1.1. Найменше максимальне парування (у версії розв'язності) — задача GT10 у Додатку A1.1.
.
Посилання Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), «A compendium of NP optimization problems»:
Найменша домінівна множина ребер, Найменше максимальне парування.