Как в графе найти самый «большой» полный подграф?

Question

[neuroepoc]

Другими словами, есть набор точек (от 250000 до 1000000), которые случайным образом связаны между собой. Среди этих точек нужно найти, такие N точек, каждая из которых связана с оставшимися N-1 точками, при этом, чтобы N было максимальным.

Answer 1

[Mercury13]

Это штатная задача, т.н. «задача о клике», NP-полная. Ничего лучше усовершенствованного перебора не существует.
https://ru.wikipedia.org/wiki/Алгоритм_Брона_—_Кербоша

Answer 2

[Rsa97]

Найти все подграфы, выбрать из них самый большой.

Comments

[neuroepoc]

ну, еще проверить, что подграф полный)

Answer 3

[Андрюха]

Это можно выполнить с помощью depth first search в линейное время. Выбрать вершину, выполнить от нее dfs помечая вершины как 0, затем выбрать другую (еще не помеченную) вершину, итд. Одновременно вести учет к-ва вершин в каждом подграфе.

Comments

[neuroepoc]

этот подход учитывает, что искомые подграфы должны быть полными? т.е. между любыми двумя вершинами должно быть ребро

[Андрюха]

нет :(

Answer 4

[tsarevfs]

Хм, придумалось судя по всему неправильное решение (жадное). Но интересно где проблема.
UPD: Понял где проблема.
Лемма 1 Два полных непересекающихся подграфа (без общих вершин) размера m и n соответственно между вершинами которых есть m*n ребер образуют полный подграф с m*n вершин.
Запихиваем все вершины в СНМ (Система непересекающихся множеств). Каждая вершина -- полный подграф размера 1. Дальше в процессе обхода "сливаем" полные подграфы.
Для этого храним map: (subgraph1, subgraph1) -> numOfConnections. Каждый раз когда встречаем ребро -- с помощью СНМ находим к каким подграфам относятся вершины и увеличиваем значение в map (или добавляем единицу, если ключа не было). Если значение оказалось больше чем произведение размеров подграфов -- сливаем их.

UPD: проблема жадного алгоритма в том, что мы получим не максимальный подграф. Иногда делать очередное слияние не выгодно. Например есть маленький подграф А, и 2 больших B и C. B можно слить с С или с А, но все 3 не образуют полный граф. Тогда если мы сольем B и A, то оптимальное решение уже не получится.

Comments

[neuroepoc]

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

изолированные

Точно не знаю, что имею в виду под изолированностью подграфа. Точнее не знаю как конкретно описать условие "изолированности".

полные подграфы? Как пример, анализ дружественных связей в вк. У пользователя есть друзья, среди этих друзей необходимо найти микросообщества этого пользователя(цель: нахождение критериев по которому эти микросообщества - полные графы построены).