Приближенные алгоритмы аппроксимации графами с ограниченным числом компонент

Рассматривается задача аппроксимации графа, где для заданного обыкновенного графа требуется найти ближайший к нему граф на том же множестве вершин, каждая компонента связности которого является полным графом. При этом расстояние между графами понимается как мощность симметрической разности множеств их ребер. Приведена краткая сводка известных результатов. Для двух вариантов задачи аппроксимации графа предложены алгоритмы их приближенного решения с константными оценками погрешности.