 Приклади домінівних множин ребер.
У теорії графів домінівна́ множина́ ре́бер (або реберна домінівна́ множина́) графа 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»:

::  Найменша домінівна множина ребер,
::  Найменше максимальне парування.


