Найти все полные подграфы внутри графика

Это известно как проблема клики ; это трудно и в целом является NP-полным, и да, есть много алгоритмов для этого.

Если граф обладает дополнительными свойствами (например, двудольный), то задача становится значительно проще и разрешима за полиномиальное время, но в остальном она очень сложна и полностью разрешима только для небольших графов.

Из Википедии

В информатике проблема клики относится к любой из проблем связано с нахождением конкретных полных подграфов ("клик") в графе, то есть наборов элементов, где каждая пара элементов связана.

Проблемы клики включают в себя:

• нахождение максимальной клики (клики с наибольшим числом вершин),
• нахождение клики максимального веса во взвешенном графе,
• перечисление всех максимальных клик (клики, которые не могут быть увеличены)
• решение задачи принятия решения о проверке того, содержит ли граф клика больше заданного размера.

Все эти задачи трудны: задача решения клики является NP-полной (одна из 21 NP-полных задач карпа), задача нахождения максимальной клики является трудноразрешимой с фиксированными параметрами и трудной для аппроксимации, а перечисление всех максимальных клик может потребовать экспоненциального времени, поскольку существуют графики с экспоненциально большим числом максимальных клик. Тем не менее, существуют алгоритмы для этих задач, которые работают в экспоненциальном времени или которые обрабатывают некоторые более специализированные входные графики в полиномиальном времени.

См. также

• алгоритм Брона-Кербоша