В этой статье в Википедии о проблеме Клика в теории графов вначале говорится, что проблема нахождения клики размера K в графе G является NP-полной:
Клики также изучались в информатике: обнаружение, есть ли клика заданного размера на графе (проблема клики), является NP-полной, но, несмотря на этот результат сложности, было изучено много алгоритмов для нахождения клик.
Но в этой другой статье в Википедии о проблеме Клика в CS говорится, что решение проблемы для фиксированного размера k - это проблема в P, ее можно перебить за полиномиальное время.
Алгоритм перебора, чтобы проверить, содержит ли граф G клику из k-вершин, и найти любую такую клику, которая в нем содержится, состоит в том, чтобы исследовать каждый подграф, по крайней мере, с k вершинами и проверить, образует ли он клику. Этот алгоритм требует времени O (n ^ kk ^ 2): необходимо проверить O (n ^ k) подграфов, каждый из которых имеет O (k ^ 2) ребер, наличие которых в G необходимо проверить. Таким образом, проблема может быть решена за полиномиальное время, когда k является фиксированной константой. Однако когда k является частью входных данных для задачи, время экспоненциально.
Есть что-то, чего я здесь не хватает? Может быть разница в формулировке проблемы? И что означает последнее предложение, что «когда k является частью входных данных для задачи, время является экспоненциальным»? Почему есть разница, когда k является частью входных данных для проблемы?
Моя идея состоит в том, чтобы найти клику размера k в графе G, мы сначала выбираем подмножество размера k узлов из G и проверяем, все ли они связаны с другими k узлами, что можно сделать постоянным время. И повторяйте это, пока у нас не будет клика размером k. Количество наборов из k узлов, которые мы можем выбрать из G, равно n! / k! * (nk) !.
Ответы:
Просто поясним, на что указал @Lamine: когда является частью ввода, k может быть больше nk k , и в этом случае число потенциальных наборов кликов равно ( nn2 по крайней мере(n(nn2) . Следовательно, ваш наивный алгоритм занял бы время2н(nn2)n2 которая явно экспоненциально по длине ввода| х| +| к| =n+logn. Параметризованная версияG(n,k),где мы ищемk-клики ввершинном графе, фиксирует сложность задачи в наиболее обобщенной форме, посколькуявляется частью входных данных. Следовательно, алгоритм поли-времени длятакже предполагает алгоритм поли-времени для любого конкретного.2n2 |x|+|k|=n+logn G(n,k) k n k G(n,k) k
источник