Двочасткова розмірність

найменше число біклік, що покривають усі ребра графу

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

ПрикладРедагувати

Приклад покриття ребер бікліками розібрано в таких діаграмах:

Формули двочасткових розмірностей для деяких графівРедагувати

Двочасткова розмірність повного графа з n вершинами   дорівнює   .

Двочасткова розмірність корони з 2n вершинами дорівнює  , де

 

є оберненою функцією центрального біноміального коефіцієнта[1].

Фішбурн і Гаммер[2] визначили двочасткові розмірності для деяких графів. Наприклад, шлях   має розмірність  , а цикл   має розмірність  .

Обчислення двочасткових розмірностейРедагувати

Задача визначення двочасткової розмірності для заданого графа G є задачею оптимізації. Задача розв'язності для двочасткової розмірності можна перефразувати так:

ДАНО: Граф   і додатне ціле число  .
ПИТАННЯ: Чи містить G біклікове покриття ребер, у якому максимум   біклік?

Ця задача міститься під номером GT18 у класичній книзі Гарея і Джонсона про NP-повноту[3] і є прямим переформулюванням іншої задачі розв'язності на сімействах скінченних множин.

Задача про базисну множину міститься під номером SP7 в тій самій книзі. Тут дано сімейство підмножин   скінченної множини  , базисна множина для   — це інше сімейство підмножин   множини  , така, що будь-яку множину з   можна уявити як об'єднання деяких базисних елементів з  . Задача про базисну множину тепер формулюється так:

ДАНО: Скінченну множину  , сімейство   підмножин множини   і додатне ціле число k.
ПИТАННЯ: Чи існує для   базисна множина, розмір якої не більший від  ?

У першому формулюванні NP-повноту довів Орлін[4] навіть для двочасткових графів. NP-повноту задачі про базисну множину довів раніше Стокмеєр[5]. Задача залишається NP-складною, навіть якщо ми обмежимося двочастковими графами, двочасткова розмірність яких становить менше  , де n позначає розмір конкретної задачі[6]. Добре, однак, що задача розв'язна за поліноміальний час на двочасткових вільних від доміно графів[7] (доміно — це драбина висоти 3).

Щодо існування апроксимаційних алгоритмів Сімон[8] довів, що задачу не можна добре апроксимувати (в припущенні PNP). Більш того, двочасткову розмірність NP-складно апроксимувати для   для будь-якого фіксованого   навіть для двочасткових графів[9].

Для порівняння, доведення, що задача є фіксовано-параметрично розв'язною[en], є вправою під час побудови алгоритмів параметричної редукції (як у книзі Донвея і Феллоуса[10]). Фляйшнер, Міджуні, Паулусма і Зайдер[11] навели також конкретні межі результуючого ядра, які потім поліпшили Нор, Хермелін, Чарлат і ін.[12]

Фактично, для заданого двочасткового графа з n вершинами можна визначити за час  , де  , чи перевищує двочасткова розмірність графа число k[12].

ЗастосуванняРедагувати

Завдання визначення двочасткової розмірності графа виникає в різних контекстах обчислень. Наприклад, у комп'ютерних системах різним користувачам системи може бути дозволено або заборонено доступ до різних ресурсів. При керуванні доступом на основі ролей, роль користувача визначає права доступу до набору ресурсів. Користувач може мати кілька ролей і він може отримати доступ до ресурсів, доступних для однієї з ролей. Роль, у свою чергу, можна призначити декільком користувачам. Задача пошуку ролей полягає у виділенні такого мінімального набору ролей, що для кожного користувача виділені йому ролі гарантують доступ до всіх ресурсів, необхідних користувачеві. Мнгожину користувачів разом зі множиною ресурсів природним чином задає двочастковий граф, ребра якого задають доступ користувачів до ресурсів. Кожна бікліка в такому графі є потенційною роллю, а оптимальним розв'язком задачі пошуку ролей буде саме мінімальне покриття ребер бікліками[13].

Аналогічний сценарій виникає в комп'ютерній безпеці, а саме, в безпечному масовому розсиланні. У цій ситуації потрібно розіслати деякі повідомлення низці приймачів через небезпечний канал. Кожне повідомлення слід зашифрувати деяким ключем шифрування, який відомий тільки приймачу, якому передається повідомлення. Кожен приймач може мати багато ключів шифрування і кожен ключ розсилається на кілька приймачів. Задача оптимального вибору ключів шифрування полягає в знаходженні мінімального набору ключів шифрування, за якого безпечне розсилання буде забезпечено. Як і вище, задачу можна змоделювати з використанням двочасткового графа, в якому мінімальне біклікове покриття ребер збігається з розв'язком задачі оптимального вибору ключів шифрування[14].

Інше застосування стосується біології, де в серології мінімальне покриття ребер бікліками використовується в математичному моделюванні людського лейкоцитарного антигену (HLA)[15].

Див. такожРедагувати

ПриміткиРедагувати

ЛітератураРедагувати

ПосиланняРедагувати