Вводные.
Есть граф из N < 100 вершин. С вершиной v0 связаны ребром* все остальные вершины. Большинство вершин связано ребрами как минимум с двумя вершинами. В среднем каждая вершина связана ребрами с большинством других вершин. У каждой вершины есть флаг, принимающий значение 1 или 0.

Задача.
Разделить граф на минимальное число пересекающихся субграфов (подграфов?), в каждом из которых все вершины будут связаны ребрами со всеми вершинами. Все субграфы должны содержать вершину v0. В каждом субграфе не должно быть более K<20 вершин с флагом 1 и не более J<20 вершин с флагом 0.

* Здесь и далее под связью ребром подразумевается прямая связь двух вершин. Связь двух вершин через третью (транзитивная?) недостаточна.

Есть у кого-нибудь мысли, как это решить?

Заранее благодарен.

P. S. Это не ВУЗовская задача. Прикладная.

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

AbstractionТретье соображение - вернее, вопрос: нужно строго минимальное количество клик или достаточно близкого к минимальному?Достаточно близкого. Если еще будет прикинуто, какова вероятность найти более оптимальное решение и на сколько оно будет оптимальнее - будет вообще круто. :)

Еще забыл заметить: время работы алгоритма может быть вплоть до нескольких суток - это редкая операция. Главное, чтобы не месяцы-года-века.

AbstractionПервое соображение: если выделить любую клику из графа за вычетом v0, то добавление к ней v0 даст клику с на единицу большим числом вершин. То есть, можно выкинуть из рассмотрения v0 и уменьшить на единицу лимит по соответствующему флагу. Хорошее соображение. И спасибо за "клику" - не знал, как это называется, теперь хотя бы искать можно.

Abstraction,

а можете ссылку на жадный алгоритм кинуть?

Abstraction,

теперь информации достаточно.

Спасибо вам, бОльшую часть задачи вы за меня решили. Осталось только выделить время и реализовать.