Графовые разложения для объединения «локальных» функций маркировки вершин

15

xijEf(xi,xj)
maxxijEf(xi,xj)

Где max или сумма берется по всем меткам V , произведение берется по всем ребрам E для графа G={V,E} а f - произвольная функция. Эту величину легко найти для ограниченных графов ширины дерева и в общем случае NP-hard для плоских графов. Количество правильных раскрасок, максимальный независимый набор и количество эйлеровых подграфов являются особыми примерами вышеуказанной проблемы. Меня интересуют схемы аппроксимации полиномиального времени для задач такого типа, особенно для плоских графов. Какие графовые разложения были бы полезны?

Редактировать 11/1 : В качестве примера, я задаюсь вопросом о разложениях, которые могут быть аналогичны кластерным расширениям статистической физики (то есть расширению Майера). Когда f представляет слабые взаимодействия, такие расширения сходятся, что означает, что вы можете достичь заданной точности с помощью k условий расширения, независимо от размера графика. Не означает ли это наличие PTAS для количества?

Обновление 02/11/2011

Высокотемпературные расширения переписывают функцию распределения Z как сумму слагаемых, в которых члены более высокого порядка зависят от взаимодействий более высокого порядка. Когда «исчезают корреляции», члены старшего порядка затухают достаточно быстро, так что почти вся масса Z содержится в конечном числе членов младшего порядка.

Например, для модели Изинга рассмотрим следующее выражение ее функции разбиения.

Z=xXexpJijExixj=cAC(tanhJ)|A|

Здесь c простая константа, C - множество эйлеровых подграфов нашего графа, |A|это число ребер в подграфе A .

Мы переписали функцию разбиения как сумму по подграфам, где каждый член в сумме экспоненциально штрафуется размером подграфа. Теперь сгруппируйте члены с одним и тем же показателем и приблизьте Z , взяв первые k членов. Когда число эйлеровых подграфов размера p не растет слишком быстро, ошибка нашего приближения экспоненциально уменьшается с ростом k .

Приблизительный подсчет в общем сложный, но простой для случаев «затухания корреляции». Например, в случае модели Изинга наблюдается затухание корреляции, когда растет медленнее, чем где - число эйлеровых подграфов размера . Я полагаю, что в таком случае усечение высокотемпературного расширения дает PTAS для( tanh J ) k f ( k ) k Zf(k)(tanhJ)kf(k)kZ

Другим примером является подсчет взвешенных независимых наборов - он пригоден для любого графика, если вес достаточно мал, потому что вы можете заставить проблему демонстрировать затухание корреляции. Затем количество аппроксимируется путем подсчета независимых множеств в областях ограниченного размера. Я полагаю, что результат Dror Weitz 'STOC'06 подразумевает, что невзвешенный независимый подсчет множеств возможен для любого графа с максимальной степенью 4.

Я нашел два семейства «локальных» разложений - кластерные графы Бете и графы регионов Кикучи. По сути, декомпозиция Bethe говорит вам о необходимости умножать счет в регионах и делить на счет в перекрытиях регионов. Метод графика области Кикучи улучшает это, принимая во внимание, что перекрытия областей могут сами перекрываться, используя тип коррекции «включение-исключение».

Альтернативный подход состоит в том, чтобы разложить проблему на глобально поддающиеся трактовке части, например, в «Вариационный вывод над комбинаторными пространствами». Однако локальные декомпозиции позволяют контролировать качество аппроксимации, выбирая размер региона

Ярослав Булатов
источник

Ответы:

7

То, что я хочу сказать, слишком длинно для (но действительно должно быть) комментария.

Если я правильно читаю вопрос, вам нужна FPRAS (полностью полиномиальная схема рандомизированной аппроксимации) для любой из вышеуказанных величин, каждая из которых включает в себя различные # P-полные задачи в качестве особых случаев. В частности, вы хотите общий FPRAS в случае плоских графов, используя расширение кластера.

Я сомневаюсь, что это возможно из-за того факта, что NP-полнота проблемы существования (например, правильная раскраска) подразумевает, что соответствующая проблема подсчета (например, количество правильных раскрасок) завершена в #P относительно AP-сводимости (приближение- сохранение). См. Dyer, Goldberg, Greenhill and Jerrum, Algorithmica (2004) 38: 471-500.

Но, возможно, я неправильно понял вопрос.

(На самом деле, не могли бы вы объяснить непосвященному значение высокотемпературных расширений?)

RJK
источник
Я положил ответ на свой вопрос
Ярослав Булатов
@ Ярослав: Спасибо за подробные разъяснения! Кстати, под «регионом» вы подразумеваете «подмножество вершин»? (Это то, что я вижу, когда смотрю на Хеске, JAIR 26 (2006), 153-190.) Так что на самом деле кажется, что вы ищете конкретные FPRAS (то есть с определенным выбором f) для определенных классов (например, степень в большинство из 4) плоских графов, используя то, что вы называете «разложением графа» (если быть честным, это очень перегруженный термин). Это верно?
RJK
Да, регионы - это подмножества вершин, и мне интересен PTAS для «поддающихся обработке» классов графов. Кстати, вот отработанный пример декомпозиции кластера для подсчета независимых множеств, которые, я думаю, могут быть превращены в PTAS для случаев с затуханием корреляции - yaroslavvb.blogspot.com/2011/02/…
Ярослав Булатов,