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

В теории графов и комбинаторной оптимизации двудольная размерность или число бикликового покрытия графа 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-полных задач^[англ.]
• Число пересечений графа, минимальное число клик, необходимых для покрытия рёбер графов