Является ли эта оптимизация?

В полном комплекте n -partite неориентированный график, каждый набор партитов имеет n вершины. Моя проблема заключается в том, чтобы найти минимальный вес n -clique на графике. Я хотел бы знать, может ли проблема быть решена в poly-n времени.Является ли эта оптимизация?

Подробнее терминов:

Полный к-дольный граф: график, на котором вершины смежны тогда и только тогда, когда они принадлежат к различным наборам дольных (wikipedia). На графике есть k partite. В моей задаче k = n.

Clique: Клика в графе G является полным подграфом G; т. е. это подмножество S таких вершин, что каждая из двух вершин из S связана ребрами в G (wikipedia).

Минимальный вес Clique: У каждого края графика есть вес. Вес клики - это сумма весов всех ребер в клике. Цель состоит в том, чтобы найти клику с минимальным весом.

Обратите внимание, что размер требуемой клики составляет n, что является наибольшим размером клики на полном n-стороннем графике, и это всегда достижимо.

Я искал часы, и нет никаких исследований, направленных на решение конкретной проблемы. Какие-либо предложения?

источник

2013-07-07 linusz

Мы знаем, что такое клика. Вы говорите, что хотите оптимизировать [NP трудную проблему] (http://en.wikipedia.org/wiki/Clique_problem)^_ ^? –

@BenjaminGruenbaum Ну, я думаю, это отличается от проблемы клики в ссылке. Я надеюсь, что разница может привести к быстрому решению. – linusz

Есть n ** k опций для проверки на первом месте (клика находится только между краями на разных частях графика). Просто проверьте все параметры, проверяющие каждый узел в одной части (n таких) на узлах в других частях, все опции для выбора узла из части - n, вы делаете это для k частей, так что у вас есть n^k время выполнения (как вы хотели) ... это все еще очень медленно. –

Да, это NP-hard через это сокращение от CLIQUE.

Пусть (G, k) является экземпляром CLIQUE (определите, существует ли клика мощности не менее k). Подготовьте k-частичный граф H с k копиями каждой вершины в G и ребрами между двумя вершинами v и w тогда и только тогда, когда они находятся в разных частях и являются копиями смежных вершин в G. Существует k-клика в G тогда и только тогда, когда существует Х-клика в H. (С весами: сделайте существующие края весом 1 и введите недостающие с весом 0).

(Конечно, это в литературе, но это воскресенье и Мне не хочется смотреть.)

источник

2013-07-07 18:41:43

Я не уверен в сокращении. Моя проблема состоит в том, чтобы свести к минимуму вес клики, и размер клики, как известно, является максимальным, т. Е. N (он всегда доступен в полном n-частичном графе). Кроме того, в построенном графике H вершины, которые являются копиями одной и той же вершины, не связаны (они не смежны). Но это не так в моем случае: все две вершины, принадлежащие разным частям, связаны между собой. – linusz

@linusz. Сокращение для взвешенной версии интересующей вас проблемы имеет полный k-partite-граф с ребрами, имеющими вес 0, если они соединяют копии в разных частях G-смежных вершин и 1 в противном случае. –

Квадратичное назначение может быть легко сведено к этой задаче путем сопоставления местоположения с каждым двудольным множеством и средством с каждой вершиной каждого двудольного набора. Вес любого ребра между двумя вершинами, связанными с одним и тем же объектом, устанавливается в бесконечность. Так как квадратичное задание NP-твердое, то эта проблема также NP-hard.

источник

2013-07-07 20:02:33

ответ

Смежные вопросы