найти максимальный вес подграфа

Question

Мой график выглядит следующим образом:

Мне нужно найти подграф максимального веса.

Проблема заключается в следующем:

Существует n кластеров Vectex, и в каждом кластере Vextex есть несколько вершин.Для двух вершин в разных кластерах вершин есть взвешенное ребро, а в одном и том же кластере Vextex нет ребра среди вершин.Теперь я хочу найти подграф максимального веса, найдя только одну вершину в каждом кластере вершин.И общий вес вычисляется путем сложения всех весов ребер между выбранной вершиной.Я добавляю картинку, чтобы объяснить проблему.Теперь я знаю, как смоделировать эту проблему методом ILP.Однако я не знаю, как решить это с помощью алгоритма аппроксимации и как получить его коэффициент аппроксимации.

Не могли бы вы дать несколько решений и предложений?

Большое спасибо.Если какие-либо неясные моменты в этом описании, пожалуйста, не стесняйтесь спрашивать.

Answer 1

Я не думаю, что вы можете найти alpha -приложение для этой проблемы, для любого alpha. Это потому, что если такое приближение существует, то это также доказывает, что гипотеза уникальных игр (UGC) неверна. И опровержение (или доказательство) UGC - довольно большой подвиг: -)
(и я на самом деле среди верующих UGC, поэтому я бы сказал, что это невозможно: p)

Сокращение является довольно простым, поскольку любой экземпляр UGC может быть описан как ваша проблема с весами 0 или 1 по краям.

То, что я могу видеть как полиномиальное приближение, это 1/k -приброс (k количество кластеров), использующий алгоритм максимального совпадения веса (PM) (мы предполагаем, что число кластеров четное, если оно нечетное) просто добавьте «бесполезный» с 1 вершиной, везде 0 весов).

Во-первых, вам нужно построить новый график. Одна вершина на кластер. Вес ребра u, v имеет вес max w(e) для ребра e от кластера u к кластеру v. Запустите максимальный вес PM на этом графике.

Затем вы можете выбрать одну вершину на кластер, ту, которая соответствует ребру, выбранному в PM.
Общий вес раствора, извлеченного из ПМ, по меньшей мере такой же большой, как вес ПМ (поскольку он содержит ребра ПМ + другие ребра).

И тогда вы можете сделать вывод, что это приблизительно 1/k, потому что если существует решение проблемы, которое более чем в k раз превышает вес PM, тогда PM не был максимальным.

Объяснение довольно короткое ( lapidaire Я бы сказал), скажите мне, есть ли одна часть, с которой вы не поймаете / не согласитесь.

Редактировать: Эквивалентность с UGC: объяснение уникальной обложки.
Подумайте об экземпляре UGC. Затем каждый узел в экземпляре UGC будет представлен кластером с таким количеством узлов в кластере, сколько цветов в экземпляре UGC. Затем создайте ребро с весом 0, если они не соответствуют ребру в UGC, или если оно соответствует «плохому цветовому соответствию». Если они соответствуют хорошему цветовому сочетанию, тогда присвойте ему вес 1.
Затем, если вы найдете оптимальное решение для экземпляра вашей проблемы, это означает, что оно соответствует оптимальному решению для соответствующего экземпляра UGC.
Таким образом, если UGC справится, это означает, что NP-сложность приблизить вашу проблему.