Treewith является важным параметром графа, который указывает, насколько близко граф от дерева (хотя и не в строгом топологическом смысле).
Хорошо известно, что вычисление ширины дерева является NP-сложным.
Существуют ли естественные классы графов, для которых сложно вычислить ширину дерева?
Так же:
Существуют ли интересные графовые классы, где вычисление ширины дерева легко? Если да, есть ли структурное свойство / тест, который можно использовать? То есть граф обладает свойством вычисляющим ширину дерева .X ⇒ G ∈ P
Ответы:
Treewidth является NP-трудным для вычисления на двудольных графах, действительно оригинальное доказательство NP-твердости для Treewidth Arnborg et al. показывает это. Кроме того, Bodlaender и Thilikos показали, что NP-сложнее вычислить ширину графиков максимальной степени . Наконец, для любого графа древесной ширины по крайней мере , 2 , расями края (то есть, заменяя края на степень 2 вершины , смежной с двумя краевыми конечными точками) не меняет treeewidth графика. Следовательно, NP-трудно вычислить ширину дерева двудольных 2-вырожденных графов произвольно большого обхвата.9 2 2
Эта проблема решается за полиномиальное время на хордовых графах, графах перестановок и, в более общем плане, на всех классах графов с полиномиальным числом потенциальных максимальных клик, см. Эту статью Бушитта и Тодинки. Отметим, что в той же статье показано, что множество потенциальных максимальных кликов графа G может быть вычислено из G за время O ( | Π ( G ) | 2 ⋅ n O ( 1 ) ) . Кроме того, алгоритм Бодлендера определяет, является ли GΠ(G) G G O(|Π(G)|2⋅nO(1)) G имеет длину дерева не более за время 2 O ( k 3 ) n . Следовательно, древесная ширина полиномиальное время разрешимо для графов древесной шириной O ( ( лог - п ) 1 / 3 ) .k 2O(k3)n O((logn)1/3)
Это нерешенная открытая проблема, является ли вычисление ширины дерева плоских графов разрешимым за полиномиальное время или NP завершена. Стоит отметить, что соответствующая ширина ветви параметра графа (которая всегда находится в пределах 1,5 от ширины дерева) вычисляется за полиномиальное время на плоских графах.
источник