Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера

В задачах кластеризации на графах требуется разбить множество вершин заданного графа на попарно непересекающиеся подмножества (называемые кластерами) так, чтобы минимизировать число рёбер между кластерами и число отсутствующих рёбер внутри кластеров. Мы рассматриваем вариант задачи, в котором размеры кластеров ограничены сверху натуральным числом $s.$ Задача NP-трудна для любого фиксированного $s \geqslant 3.$ Для этого варианта задачи предложены полиномиальные приближённые алгоритмы с гарантированными оценками точности, равными $5/3$ в случае $s=3$ и $2$ в случае $s=4.$ Доказано также, что при $s=3$ задача APX-трудна. Ил. 5, библиогр. 20.