ПСУ с неограниченной дробной шириной гипердерева

10

На SODA 2006 работа Мартина Грохе и D sharp Нила Маркса «Решение ограничений с помощью дробных краевых покрытий» ( цитирование ACM ) показала, что для класса гиперграфов H с ограниченной дробной шириной гипердерева CSP ( H ) \ in ПТИМ .a´HHPTIME

Определения и т. Д.

Большой обзор разложений стандартных деревьев и ширины деревьев см. Здесь (Заранее спасибо, JeffE!).

Пусть H гиперграф.

Тогда для гиперграфа H и отображения γ:E(H)[0,) ,

B(γ)= { vV(H):eV(H),veγ(e)1 }.

Кроме того, пусть weight ( γ ) = eEγ(e) .

Тогда дробное разложение гипердерева H является тройным (T,(Bt)tV(T),(γt)tV(T)) , где:

  • (T,(Bt)tV(T)) - это разложение дерева H , и
  • (γt)tV(T) - это семейство отображений из E(H) в [0,) st для каждого tV(T),BtB(γt) ,

Тогда мы говорим ширину от является {вес }.(T,(Bt)tV(T),(γt)tV(T))max(γt),tV(T)

Наконец, дробная шириной гипердерева из , FHW ( ), является минимумом ширины по всему возможному дробному гипердереву разложения .HHH

Вопрос

Как указано выше, если дробная ширина гипердерева основного графа CSP ограничена константой, то для решения CSP существует алгоритм с полиномиальным временем. Однако в конце связанной статьи осталась нерешенной проблема, существуют ли какие-нибудь разрешимые семейства экземпляров CSP за полиномиальное время, имеющие неограниченную ширину гипердерева. (Я должен также отметить, что этот вопрос полностью решен в случае ограниченной и неограниченной длины дерева ( ACM-цитирование ) в предположении, что .) Поскольку с момента публикации первой ссылки прошло некоторое время, плюс я относительно не осведомлен об общем состоянии этого подполя, мой вопрос:FPTW[1]

Известно ли что-нибудь о (не) управляемости CSP над графами с неограниченной дробной шириной гипердерева?
Даниэль Апон
источник

Ответы:

8

Вы связались с двумя статьями, обе с предположениями. Я полагаю, вы имеете в виду гипотезу Гроэ в 2007 году.

На этот вопрос ответили в 2008 году:

Теорема 5. CSP (C , _) находится в NP, но ни в P, ни в NP-полной (если P = NP). Более того, множество C может быть определено за детерминированное полиномиальное время.00

  • Мануэль Бодирский и Мартин Гроэ, Недихотомия в сложности удовлетворения ограничений , ICALP 2008. doi: 10.1007 / 978-3-540-70583-3_16 ( PDF )

Идея состоит в том, чтобы продуть отверстия в размерах экземпляра CLIQUE, используя ту же технику отложенной диагонализации, введенную Ладнером для его теоремы. Отметим, что множество C содержит сколь угодно большие клики, а ширина дробного гипердерева клика равна . Таким образом, возможно иметь CSP вида CSP (A, _), которые имеют промежуточную сложность, где A имеет неограниченную дробную ширину гипердерева. Это отвечает гипотезе Гроэ в отрицательном.0nn/2

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

  • Ицзя Чен, Марк Терли и Марк Вейер, Понимание сложности изоморфизмов индуцированного подграфа , ICALP 2008. doi: 10.1007 / 978-3-540-70575-8_48 ( PDF )

Наконец, любой класс экземпляров CSP может быть преобразован в представление с дробной шириной гипердерева. Во многих случаях это преобразование ограничено полиномиальным размером и может быть выполнено за полиномиальное время. Это означает, что легко генерировать CSP с неограниченной дробной шириной гипердерева, даже по модулю гомоморфной эквивалентности. Эти CSP не будут иметь форму CSP (A, _), поскольку целевые структуры являются особыми, но они действительно дают четкую причину, по которой CSP, определенные ограничением только исходных структур, не так уж интересны: часто это просто слишком легко скрыть древовидную структуру экземпляра CSP, изменив представление так, чтобы исходная структура имела большую ширину. (Это обсуждается в главе 7 моей диссертации .)

Андраш Саламон
источник
спасибо за отличный ответ. Быстрый следующий вопрос: мое прочтение «Сложности гомоморфизма и проблем удовлетворения ограничений, видимых с другой стороны», заключается в том, что существует дихотомия P против NP-c для CSP в форме CSP (C, _) для не гиперграфы ограниченной арности, правильно ли я верю в это? Или, что более важно, в следствии 6.1 этой статьи нет скрытых предположений / предположений, о которых я не знаю, так? Или, кроме того, дихотомия там просто P против не-P? (Извините, если это очевидно.)
Даниэль Апон
2
@Daniel: Эта статья была не столько о дихотомиях, сколько о точной характеристике поддающихся обработке структурно-ограниченных случаев, а также случаев ограниченной ширины. Известно, что ограниченная ширина подразумевает податливость, но ключевая часть работы Гроэ в другом направлении. Неограниченная ширина подразумевает вложение миноров сетки произвольно большого размера, которые затем можно использовать для кодирования NP-сложной задачи, такой как CLIQUE. Гипотеза о дихотомии Федера / Варди для CSP предназначена для ограничений типа CSP (_, B), которые, как полагают, либо в P, либо в NP-полных.
Андрас Саламон
@Daniel: Кстати, этот материал, конечно, не был очевиден для меня, когда я впервые прочитал его. Быстрое резюме статьи Гроэ в моем предыдущем комментарии многим обязано Дейву Коэну.
Андрас Саламон