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

Question

У меня есть связанный, неориентированный граф G = (V, E), набор S = {S_1, S_2, ..., S_n}, где каждый S_i является подмножеством V, и ak> 1. Как я могу разбить V на k подмножеств так, чтобы было гарантировано, что:

1. для каждого i, каждый узел в S_i находится в том же подмножестве
2. каждое подмножество представляет связанный подграф G?

Answer 1

Задача леса Штейнера для заданного взвешенного графа G = (V, E) и пар вершин (s ₁ , t ₁ ),…, (s _m , t _m ), найдите самый легкий ребер-подграф H группы G такой, что для всех i вершины s _i и t _i принадлежат одному и тому же связанному компоненту H.

Вариант решения вашей проблемы, по сути, является версией решения леса Штейнера с единичными весами.К сожалению, этот особый случай все еще NP-сложен.

Сокращение от особого случая леса Штейнера до вашей проблемы с учетом невзвешенного экземпляра леса Штайнера и инструкций, чтобы определить, существует ли решение проблемы вMost C, создайте экземпляр вашей проблемы с тем же графом, k = | V |- c, и, для всех i, пусть S _i = {s _i , t _i }.Если существует лес стоимости Штейнера не более c, то связанные компоненты леса - это ваши подмножества, число которых не меньше | V |- с = к.И наоборот, если экземпляр вашей проблемы имеет решение, то мы можем найти связующее дерево в каждом из ваших подмножеств, и общая стоимость не превышает | V |- k = c.

Наилучший известный коэффициент аппроксимации равен 2, что мало поможет, если k мало.Вам, вероятно, придется использовать ветви и границы.

Answer 2

Несколько случайных наблюдений.Возможно, вы не сможете присоединиться к двум S_i, S_j, потому что они не образуют связанный подграф.Поскольку граф связан, вы всегда можете соединить его, если просто добавите достаточно S_k - в итоге вы получите полный граф, связанный по определению.Таким образом, требование к соединению ведет вас к слиянию.Требование к подмножествам, однако, заставляет вас держать вещи отдельно.По сути, у вас есть пространство поиска ^ k, которое вы можете радикально сократить, если будете следить за этими условиями.Конечно, если у вас нет «свободных» узлов без S, это полностью меняет игру.

Да, на самом деле это не ответ, а начало.Выложу как угодно;)