Двустороннее измерение

В математических областях теории графов и комбинаторной оптимизации двудольная размерность или число бикликового покрытия графа всех 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\}

является обратной функцией центрального биномиального коэффициента ( де Кан, Грегори и Пулман, 1981 ).

Двустороннее измерение $n\times m$ граф решётчатый ${\frac {nm}{2}}-1$ , если $m$ четный и $n-1=k(m-1)+2\ell$ для некоторых целых чисел $0\leq \ell <k$ ; и есть ${\big \lfloor }{\frac {nm}{2}}{\big \rfloor }$ в противном случае ( Guo, Huynh & Macchia 2019 ).

Фишберн и Хаммер (1996) определяют двудольную размерность некоторых специальных графов. Например, путь $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 .

ВОПРОС: Существует ли установленный базис максимального размера

k

для

{\mathcal {S}}

?

доказал, что проблема NP -полна В своей прежней формулировке Орлин (1977) даже для двудольных графов . было доказано, что формулировка задачи базиса множеств является NP Ранее Стокмейером (1975) -полной . Проблема остается NP -трудной, даже если мы ограничимся двудольными графами, двудольная размерность которых гарантированно не превышает $O(\log \,\!n)$ , где n обозначает размер данного экземпляра задачи ( Готлиб, Сэвидж и Ерухимович, 2005 ). Положительным моментом является то, что проблема разрешима за полиномиальное время на двудольных графах без домино ( Amilhastre, Janssen & Vilarem 1997 ).

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

Напротив, доказательство того, что проблема разрешима с фиксированными параметрами, представляет собой упражнение по разработке алгоритмов кернеризации , которое появляется как таковое в учебнике Дауни и Феллоуз (1999) . Флейшнер и др. (2009) также дают конкретные ограничения на размер получаемого ядра, которые тем временем были улучшены Nor et al. (2010) .Фактически, для данного двудольного графа с n вершинами можно решить за время $O(f(k))+n^{3}$ с $f(k)=2^{k2^{k-1}+3k}$ не превышает ли его двудольная размерность k ( Nor et al. 2010 )

Приложения

Проблема определения двудольной размерности графа возникает в различных контекстах вычислений. Например, в компьютерных системах разным пользователям системы может быть разрешен или запрещен доступ к различным ресурсам. В системе управления доступом на основе ролей роль предоставляет права доступа к набору ресурсов. Пользователь может владеть несколькими ролями, и у него есть разрешение на доступ ко всем ресурсам, предоставленным некоторыми из его ролей. Кроме того, роль может принадлежать нескольким пользователям. Задача анализа ролей состоит в том, чтобы найти минимальный набор ролей, такой, чтобы каждому пользователю его роли, вместе взятые, предоставляли доступ ко всем указанным ресурсам. Набор пользователей вместе с набором ресурсов в системе естественным образом образуют двудольный граф, ребра которого являются разрешениями. Каждая биклика в этом графе представляет собой потенциальную роль, и оптимальным решением проблемы анализа ролей являются именно минимальные покрытия ребер биклики ( Ene et al. 2008 ).

Похожий сценарий известен в области компьютерной безопасности , а точнее, в области защищенного вещания . В этой настройке необходимо отправить несколько сообщений каждому набору получателей по незащищенному каналу. Каждое сообщение должно быть зашифровано с использованием некоторого криптографического ключа, известного только предполагаемым получателям. Каждый получатель может обладать несколькими ключами шифрования, и каждый ключ будет распространяться среди нескольких получателей. Задача генерации оптимальных ключей состоит в том, чтобы найти минимальный набор ключей шифрования для обеспечения безопасной передачи. Как и выше, проблему можно смоделировать с помощью двудольного графа, минимальные покрытия ребер которого совпадают с решениями задачи оптимальной генерации ключей ( Шу, Ли и Яннакакис, 2006 ).

Другое применение находится в биологии, где минимальные двусторонние края используются в математических моделях серологии человеческого лейкоцитарного антигена (HLA) ( Nau et al. 1978 ).

См. также

Список NP-полных задач
Число пересечений (теория графов) — минимальное количество клик , необходимое для покрытия ребер графа.

Ссылки

Амильястр, Жером; Янссен, Филипп; Виларем, Мари-Катрин (1997), «Вычисление минимального бикликового покрытия полиномиально для двудольных графов без домино», Труды восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, 5–7 января 1997 г., Новый Орлеан, Луизиана. , ACM/SIAM, стр. 36–42, ISBN. 9780898713909
де Кан, Доминик; Грегори, Дэвид А.; Пуллман, Норман Дж. (1981), «Булев ранг матриц ноль-единица», в Кадогане, Чарльз К. (редактор), 3-я Карибская конференция по комбинаторике и информатике , факультет математики, Вест-Индский университет, стр. 169–173, МР 0657202 .
Дауни, Род ; Товарищи, Майкл Р. (1999), Параметризованная сложность , Springer, ISBN 0-387-94883-Х .
Эне, Алина; Хорн, Уильям Г.; Милосавлевич, Никола; Рао, Прасад; Шрайбер, Роберт; Тарьян, Роберт Эндре (2008), «Быстрые точные и эвристические методы для задач минимизации ролей», Рэй, Индракши; Ли, Нинхуэй (ред.), 13-й симпозиум ACM по моделям и технологиям контроля доступа (SACMAT 2008) , ACM, стр. 1–10 .
Фишберн, Питер С .; Хаммер, Питер Ладислав (1996), «Двудольные измерения и двудольные степени графов», Discrete Mathematics , 160 (1–3): 127–148, doi : 10.1016/0012-365X(95)00154-O .
Флейшнер, Герберт; Муджуни, Эгберт; Паулюсма, Даниэль; Зейдер, Стефан (2009), «Покрытие графов несколькими полными двудольными подграфами», Theoretical Computer Science , 410 (21–23): 2045–2053, doi : 10.1016/j.tcs.2008.12.059 .
Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5 .
Готлиб, Ли-Эд Дж.; Сэвидж, Джон Э .; Ерухимович, Аркадий (2005), «Эффективное хранение данных в больших наномассивах», Теория вычислительных систем , 38 (4): 503–536, doi : 10.1007/s00224-004-1196-9 , S2CID 5844939 .
Грубер, Герман; Хольцер, Маркус (2007), «Неаппроксимируемость недетерминированного состояния и сложность перехода при условии P <> NP.», в Харью, Терджо; Кархумяки, Юхани; Леписто, Арто (ред.), 11-я Международная конференция по развитию теории языка (DLT 2007) , LNCS, vol. 4588, Турку, Финляндия: Springer, стр. 205–216, doi : 10.1007/978-3-540-73208-2_21 .
Го, Кристал; Хьюнь, Тони; Маккиа, Марко (2019), «Биклика, покрывающая число сеток», Электронный журнал комбинаторики , 26 (4), arXiv : 1811.03396 , doi : 10.37236/8316 .
Монсон, Сильвия Д.; Пуллман, Норман Дж.; Рис, Рольф (1995), «Обзор кликовых и биклических накрытий и факторизаций (0,1)-матриц», Бюллетень ICA , 14 : 17–86, MR 1330781 .
Нау, Д.С.; Марковский, Г.; Вудбери, Массачусетс; Амос, Д.Б. (1978), «Математический анализ серологии человеческого лейкоцитарного антигена» (PDF) , Mathematical Biosciences , 40 (3–4): 243–270, doi : 10.1016/0025-5564(78)90088-3 .
И, Игорь; Гермелин, Дэнни; Шарла, Сильвен; Энгельштадтер, Ян; Рейтер, Макс; Дюрон, Оливье; Саго, Мари-Франс (2010), «Вывод сэкономленности Mod/Resc», Сопоставление комбинаторных шаблонов , Конспекты лекций по информатике, том. 6129, стр. 202–213, arXiv : 1002.1292 , doi : 10.1007/978-3-642-13509-5_19 , ISBN 978-3-642-13508-8 , S2CID 6675399
Орлин, Джеймс (1977), «Удовлетворенность в теории графов: покрытие графов кликами», Indagationes Mathematicae , 80 (5): 406–424, doi : 10.1016/1385-7258(77)90055-5 .
Шу, Гоцян; Ли, Дэвид; Яннакакис, Михалис (2006), «Заметка об управлении ключами шифрования широковещательной передачи с приложениями для крупномасштабных систем оповещения о чрезвычайных ситуациях», 20-й Международный симпозиум по параллельной и распределенной обработке (IPDPS 2006) , IEEE .
Саймон, Ханс-Ульрих (1990), «О приближенных решениях задач комбинаторной оптимизации», SIAM Journal on Discrete Mathematics , 3 (2): 294–310, doi : 10.1137/0403025 .
Стокмейер, Ларри Дж. (1975), Задача базиса множества является NP-полной , Технический отчет RC-5431, IBM .

Внешние ссылки

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