Существуют ли интересные графовые классы, в которых сложно вычислить ширину дерева?

13

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

Хорошо известно, что вычисление ширины дерева является NP-сложным.

Существуют ли естественные классы графов, для которых сложно вычислить ширину дерева?

Так же:

Существуют ли интересные графовые классы, где вычисление ширины дерева легко? Если да, есть ли структурное свойство / тест, который можно использовать? То есть граф обладает свойством вычисляющим ширину дерева .X G PграммИкс Gп

PsySp
источник
Для классов графов, где treewidth ограничен или неограничен, вы можете увидеть graphclasses.org; выполните поиск по параметру treewidth, и вы получите список проходов графа, где treewidth ограничена (или не ограничена): graphclasses.org/classes/par_10.html
Antony
Вы также можете использовать их Java-приложение, чтобы увидеть классы, где разложение по ширине сложно (или просто)
Cyriac Antony

Ответы:

16

Treewidth является NP-трудным для вычисления на двудольных графах, действительно оригинальное доказательство NP-твердости для Treewidth Arnborg et al. показывает это. Кроме того, Bodlaender и Thilikos показали, что NP-сложнее вычислить ширину графиков максимальной степени . Наконец, для любого графа древесной ширины по крайней мере , 2 , расями края (то есть, заменяя края на степень 2 вершины , смежной с двумя краевыми конечными точками) не меняет treeewidth графика. Следовательно, NP-трудно вычислить ширину дерева двудольных 2-вырожденных графов произвольно большого обхвата.922

Эта проблема решается за полиномиальное время на хордовых графах, графах перестановок и, в более общем плане, на всех классах графов с полиномиальным числом потенциальных максимальных клик, см. Эту статью Бушитта и Тодинки. Отметим, что в той же статье показано, что множество потенциальных максимальных кликов графа G может быть вычислено из G за время O ( | Π ( G ) | 2n O ( 1 ) ) . Кроме того, алгоритм Бодлендера определяет, является ли GΠ(G)GGO(|Π(G)|2nO(1))Gимеет длину дерева не более за время 2 O ( k 3 ) n . Следовательно, древесная ширина полиномиальное время разрешимо для графов древесной шириной O ( ( лог - п ) 1 / 3 ) .k2O(k3)nO((logn)1/3)

Это нерешенная открытая проблема, является ли вычисление ширины дерева плоских графов разрешимым за полиномиальное время или NP завершена. Стоит отметить, что соответствующая ширина ветви параметра графа (которая всегда находится в пределах 1,5 от ширины дерева) вычисляется за полиномиальное время на плоских графах.

Даниелло
источник
Спасибо. Таким образом, единственный известный класс - это двудольные графы? Свойство потенциальных максимальных клик мне не кажется удивительным. Это свойство P-время проверяется?
PsySp
1
3n/3
8
Бодлендер и Тиликос [DAM 79 (1997) 45-61] показали, что вычисление ширины дерева является NP-трудным для графов максимальной степени 9.
Yota
2
В дополнение к твердости для двудольных графов, следует также отметить, что вычисление ширины дерева также сложно для двудольных графов, впервые наблюдавшихся, я думаю, Тоном Клоксом в своей диссертации.
vb le
2
Вы можете упомянуть, что (почти) ничего не известно о его сложности аппроксимации и параметризованных нижних границах. В принципе, может существовать алгоритм PTAS или алгоритм субэкспоненциального времени, хотя оба они маловероятны. Единственная аппроксимация твердости основана на расширении малого набора (SSE). DOI: 10.1613 / jair.4030.
Yixin Цао