Плотный подграф

В теории графов и информатике плотный подграф — это подграф с множеством ребер на вершину. Это формализуется следующим образом: пусть $G$ $= (V, E)$ — неориентированный граф , а $S = (V S, E S)$ — подграф $G$ . Тогда плотность S определяется как:

d(S)={|E_{S}| \over |V_{S}|}

Самая плотная задача подграфа — это нахождение подграфа максимальной плотности. Плотность максимально плотного подграфа графа иногда называют плотностью его подграфа . В 1984 году Эндрю В. Голдберг разработал полиномиальный алгоритм для нахождения подграфа максимальной плотности с использованием метода максимального потока . Он был улучшен Галло, Григориадисом и Тарьяном в 1989 году ^[1] для выполнения за время $O (nm log(n 2 / m))$ . Простой LP для нахождения оптимального решения был предложен Чарикаром в 2000 году. ^[2]

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

Самый плотныйкподграф

Существует множество вариаций задачи о самом плотном подграфе. Одна из них — задача о самом плотном $k$ -подграфе, где цель состоит в том, чтобы найти подграф максимальной плотности ровно на $k$ вершинах. Эта задача обобщает задачу о клике и, таким образом, является NP-трудной в общих графах. Существует полиномиальный алгоритм, аппроксимирующий самый плотный $k-$ подграф в пределах отношения для каждого , ^[3] в то время как он не допускает -аппроксимации за полиномиальное время, если только гипотеза об экспоненциальном времени не ложна. ^[4] При более слабом предположении, что , для задачи не существует PTAS . ^[5] $n^{1/4\,+\,\epsilon }$ $\epsilon >0$ $n^{1/\!\operatorname {полилоглог} n}$ ${\mathsf {NP}}\nsubseteq \bigcap _{\epsilon >0}{\mathsf {BPTIME}}(2^{n^{\epsilon }})$

Задача остаётся NP-трудной в двудольных графах и хордовых графах , но является полиномиальной для деревьев и разветвлённых графов . ^[6] Открыто, является ли задача NP-трудной или полиномиальной в (собственных) интервальных графах и планарных графах ; однако, вариация задачи, в которой требуется, чтобы подграф был связным, является NP-трудной в планарных графах. ^[7]

Самая плотная в максимумекподграф

Целью задачи о наиболее плотном подграфе является нахождение подграфа максимальной плотности на не более чем вершинах. Андерсен и Челлапилла показали, что если существует -аппроксимация для этой задачи, то это приведет к -аппроксимации для задачи о наиболее плотном подграфе. ^[8] Позже это было улучшено Хуллером и Саха , которые показали, что -аппроксимация для наиболее плотном подграфе подразумевает -аппроксимацию для задачи о наиболее плотном подграфе. ^[9] $к$ $к$ $\альфа$ $\Тета (\альфа ^{2})$ $к$ $\альфа$ $к$ $4\альфа$ $к$

Самый плотный по крайней мерекподграф

Задача о самом плотном минимуме определяется аналогично задаче о самом плотном максимуме подграфе. Задача является NP-полной, ^[9] но допускает 2-аппроксимацию за полиномиальное время. ^[10] Более того, есть некоторые свидетельства того, что этот алгоритм аппроксимации по сути является наилучшим из возможных: если принять гипотезу о небольшом расширении множества (предположение о вычислительной сложности, тесно связанное с гипотезой об уникальных играх ), то аппроксимировать задачу с точностью до множителя для каждой константы NP-трудно . ^[11] $к$ $к$ $(2-\epsilon)$ $\epsilon >0$

К-clique плотнейший подграф

Харалампос Цуракакис представил задачу о самом плотном подграфе -клики. Эта вариация задачи о самом плотном подграфе направлена на максимизацию среднего числа индуцированных клик , где — множество -клик, индуцированных . Обратите внимание, что задача о самом плотном подграфе получается как частный случай для . Это обобщение обеспечивает эмпирически успешный подход поливремени для извлечения больших почти-клик из крупномасштабных сетей реального мира. $к$ $к$ $d_{k}(S)={|C_{k}(S)| \over |V_{S}|}$ $C_{k}(S)$ $к$ $S$ $к=2$

Локально топ-ксамый плотный подграф

Цинь и др. представили задачу обнаружения топ -k локально плотных подграфов в графе, каждый из которых достигает наивысшей плотности в своей локальной области в графе: он не содержится ни в одном суперграфе с такой же или большей плотностью, и не содержит подграфов с плотностью, слабо связанной с остальной частью локального плотного подграфа. Обратите внимание, что задача о самом плотном подграфе получается как частный случай для . Множество локально плотных подграфов в графе можно вычислить за полиномиальное время. $к=1$

Ссылки

^ Галло, Джорджио; Григориадис, Майкл Д.; Тарьян, Роберт Э. (1989), «Быстрый параметрический алгоритм максимального потока и его применение», SIAM Journal on Computing , 18 (1): 30–55, doi :10.1137/0218003, MR 0978165
^ Чарикар, Моисей (2000), «Жадные аппроксимационные алгоритмы для поиска плотных компонентов в графе», в Янсен, Клаус; Хуллер, Самир (ред.), Аппроксимационные алгоритмы для комбинаторной оптимизации, Третий международный семинар, APPROX 2000, Саарбрюккен, Германия, 5-8 сентября 2000 г., Труды , Lecture Notes in Computer Science, т. 1913, Springer, стр. 84–95, doi :10.1007/3-540-44436-X_10, ISBN 978-3-540-67996-7
^ Бхаскара, Адитья; Чарикар, Моисей ; Хламтач, Эден; Фейге, Уриэль ; Виджаярагхаван, Аравиндан (2010), «Обнаружение высоких логарифмических плотностей — приближение $O$ $($ $n$ $1/4$ $)$ для самого плотного $k$ -подграфа», STOC'10 — Труды Международного симпозиума ACM 2010 года по теории вычислений , ACM, Нью-Йорк, стр. 201–210, doi :10.1145/1806689.1806719, ISBN 9781450300506, MR 2743268, S2CID 1391318.
^ Manurangsi, Pasin (2017), "Почти полиномиальное отношение ETH-трудности аппроксимирующего плотнейшего k-подграфа", STOC'17 — Труды 49-го ежегодного симпозиума ACM SIGACT по теории вычислений , ACM, стр. 954–961, arXiv : 1611.05991 , doi : 10.1145/3055399.3055412, ISBN 9781450345286, S2CID 1892186.
^ Хот, Субхаш (2006), «Исключение PTAS для графа min-bisection, плотного $k$ -подграфа и двудольной клики», SIAM Journal on Computing , 36 (4): 1025–1071, CiteSeerX 10.1.1.114.3324 , doi :10.1137/S0097539705447037, MR 2272270, S2CID 16514252 .
^ Корнейл, Д.Г.; Перл, И. (1984), «Кластеризация и доминирование в совершенных графах», Дискретная прикладная математика , 9 (1): 27–39, doi : 10.1016/0166-218X(84)90088-X , MR 0754426.
^ Кейл, Дж. Марк; Брехт, Тимоти Б. (1991), «Сложность кластеризации в планарных графах» (PDF) , Журнал комбинаторной математики и комбинаторных вычислений , 9 : 155–159, MR 1111849.
^ Андерсен, Рид; Челлапилла, Кумар (2009). «Поиск плотных подграфов с ограничениями по размеру». В Авраченков, Константин; Донато, Дебора; Литвак, Нелли (ред.). Алгоритмы и модели для веб-графа . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. стр. 25–37. doi :10.1007/978-3-540-95995-3_3. ISBN 978-3-540-95995-3.
^ ab Khuller, Samir ; Saha, Barna (2009), "On find thick subgraphs" (PDF) , Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I , Lecture Notes in Computer Science, vol. 5555, Berlin: Springer-Verlag, pp. 597–608, CiteSeerX 10.1.1.722.843 , doi :10.1007/978-3-642-02927-1_50, ISBN 978-3-642-02926-4, г-н 2544878
^ Андерсен, Рид (2007), Поиск больших и малых плотных подграфов , arXiv : cs/0702032 , Bibcode : 2007cs........2032A
^ Manurangsi, Pasin (2018), "Неаппроксимируемость задач максимальной биклики, минимального $k$ -разреза и плотнейшего по крайней мере $k$ -подграфа из гипотезы расширения малого множества", Алгоритмы , 11 (1): 10, arXiv : 1705.03581 , doi : 10.3390/a11010010 , MR 3758880

Дальнейшее чтение

Андерсен, Р.; Челлапилла, К. (2009), «Поиск плотных подграфов с ограничениями по размеру», WAW : 25–36.
Фейге, У.; Кортсарц, Г.; Пелег, Д. (1997), «Проблема плотного $k$ -подграфа», Algorithmica , 29 (3): 410–421, CiteSeerX 10.1.1.25.9443 , doi :10.1007/s004530010050, S2CID 8354738.
Голдберг, А.В. (1984), «Нахождение подграфа максимальной плотности», Технический отчет.
Цуракакис, К. (2015), «Проблема самого плотного подграфа K-клики», Труды 24-й Международной конференции по всемирной паутине , стр. 1122–1132, CiteSeerX 10.1.1.695.7667 , doi :10.1145/2736277.2741098, ISBN 9781450334693, S2CID 14586622.
Qin, Lu; Li, Rong{-}Hua; Chang, Lijun; Zhang, Chengqi (2015), "Locally density subgraph discovery", в Cao, Longbing; Zhang, Chengqi; Joachims, Thorsten; Webb, Geoffrey I.; Margineantu, Dragos D.; Williams, Graham (ред.), Труды 21-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных, Сидней, Новый Южный Уэльс, Австралия, 10-13 августа 2015 г. , {ACM}, стр. 965–974, doi :10.1145/2783258.2783299, ISBN 9781450336642, S2CID 11041435.