Двудольное измерение

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

Пример [ править ]

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

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

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

Двудольный размерность N -vertex полного графа , является . ${\ displaystyle K_ {n}}$ ${\ Displaystyle \ lceil \ log _ {2} п \ rceil}$

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

{\ Displaystyle \ сигма (п) = \ мин \ влево \ {\, к \ середина п \ leq {\ binom {k} {\ lfloor k / 2 \ rfloor}} \, \ right \}}

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

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

Fishburn & Hammer (1996) определяют двудольную размерность некоторых специальных графов. Например, путь есть, а есть цикл . ${\ displaystyle P_ {n}}$ ${\ displaystyle d (P_ {n}) = \ lfloor n / 2 \ rfloor}$ ${\ displaystyle C_ {n}}$ ${\ Displaystyle д (C_ {п}) = \ lceil п / 2 \ rceil}$

Вычисление двудольного измерения [ править ]

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

ЭКЗЕМПЛЯР: график и положительное целое число .

{\ Displaystyle G = (V, E)}

{\ displaystyle k}

ВОПРОС: Допускает ли G бикликовое краевое покрытие, содержащее не более бикликов?

{\ displaystyle k}

Эта проблема появляется как проблема GT18 в классической книге Гэри и Джонсона о NP- полноте и представляет собой довольно прямую переформулировку другой проблемы принятия решений для семейств конечных множеств.

Проблема набора базисов фигурирует как проблема 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}}}$

Пример: конечное множество , семейство подмножеств и положительное целое число k .

{\ displaystyle {\ mathcal {U}}}

{\ Displaystyle {\ mathcal {S}} = \ {S_ {1}, \ ldots, S_ {n} \}}

{\ displaystyle {\ mathcal {U}}}

ВОПРОС: Существует ли набор размеров максимум для ?

{\ displaystyle k}

{\ Displaystyle {\ mathcal {S}}}

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

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

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

Приложения [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Амилхастр, Жером; Янссен, Филипп; Виларем, Мари-Катрин (1997), «Вычисление минимального бикликового покрытия является полиномом для двудольных графов без домино», Труды восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, 5–7 января 1997 года, Новый Орлеан, Луизиана. , ACM / SIAM, стр. 36–42.
де Кан, Доминик; Грегори, Дэвид А .; Пуллман, Норман Дж. (1981), «Булев ранг матриц нуля или единицы», в Cadogan, Charles C. (ed.), 3rd Caribbean Conference on Combinatorics and Computing , Department of Mathematics, University of West Indies, pp. 169–173, MR 0657202..
Дауни, Род ; Товарищи, Майкл Р. (1999), Параметризованная сложность , Springer, ISBN 0-387-94883-X.
Эне, Алина; Хорн, Уильям Дж .; Милосавлевич, Никола; Рао, Прасад; Шрайбер, Роберт; Тарджан, Роберт Эндре (2008), «Быстрые точные и эвристические методы для задач минимизации ролей», в Рэй, Индракши; Ли, Нинхуэй (ред.), 13-й симпозиум ACM по моделям и технологиям контроля доступа (SACMAT 2008) , ACM, стр. 1–10.
Фишберн, Питер С .; Хаммер, Питер Лэдислав (1996), "Двудольные измерения и двудольные степени графов", Дискретная математика , 160 (1–3): 127–148, DOI : 10.1016 / 0012-365X (95) 00154-O.
Флейшнер, Герберт; Муджуни, Эгберт; Паулюсма, Даниэль; Szeider, Стефан (2009), "Покрытие графы с нескольких полных подграфов двудольных", Теоретическая информатика , 410 (21-23): 2045-2053, DOI : 10.1016 / j.tcs.2008.12.059.
Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5.
Gottlieb, Lee-Ad J .; Сэвидж, Джон Э .; Yerukhimovich, Аркадий (2005), "Эффективное хранение данных в больших nanoarrays", Теория вычислительных систем , 38 (4): 503-536, DOI : 10.1007 / s00224-004-1196-9.
Грубер, Германн; Хольцер, Маркус (2007), «Неприблизимость недетерминированного состояния и сложность перехода в предположении P <> NP.», В Харью, Терьо; Кархумяки, Юхани; Lepistö, Арто (ред.), 11 - я Международная конференция по достижениям в теории языка (DLT 2007) , LNCS, 4588 , Турку, Финляндия:. Springer, С. 205-216, DOI : 10.1007 / 978-3-540-73208-2_21.
Го, Кристал; Huynh, Тони; Macchia, Марко (2019), "О Biclique Перекрытия Количество Сетки", Электронный журнал комбинаторике , 26 (4), DOI : 10,37236 / 8316.
Монсон, Сильвия Д .; Пуллман, Норман Дж .; Рис, Рольф (1995), "Обзор кликовых и бикликовых покрытий и факторизации (0,1) -матриц", Бюллетень ICA , 14 : 17–86, MR 1330781.
Nau, DS; Марковский, Г .; Вудбери, Массачусетс; Эймос, Д. Б. (1978), "Математический анализ человеческого лейкоцитарного антигена серологических" (PDF) , Математическая Biosciences , 40 (3-4): 243-270, DOI : 10,1016 / 0025-5564 (78) 90088-3.
И Игорь; Гермелин, Дэнни; Шарлат, Сильвен; Энгельштадтер, Ян; Рейтер, Макс; Дюрон, Оливье; Саго, Мари-Франс (2010), «Mod / Resc Parsimony Inference», комбинаторное сопоставление шаблонов, конспект лекций по информатике, 6129 , стр. 202–213, arXiv : 1002.1292 , doi : 10.1007 / 978-3-642-13509 -5_19 , ISBN 978-3-642-13508-8
Орлин, Джеймс (1977), "Удовлетворенность в теории графов: покрывающие графы с кликами", Indagationes Mathematicae , 80 (5): 406-424, DOI : 10,1016 / 1385-7258 (77) 90055-5 CS1 maint: discouraged parameter (link).
Шу, Гоцян; Ли, Дэвид; Яннакакис, Михалис (2006), «Заметка об управлении ключами широковещательного шифрования с приложениями для крупномасштабных систем оповещения о чрезвычайных ситуациях», 20-й Международный симпозиум по параллельной и распределенной обработке (IPDPS 2006) , IEEE.
Саймон, Ханс-Ульрих (1990), "О приближенных решений для задач комбинаторной оптимизации", SIAM журнал по дискретной математике , 3 (2): 294-310, DOI : 10,1137 / 0403025.
Стокмейер, Ларри Дж. (1975), Проблема набора базисов является NP-полной , Технический отчет RC-5431, IBM.

Внешние ссылки [ править ]

блог записи о двудольном измерении по Дэвиду Eppstein