Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе

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