Есть ли какая-нибудь проблема в которая разрешима в ограниченных графах ширины дерева?

16

Я ищу проблему, которая принадлежит в общих графах, но находится в в графах с ограниченной шириной дерева. На самом деле я думаю, что эти проблемы сложнее, чем использование нормального динамического программирования в ограниченных графах. -ширины графиков для их решения. $\mathsf{\Sigma^P_2}$ $\mathsf{P}$

cc.complexity-theory graph-theory treewidth Saeed
источник

Если проблема в P для графов с ограниченной шириной, почему вы говорите, что это «сложнее, чем использование нормального DP» в таких графах?

Суреш Венкат

11

Перечислите хроматическое число (верно ли, что граф имеет раскраску вершин, когда каждая вершина получает список из k допустимых цветов?) - это -полная задача, но решаемая за линейное время на графах с ограниченной шириной: $\Pi_2^P$

http://www.ii.uib.no/~daniello/papers/EqColoring.pdf

Даниэль Маркс
источник

3

Если вам понравился этот результат, то, возможно, вас также интересует следующая статья: arxiv.org/abs/1110.4077 . Он появился на arXiv на этой неделе, и авторы показывают, что хроматическое число по краям списка и общее хроматическое число по списку также могут быть решены в линейном времени для графиков ограниченной ширины дерева.

Барт Янсен

13

Я думаю, что 2-кликовая окраска [GT19 в Schaefer и Umans ] является примером. Вопрос заключается в том, может ли данный граф (неправильно) быть 2-цветным таким образом, чтобы ни одна из его максимальных клик не была монохроматической. Для графиков ограниченной ширины дерева каждая максимальная клика должна происходить в пределах одного пакета разложения дерева, поэтому он должен работать с использованием стандартного подхода динамического программирования, в котором состояния динамической программы представляют собой 2 цвета пакета, которые правильно окрашивают все максимальный клик внутри сумки и соответствует хорошему состоянию детских сумок.

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

1

Он находится в P для TW (<= k) также по этой причине: раскраска k-клики выражается MS: "Существует X_1, ... X_k (Partition (X_1, ..., X_k) и ForAll X (CliqueMax") (X) => нет (существует X_i (Forall x в X (x в X_i)))))

M. kanté

2

Я думаю, что вы имеете в виду

\exists X_{1}, \dots, X_{k} : (IsPartition (X_{1}, \dots, X_{k}) \land \forall X : (MaxClique (X) ⟹ \neg (\exists X_{i} : \forall x \in X : x \in X_{i})))

$\exists X_1, \dots, X_k: (\text{IsPartition}(X_1, \dots, X_k) \land \forall X: (\text{MaxClique}(X) \implies \lnot(\exists X_i: \forall x\in X: x\in X_i)))$

Джефф

Есть ли какая-нибудь проблема в которая разрешима в ограниченных графах ширины дерева?

Ответы: