На SODA 2006 работа Мартина Грохе и D sharp Нила Маркса «Решение ограничений с помощью дробных краевых покрытий» ( цитирование ACM ) показала, что для класса гиперграфов H с ограниченной дробной шириной гипердерева CSP ( H ) \ in ПТИМ .
Определения и т. Д.
Большой обзор разложений стандартных деревьев и ширины деревьев см. Здесь (Заранее спасибо, JeffE!).
Пусть гиперграф.
Тогда для гиперграфа и отображения ,
{ }.
Кроме того, пусть weight ( ) = .
Тогда дробное разложение гипердерева является тройным , где:
- - это разложение дерева , и
- - это семейство отображений из в st для каждого ,
Тогда мы говорим ширину от является {вес }.
Наконец, дробная шириной гипердерева из , FHW ( ), является минимумом ширины по всему возможному дробному гипердереву разложения .
Вопрос
Как указано выше, если дробная ширина гипердерева основного графа CSP ограничена константой, то для решения CSP существует алгоритм с полиномиальным временем. Однако в конце связанной статьи осталась нерешенной проблема, существуют ли какие-нибудь разрешимые семейства экземпляров CSP за полиномиальное время, имеющие неограниченную ширину гипердерева. (Я должен также отметить, что этот вопрос полностью решен в случае ограниченной и неограниченной длины дерева ( ACM-цитирование ) в предположении, что .) Поскольку с момента публикации первой ссылки прошло некоторое время, плюс я относительно не осведомлен об общем состоянии этого подполя, мой вопрос:
Известно ли что-нибудь о (не) управляемости CSP над графами с неограниченной дробной шириной гипердерева?
источник