Многозадачная проблема

12

Я ищу имя или какие-либо ссылки на эту проблему.

Для заданного взвешенного графа найти разбиение вершин с точностью доустанавливает таким образом, чтобы максимизировать значение срезов: Обратите внимание, что некоторые из множеств могут быть пустыми. Таким образом, проблема, по сути, заключается в максимальном k-сокращении, за исключением того, что не является частью ввода: алгоритм может выбрать любоеG=(V,E,w)n=|V|S1,,Sn

c(S1,,Sn)=ij((u,v)E:uSi,vSjw(u,v))
Sikkэто нравится, чтобы максимизировать ценность обрезанных краев. Очевидно, что проблема тривиальна, если веса ребер неотрицательны: просто поместите каждую вершину отдельно в ее собственное множество, и вы обрежете все ребра. Но, чтобы сделать вещи интересными, допустимы отрицательные грани веса.

Это изученная проблема? Ссылки на алгоритмические результаты или результаты по твердости приветствуются!

Аарон Рот
источник
2
Чтобы узнать больше о проблеме, что вы знаете о простых особых случаях? Например, что, если веса просто +1 или 1 ? Что, если G полный граф, а веса ±1 ?
Юкка Суомела

Ответы:

11

Проблема представляет собой вариант Correlation Clustering (CC) Bansal, N., Blum, A. and Chawla, S. (2004). «Корреляционная кластеризация». Журнал машинного обучения (Специальный выпуск по теоретическим достижениям в кластеризации данных, стр. 86–113, doi: 10.1023 / B: MACH.0000033116.57574.95.

Исходная формулировка CC находится на полном графе и для каждого ребра у нас есть два веса: и . Для данного разбиения пусть будет равно если и находятся в одном и том же кластере а противном случае. Тогда значение разбиения в равно .G(v,w)a(v,w)b(v,w)PcP(v,w)a(v,w)vwPb(v,w)PVv,wc(v,w)

Ваша задача эквивалентна для всех v, w и допускает отрицательное (оригинальная статья допускала только + 1, -1 весов). Статья Эрика Д. Демейна, Дотана Эмануэля, Амоса Фиат, Николь Имморлика: корреляционная кластеризация в общих взвешенных графах. Теор. Вычи. Sci. 361 (2-3): 172-187 (2006) http://dx.doi.org/10.1016/j.tcs.2006.05.008 дает алгоритм -приложения для общего (т. Е. Не полного) графики. Я полагаю, что это может быть распространено и на вашу проблему, и я бы не исключил приближения с постоянным множителем.b ( v , w ) O ( log n )a(v,w)=0b(v,w)O(logn)

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

Джанлука Делла Ведова
источник
18

Я не знаю ни одной ссылки, но я могу показать, что она NP-полная, за счет сокращения от раскраски графика.

Учитывая граф G и число цветов k, которыми можно раскрасить G, создайте новый граф G ', который состоит из G вместе с k новыми вершинами, так, чтобы каждая новая вершина была связана с каждой вершиной в G. Присвойте вес + kn каждое ребро G, вес + kn для каждого ребра, соединяющего две k новых вершин, и вес -1 для каждого ребра, соединяющего k новых вершин G.

Тогда, если G может быть k-цветным, раскраска (вместе с разбиением, которое присваивает каждую из новых вершин одному из цветовых классов) достигает общего веса kn (m + k (k-1) / 2) - (k -1) п.

В другом направлении, если у вас есть разделение, которое достигает этого общего веса, тогда оно должно обрезать все ребра G и все ребра между парами новых вершин. Обрезка всех ребер G определяет раскраску G, а резка ребер между парами новых вершин подразумевает, что каждая вершина G может быть смежной не более чем с одной из k новых вершин. Поэтому, чтобы получить оптимальный - (k-1) n член в весе, каждая вершина G должна быть смежной ровно с одной из новых вершин, и, следовательно, в раскраске может быть только k классов цвета, определяемых раздел.

Таким образом, разбиения с заданной весовой границей 1-1 соответствуют k-раскраскам G, так что это определяет сокращение от раскраски до вашей проблемы разбиения.

Дэвид Эппштейн
источник
11

Позвольте мне дополнить прекрасное доказательство NP-полноты Дэвида, добавив ссылку на особый случай, заданный Юккой в ​​комментарии к вопросу. Если граф является полным графом, а вес ребер ограничен до ± 1, задача эквивалентна NP-полной задаче, известной как Cluster Editing.

Редактирование кластера - это следующая проблема, предложенная Шамиром, Шараном и Цуром [SST04]. Здесь кластерный граф - это граф, который представляет собой объединение клик, не пересекающихся с вершинами, а редактирование - это добавление или удаление одного ребра.


Экземпляр редактирования кластера : граф G = ( V , E ) и целое число k ∈ℕ.
Вопрос : возможно ли превратить G в кластерный граф не более чем за k правок?

Редактирование кластера завершено NP [SST04].

Чтобы увидеть, что редактирование кластера эквивалентно вышеупомянутому частному случаю текущей задачи, пусть G = ( V , E ) - граф. Пусть n = | V | и рассмотрим G как подграф полного графа K n . В К п , дают вес -1 до краев в G и веса +1 к краям не в G . Тогда G можно превратить в граф кластеров не более чем за k правок, если и только если существует разбиение ( S 1 ,…, S n ) такое, что c ( S 1 ,…,S n ) ≥ - | E | - k для этого взвешенного полного графа K n .(n2)

[SST04] Рон Шамир, Родед Шаран и Декел Цур. Проблемы модификации графа кластера. Дискретная прикладная математика , 144 (1–2): 173–182, ноябрь 2004 г. http://dx.doi.org/10.1016/j.dam.2004.01.007

Цуёси Ито
источник