$2$-Приближённые алгоритмы для двух задач кластеризации на графах

Изучаются вариант задачи $2$-кластеризации на графе и соответствующая задача с частичным обучением. В этих задачах для данного графа требуется найти ближайший $2$-кластерный граф, т. е. граф на том же множестве вершин, имеющий ровно 2 непустые компоненты связности, каждая из которых является полным графом. Расстояние между графами равно числу их несовпадающих рёбер. Обе рассматриваемые задачи NP-трудны. В 2008 г. Коулман, Саундерсон и Вирт предложили полиномиальный $2$-приближённый алгоритм для аналогичной задачи, в которой число кластеров не превосходит $2$. К сожалению, метод доказательства гарантированной оценки точности алгоритма Коулмана, Саундерсона и Вирта неприменим для задачи $2$-кластеризации на графе, в которой число кластеров в точности равно $2$. Мы предлагаем полиномиальный $2$-приближённый алгоритм для задачи $2$-кластеризации на произвольном графе. В отличие от доказательства Коулмана, Саундерсона и Вирта, наше доказательство гарантированной оценки точности этого алгоритма не использует техники переключений. Кроме того, предложен аналогичный $2$-приближённый алгоритм для соответствующей задачи с частичным обучением. Библиогр. 9.