клик номер графа

Question

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

Я пытаюсь решить следующую проблему. http://uva.onlinejudge.org/external/1/193.html

Answer 1

Это NP-полная, и вы не можете сделать это намного лучше, чем найти максимальный клик и посчитать его вершины. От Википедия :

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

• решение проблемы решения вопроса о том, содержит ли граф клику, превышающую N

Все эти проблемы трудны: проблема решения клики NP -полная (одна из проблем Карпа 21 NP -полная),

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

Поскольку проблема решения NP-Complete, нахождение номера клика общего графа должно быть NP-Hard.

Answer 2

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

Если вы готовы реализовать код, то я рекомендую вам прочитать статьи, связанные с семейством алгоритмов MCQ, MCR и MCS, а также семейством BBMC, BBMCL и BBMCX.Интересной отправной точкой является сравнительный опрос Проссера [Проссер 12] .Он включает в себя объяснение реализации этих алгоритмов на Java.

Answer 3

Как уже говорили другие, это, вероятно, действительно сложно.

Но, как и многие теоретически сложные задачи, на практике это может быть довольно быстро с хорошим алгоритмом и подходящими данными.Если вы реализуете что-то вроде Bron-Kerbosch для поиска клик, сохраняя при этом наибольший из найденных вами размеров клик, то вы можете отказаться от бесплодных деревьев поиска.

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