Двудольная размерность

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

Пример покрытия рёбер бикликами дан в следующих диаграммах:

• Пример покрытия рёбер бикликами
• 
  Двудольный граф...
• 
  ...и покрытие графа четырьмя бикликами
• 
  красная биклика покрытия
• 
  синяя биклика покрытия
• 
  зелёная биклика покрытия
• 
  чёрная биклика покрытия

Бикликовая размерность полного графа с n вершинами ${\displaystyle K_{n}}$ равна ${\displaystyle \lceil \log _{2}n\rceil }$.

Двудольная размерность короны с 2n вершинами равна ${\displaystyle \sigma (n)}$, где

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

является обратной функцией центрального биномиального коэффициента^[1]. Фишбурн и Хаммер^[2] определили двудольные размерности для некоторых специальных графов. Например, путь ${\displaystyle P_{n}}$ имеет размерность ${\displaystyle d(P_{n})=\lfloor n/2\rfloor }$, а цикл ${\displaystyle C_{n}}$ имеет размерность ${\displaystyle d(C_{n})=\lceil n/2\rceil }$.

Задача определения двудольной размерности для заданного графа G является задачей оптимизации. Задачу разрешимости для двудольной размерности можно перефразировать так:

ДАНО: Граф ${\displaystyle G=(V,E)}$ и положительное целое число ${\displaystyle k}$.

ВОПРОС: Содержит ли G бикликовое покрытие рёбер, в котором максимум ${\displaystyle k}$ биклик?

Эта задача содержится под номером GT18 в классической книге Гарея и Джонсона о NP-полноте^[3] и является прямой переформулировкой другой задачи разрешимости на семействах конечных множеств.

Задача о базисном множестве содержится под номером SP7 в той же книге. Здесь дано семейство подмножеств ${\displaystyle {\mathcal {S}}=\{S_{1},\ldots ,S_{n}\}}$ конечного множества ${\displaystyle {\mathcal {U}}}$, базисное множество для ${\displaystyle {\mathcal {S}}}$ — это другое семейство подмножеств ${\displaystyle {\mathcal {B}}=\{B_{1},\ldots ,B_{\ell }\}}$ множества ${\displaystyle {\mathcal {U}}}$, такое, что любое множество из ${\displaystyle S_{i}}$ можно представить как объединение некоторых базисных элементов из ${\displaystyle {\mathcal {B}}}$. Задача о базисном множестве теперь формулируется следующим образом:

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

ВОПРОС: Существует ли для ${\displaystyle {\mathcal {S}}}$ базисное множество, размер которого не больше ${\displaystyle k}$?

В первой формулировке NP-полноту доказал Орлин^[4] даже для двудольных графов. NP-полнота задачи о базисном множестве была доказана раньше Стокмейером^[5]. Задача остаётся NP-трудной, даже если мы ограничимся двудольными графами, двудольная размерность которых не превосходит ${\displaystyle O(\log \,\!n)}$, где n обозначает размер конкретной задачи^[6]. Хорошо, однако, что задача разрешима за полиномиальное время на двудольных свободных от домино графов^[7] (домино — это лестница высоты 3).

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

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

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

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

Аналогичный сценарий возникает в компьютерной безопасности, конкретнее, в безопасной широковещательной рассылке. В этой ситуации необходимо разослать некоторые сообщения ряду приёмников через небезопасный канал. Каждое сообщение необходимо зашифровать некоторым ключом шифрования, который известен только приёмнику, на который передаётся сообщение. Каждый приёмник может иметь много ключей шифрования и каждый ключ рассылается на несколько приёмников. Задача оптимального выбора ключей шифрования заключается в нахождении минимального набора ключей шифрования, при котором безопасная рассылка будет обеспечена. Как и выше, задачу можно смоделировать с использованием двудольного графа, в котором минимальное бикликовое покрытие рёбер совпадает с решением задачи оптимального выбора ключей шифрования^[14].

Другое приложение находится в биологии, где минимальное покрытие рёбер бикликами используется в математическом моделировании человеческого лейкоцитарного антигена (HLA) в серологии^[15].

• Список 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. — С. 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. — С. 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. — С. 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. — С. 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. — С. 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.
• James Orlin. Contentment in graph theory: covering graphs with cliques // Indagationes Mathematicae. — 1977. — Т. 80, вып. 5. — С. 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. — С. 294–310. — doi:10.1137/0403025.
• Larry J. Stockmeyer. The set basis problem is NP-complete. — IBM, 1975. — (Technical Report RC-5431).

• Статья о двудольной размерности Дэвида Эппштейна