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

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

Пример

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

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

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

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

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

$\sigma (n)=\min \{k\mid n\le (\genfrac{}{}{0ex}{}{k}{\lfloor k/2\rfloor })\}$

является обратной функцией центрального биномиального коэффициентаШаблон:Sfn. Фишбурн и ХаммерШаблон:Sfn определили двудольные размерности для некоторых специальных графов. Например, путь $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-полнотеШаблон:Sfn и является прямой переформулировкой другой задачи разрешимости на семействах конечных множеств.

Задача о базисном множестве содержится под номером SP7 в той же книге. Здесь дано семейство подмножеств $𝒮=\{S_1,\dots ,S_n\}$ конечного множества $𝒰$, базисное множество для $𝒮$ — это другое семейство подмножеств $ℬ=\{B_1,\dots ,B_{\ell }\}$ множества $𝒰$, такое, что любое множество из $S_i$ можно представить как объединение некоторых базисных элементов из $ℬ$. Задача о базисном множестве теперь формулируется следующим образом:

ДАНО: Конечное множество $𝒰$, семейство $𝒮=\{S_1,\dots ,S_n\}$ подмножеств множества $𝒰$ и положительное целое число k.

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

В первой формулировке NP-полноту доказал ОрлинШаблон:Sfn даже для двудольных графов. NP-полнота задачи о базисном множестве была доказана раньше СтокмейеромШаблон:Sfn. Задача остаётся NP-трудной, даже если мы ограничимся двудольными графами, двудольная размерность которых не превосходит $O(\log n)$, где n обозначает размер конкретной задачиШаблон:Sfn. Хорошо, однако, что задача разрешима за полиномиальное время на двудольных свободных от домино графовШаблон:Sfn (домино — это лестница высоты 3).

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

Для сравнения, доказательство, что задача является Шаблон:Iw, является упражнением при построении алгоритмов параметрической редукции (как в книге Донвея и ФеллоусаШаблон:Sfn). Фляйшнер, Миджуни, Паулусма и ЗайдерШаблон:Sfn привели также конкретные границы результирующего ядра, которые между тем улучшили Нор, Хермелин, Чарлат и др.Шаблон:Sfn.

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

Приложение

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

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

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

См. также

• Шаблон:Не переведено 5
• Число пересечений графа, минимальное число клик, необходимых для покрытия рёбер графов

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга

Ссылки

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