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

В теории графов и информатике плотный подграф — это подграф со множеством ребер на вершину. Это формализуется следующим образом: пусть $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 / м))$ время. Простую ЛП для поиска оптимального решения предложил Чарикар в 2000 году. ^[2]

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

Самый плотный $k-$ подграф

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

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

Самый плотный не более $k$ подграф

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

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

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

$K -клики$ Плотный подграф

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

Локально top $-k$ плотный подграф

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

Ссылки

^ Галло, Джорджио; Григориадис, Майкл Д.; Тарьян, Роберт Э. (1989), «Быстрый параметрический алгоритм максимального потока и его приложения», SIAM Journal on Computing , 18 (1): 30–55, doi : 10.1137/0218003 , MR 0978165
^ Чарикар, Моисей (2000), «Алгоритмы жадной аппроксимации для поиска плотных компонентов в графе», Янсен, Клаус; Хуллер, Самир (ред.), Алгоритмы аппроксимации для комбинаторной оптимизации, Третий международный семинар, APPROX 2000, Саарбрюккен, Германия, 5-8 сентября 2000 г., Труды , Конспекты лекций по информатике, том. 1913, Спрингер, стр. 84–95, номер документа : 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 , МР 2743268 , S2CID 1391318 .
^ Мануранси, Пасин (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 для мини-бисекции графа, плотного $k$ -подграфа и двудольной клики», SIAM Journal on Computing , 36 (4): 1025–1071, CiteSeerX 10.1.1.114.3324 , doi : 10.1137/S0097539705447037 , MR 2272270 , S2CID 16514252 .
^ Корней, Д.Г. ; Перл, Ю. (1984), «Кластеризация и доминирование в совершенных графах», Discrete Applied Mathematics , 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. дои : 10.1007/978-3-540-95995-3_3 . ISBN 978-3-540-95995-3 .
^ Jump up to: ^а ^б Хуллер, Самир ; Саха, Барна (2009), «О поиске плотных подграфов» (PDF) , Автоматы, языки и программирование: 36-й международный коллоквиум, ICALP 2009, Родос, Греция, 5–12 июля 2009 г., Материалы, Часть I , Конспекты лекций по компьютеру Наука, том. 5555, Берлин: Springer-Verlag, стр. 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
^ Мануранси, Пасин (2018), «Неаппроксимируемость задач максимальной биклики, минимальный $k$ -разрез и плотный по меньшей мере $k$ -подграф из гипотезы расширения малых множеств», Алгоритмы , 11 (1): 10, arXiv : 1705.03581 , doi : 10.3390/а11010010 , МР 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 .
Цинь, Лу; Ли, Ронг{-}Хуа; Чанг, Лицзюнь; Чжан, Ченци (2015), «Обнаружение локально плотного подграфа», в Цао, Лунбин; Чжан, Чэнци; Иоахимс, Торстен; Уэбб, Джеффри И.; Маргинеанту, Драгош Д.; Уильямс, Грэм (ред.), Труды 21-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных, Сидней, Новый Южный Уэльс, Австралия, 10–13 августа 2015 г. , {ACM}, стр. 965–974, doi : 10.1145/ 2783258.2783299 , ISBN 9781450336642 , S2CID 11041435 .

[1] Галло, Джорджио; Григориадис, Майкл Д.; Тарьян, Роберт Э. (1989), «Быстрый параметрический алгоритм максимального потока и его приложения», SIAM Journal on Computing , 18 (1): 30–55, doi : 10.1137/0218003 , MR 0978165

[2] Чарикар, Моисей (2000), «Алгоритмы жадной аппроксимации для поиска плотных компонентов в графе», Янсен, Клаус; Хуллер, Самир (ред.), Алгоритмы аппроксимации для комбинаторной оптимизации, Третий международный семинар, APPROX 2000, Саарбрюккен, Германия, 5-8 сентября 2000 г., Труды , Конспекты лекций по информатике, том. 1913, Спрингер, стр. 84–95, номер документа : 10.1007/3-540-44436-X_10 , ISBN. 978-3-540-67996-7

[3] Бхаскара, Адитья; Чарикар, Моисей ; Хламтач, Иден; Файги, Уриэль ; Виджаярагаван, Аравиндан (2010), «Обнаружение высокой плотности бревен - $O (n 1/4)$ аппроксимация самого плотного $k$ -подграфа », STOC'10 - Труды Международного симпозиума ACM по теории вычислений 2010 г. , ACM, Нью-Йорк, стр. 201–210, doi : 10.1145/1806689.1806719 , ISBN 9781450300506 , МР 2743268 , S2CID 1391318 .

[4] Мануранси, Пасин (2017), «Почти полиномиальное отношение ETH-твердости аппроксимирующего плотнейшего k-подграфа», STOC'17 — Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений , ACM, стр. 954–961, arXiv : 1611.05991 , номер doi : 10.1145/3055399.3055412 , ISBN 9781450345286 , S2CID 1892186 .

[5] Хот, Субхаш (2006), «Исключение PTAS для мини-бисекции графа, плотного $k$ -подграфа и двудольной клики», SIAM Journal on Computing , 36 (4): 1025–1071, CiteSeerX 10.1.1.114.3324 , doi : 10.1137/S0097539705447037 , MR 2272270 , S2CID 16514252 .

[6] Корней, Д.Г. ; Перл, Ю. (1984), «Кластеризация и доминирование в совершенных графах», Discrete Applied Mathematics , 9 (1): 27–39, doi : 10.1016/0166-218X(84)90088-X , MR 0754426 .

[7] Кейл, Дж. Марк; Брехт, Тимоти Б. (1991), «Сложность кластеризации в плоских графах» (PDF) , Журнал комбинаторной математики и комбинаторных вычислений , 9 : 155–159, MR 1111849 .

[8] Андерсен, Рид; Челлапилла, Кумар (2009). Авраченков Константин; Донато, Дебора; Литвак, Нелли (ред.). «Нахождение плотных подграфов с границами размера» . Алгоритмы и модели веб-графа . Конспекты лекций по информатике. Берлин, Гейдельберг: Springer: 25–37. дои : 10.1007/978-3-540-95995-3_3 . ISBN 978-3-540-95995-3 .

[:0-9] Jump up to: ^а ^б Хуллер, Самир ; Саха, Барна (2009), «О поиске плотных подграфов» (PDF) , Автоматы, языки и программирование: 36-й международный коллоквиум, ICALP 2009, Родос, Греция, 5–12 июля 2009 г., Материалы, Часть I , Конспекты лекций по компьютеру Наука, том. 5555, Берлин: Springer-Verlag, стр. 597–608, CiteSeerX 10.1.1.722.843 , doi : 10.1007/978-3-642-02927-1_50 , ISBN 978-3-642-02926-4 , МР 2544878

[10] Андерсен, Рид (2007), Поиск больших и малых плотных подграфов , arXiv : cs/0702032 , Bibcode : 2007cs........2032A

[11] Мануранси, Пасин (2018), «Неаппроксимируемость задач максимальной биклики, минимальный $k$ -разрез и плотный по меньшей мере $k$ -подграф из гипотезы расширения малых множеств», Алгоритмы , 11 (1): 10, arXiv : 1705.03581 , doi : 10.3390/а11010010 , МР 3758880

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

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

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

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

K -клики Плотный подграф

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