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

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

Приклад

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

• 
  Двочастковий граф...
• 
  ... і покриття графу чотирма бікліками:
• 
  червона бікліка покриття,
• 
  синя бікліка покриття,
• 
  зелена бікліка покриття,
• 
  чорна бікліка покриття.

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

Двочасткова розмірність повного графу з n вершинами $K_{n}$ дорівнює $\lceil \log _{2}n\rceil$ .

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

$\sigma (n)=\min \left\{\,k\mid n\leq {\binom {k}{\lfloor k/2\rfloor }}\,\right\}$

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

Фішбурн і Гаммер визначили двочасткові розмірності для деяких графів. Наприклад, шлях $P_{n}$ має розмірність $d(P_{n})=\lfloor n/2\rfloor$, а цикл $C_{n}$ має розмірність $d(C_{n})=\lceil n/2\rceil$.

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

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

ДАНО: Граф $G=(V,E)$ і додатне ціле число $k$.

ПИТАННЯ: Чи містить G біклікове покриття ребер, у якому максимум $k$ біклік?

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

Задача про базисну множину міститься під номером SP7 в тій самій книзі. Тут дано сімейство підмножин ${\mathcal {S}}=\{S_{1},\ldots ,S_{n}\}$ скінченної множини ${\mathcal {U}}$, базисна множина для ${\mathcal {S}}$ - це інше сімейство підмножин ${\mathcal {B}}=\{B_{1},\ldots ,B_{\ell }\}$ множини ${\mathcal {U}}$, така, що будь-яку множину з $S_{i}$ можна уявити як об'єднання деяких базисних елементів з ${\mathcal {B}}$. Задача про базисну множину тепер формулюється так:

ДАНО: Скінченну множину ${\mathcal {U}}$, сімейство ${\mathcal {S}}=\{S_{1},\ldots ,S_{n}\}$ підмножин множини ${\mathcal {U}}$ і додатне ціле число k.

ПИТАННЯ: Чи існує для ${\mathcal {S}}$ базисна множина, розмір якої не більший від $k$?

У першому формулюванні NP-повноту довів Орлін навіть для двочасткових графів. NP-повноту задачі про базисну множину довів раніше Стокмеєр. Задача залишається NP-складною, навіть якщо ми обмежимося двочастковими графами, двочасткова розмірність яких становить менше $O(\log \,\!n)$, де n позначає розмір конкретної задачі. Добре, однак, що задача розв'язна за поліноміальний час на двочасткових вільних від доміно графів (доміно - це драбина висоти 3).

Щодо існування апроксимаційних алгоритмів Сімон довів, що задачу не можна добре апроксимувати (в припущенні P ≠ NP ). Більш того, двочасткову розмірність NP-складно апроксимувати для $|V|^{1/3-\epsilon }$ для будь-якого фіксованого $\epsilon >0$ навіть для двочасткових графів.

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

Фактично, для заданого двочасткового графу з n вершинами можна визначити за час $O(f(k))+n^{3}$, де $f(k)=2^{k2^{k-1}+3k}$, чи перевищує двочасткова розмірність графу число k.

Застосування

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

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

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

Див. також

• Список NP-повних задач
• Число перетинів графу - найменше число клік, необхідних для покриття ребер графів

Література

• Jérôme Amilhastre, Philippe Janssen, Marie-Catherine Vilarem. Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5–7 January 1997, New Orleans, Louisiana. — ACM/SIAM, 1997. — С. 36–42.
• Dominique de Caen, David A. Gregory, Norman J. Pullman. 3rd Caribbean Conference on Combinatorics and Computing / Charles C. Cadogan. — Department of Mathematics, University of the West Indies, 1981. — С. 169–173.
• Rod Downey, Michael R. Fellows. Parameterized complexity. — Springer, 1999. — ISBN 0-387-94883-X.
• Alina Ene, William G. Horne, Nikola Milosavljevic, Prasad Rao, Robert Schreiber, Robert Endre Tarjan. 13th ACM Symposium on Access Control Models and Technologies (SACMAT 2008) / Indrakshi Ray, Ninghui Li. — ACM, 2008. — С. 1–10.
• Peter C. Fishburn, Peter Ladislaw Hammer. Bipartite dimensions and bipartite degrees of graphs // Discrete Mathematics. — 1996. — Т. 160, вип. 1–3 (14 червня). — С. 127–148. — DOI:10.1016/0012-365X(95)00154-O.
• Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, Stefan Szeider. Covering graphs with few complete bipartite subgraphs // Theoretical Computer Science. — 2009. — Т. 410, вип. 21—23 (14 червня). — С. 2045–2053. — DOI:10.1016/j.tcs.2008.12.059.
• 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.
• Lee-Ad J. Gottlieb, John E. Savage, Arkady Yerukhimovich. Efficient data storage in large nanoarrays // Theory of Computing Systems. — 2005. — Т. 38, вип. 4 (14 червня). — С. 503–536. — DOI:10.1007/s00224-004-1196-9.
• Hermann Gruber, Markus Holzer. 11th International Conference on Developments in Language Theory (DLT 2007) / Terjo Harju, Juhani Karhumäki, Arto Lepistö. — Turku, Finland : Springer, 2007. — Т. 4588. — С. 205–216. — (LNCS) — DOI:10.1007/978-3-540-73208-2_21.
• Sylvia D. Monson, Norman J. Pullman, Rolf Rees. A survey of clique and biclique coverings and factorizations of (0,1)-matrices // Bulletin of the ICA. — 1995. — Т. 14 (14 червня). — С. 17–86.
• D. S. Nau, G. Markowsky, M. A. Woodbury, D. B. Amos. A mathematical analysis of human leukocyte antigen serology // Mathematical Biosciences. — 1978. — Т. 40 (14 червня). — С. 243–270. — DOI:10.1016/0025-5564(78)90088-3.
• Igor Nor, Danny Hermelin, Sylvain Charlat, Jan Engelstadter, Max Reuter, Olivier Duron, Marie-France Sagot. Mod/Resc Parsimony Inference. — 2010. — 14 червня.
• James Orlin. Contentment in graph theory: covering graphs with cliques // Indagationes Mathematicae. — 1977. — Т. 80, вип. 5 (14 червня). — С. 406–424. — DOI:10.1016/1385-7258(77)90055-5.
• Guoqiang Shu, David Lee, Mihalis Yannakakis. 20th International Parallel and Distributed Processing Symposium (IPDPS 2006). — IEEE, 2006.
• Hans-Ulrich Simon. On Approximate Solutions for Combinatorial Optimization Problems // SIAM Journal on Discrete Mathematics. — 1990. — Т. 3, вип. 2 (14 червня). — С. 294–310. — DOI:10.1137/0403025.
• Larry J. Stockmeyer. The set basis problem is NP-complete. — IBM, 1975. — (Technical Report RC-5431)

Посилання

• Стаття Девіда Еппштейна про двочасткову розмірність (англ.)