Является ли проблема k-клики NP-полной?

23

В этой статье в Википедии о проблеме Клика в теории графов вначале говорится, что проблема нахождения клики размера 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) !.

Рафаэль
источник
13
NP-полнота проблемы зависит от того, что вы считаете входным. Потому что проблема в если есть полиномиальный алгоритм для ее решения. Если K является константой (не входом), алгоритм является полиномиальным по n . Если k является частью ввода, то алгоритм экспоненциально по k . PKnkk

Ответы:

17

Просто поясним, на что указал @Lamine: когда является частью ввода, k может быть больше nkk , и в этом случае число потенциальных наборов кликов равно ( nn2по крайней мере(n(nn2) . Следовательно, ваш наивный алгоритм занял бы время2н(nn2)n2 которая явно экспоненциально по длине ввода| х| +| к| =n+logn. Параметризованная версияG(n,k),где мы ищемk-клики ввершинном графе, фиксирует сложность задачи в наиболее обобщенной форме, посколькуявляется частью входных данных. Следовательно, алгоритм поли-времени длятакже предполагает алгоритм поли-времени для любого конкретного.2n2|x|+|k|=n+lognG(n,k)knkG(n,k)k

Саджин Корот
источник