Комбинаторная оптимизация

Предположим, у нас есть связный и неориентированный граф: G = (V, E).

Определение связного множества: группа точек, принадлежащих V группы G, образует допустимое связное множество, если и только если каждая точка в этой группе находится в пределах T-1 ребер от любой другой точки в той же группе, T - количество очков в группе.

Обратите внимание, что связное множество - это просто связный подграф G без ребер, но с точками.

И у нас есть произвольная функция F, определенная на связном множестве, т.е. заданная произвольная связная совокупность CS F (CS) даст нам реальное значение.

Два связных множества называются непересекающимися, если их объединение не является связным множеством.

Для наглядного объяснения см. График ниже: На графике наборы красных, черных и зеленых точек являются действительными связными наборами, зеленый набор не пересекается с красным набором, но черный набор не является непересекающимся с красным.

Теперь вопрос: Мы хотим найти группу непересекающихся связных множеств из G так, чтобы: (1) каждое связное множество имеет не менее K точек. (K - глобальный параметр). (2) сумма их значений функций, то есть max (Σ F (CS)), максимизирована.

Есть ли какой-либо эффективный алгоритм для решения такой проблемы, кроме исчерпывающего поиска? Thx!

Например, график может быть плоским графом в двумерной евклидовой плоскости, а значение функции F связного множества CS может быть определено как площадь минимального ограничивающего прямоугольника всех точек в CS ( минимальный ограничивающий прямоугольник - это самый маленький прямоугольник, охватывающий все точки в CS).