Найти наибольшее число попарно связанных вершин графа

[cupuyc]

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

Каждое ребро графа связывает 2 различные вершины. Между каждой парой вершин может быть не более одного ребра. Нужно найти множество максимальной мощности, такое, что любая пара вершин из этого множества связана графом. Например, есть граф из пяти вершин (обозначенных цифрами):
{1, 2, 3, 4, 5}
и 8 рёбер:
1-2
1-3
1-4
1-5
2-3
2-4
3-4
3-4
В результате мы должны получить множество {1, 2, 3, 4}. Вершина 5 в это множество не войдёт, т.к. она не связана с вершинами {2, 3, 4}.

[provincialka]

Такие подмножества называются кликами. Ваша задача - о поиске максимальной клики. Это, кажется, NP-сложная задача.

[Kenelm]

Да, это задача о поиске максимальной клики. Решается при помощи метода ветвей и границ (алгоритм Брона-Кербоша). Сложность в худшем случае $O(3^{n/3})$.