Поиск набора узлов, которые являются соседями друг друга с одним переходом в матрице смежности

Для заданного неориентированного графа с N узлами и его матрицей смежности предположим, что существует по крайней мере один набор из n узлов, в котором каждый узел-член является соседом с одним переходом для других в наборе. (n ‹‹ N)

Каков в этой ситуации алгоритм поиска такого набора узлов?

Например, это пример матрицы смежности (ссылка: GitHub Gist) с 42 узлами. И известно, что существует множество, в котором 3 узлов являются соседями друг друга по одному переходу. Тогда какой состав набора?

Моя конечная цель — выполнить эту процедуру примерно с 450 узлами, чтобы найти набор, содержащий 9 узлов-соседей с одним переходом. Поэтому я ищу масштабируемое и эффективное решение.


algorithm adjacency-matrix
person Jeon    schedule 17.11.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

Обратите внимание на разницу между кликами maximum (максимально возможная) и maximal (нельзя увеличить).

person j_random_hacker    schedule 17.11.2014