Прибавление разложения дерева минимальной ширины за полиномиальное время

Как известно, древовидная декомпозиция графа состоит из дерева со связанным мешком для каждой вершины , которое удовлетворяет следующим условиям: $G$ $T$ $T_v \subseteq V(G)$ $v \in V(T)$

Каждая вершина происходит в некотором мешке . $G$ $T$
Для каждого края есть сумка, содержащая обе конечные точки края. $G$
Для каждой вершины , мешки , содержащие вызывают связное поддерево . $v \in V(G)$ $v$ $T$

Мы также можем потребовать следующее условие, называемое худобой , от нашего разложения:

Для каждой пары сумок , of , если и с , то либо a) существует непересекающихся вершин путей в , либо b) дерево содержит ребро на пути от узла к узлу такое что $T_a$ $T_b$ $T$ $A \subseteq T_a$ $B \subseteq T_b$ $|A| = |B| = k$ $k$ $A-B$ $G$ $T$ $pq$ $a$ $b$ и множество пересекает все пути в . $|V(T_p) \cap V(T_q)| \leq k$ $V(T_p) \cap V(T_q)$ $A-B$ $G$

Робин Томас показал, что всегда есть разложение дерева минимальной ширины, которое также является скудным, и более простые доказательства этого факта были предоставлены несколькими авторами, например Патриком Белленбаумом и Рейнхардом Дистелем .

Что меня интересует, так это следующее: учитывая граф и разложение дерева минимальной ширины , можем ли мы найти разложение худого дерева минимальной ширины за полиномиальное время? $G$ $G$ $G$

Два упомянутых доказательства не дают такой эффективной конструктивности. В работе Bellenbaum и Diestel упоминается, что «Другое (более конструктивное) краткое доказательство теоремы Томаса было дано в P. Bellenbaum, Schlanke Baumzerlegungen von Graphen, Diplomarbeit, Universitat Hamburg 2000». Увы, я не смог найти рукопись в Интернете, и мой немецкий не настолько хорош.

ds.algorithms graph-theory graph-algorithms treewidth Барт Янсен
источник

Хороший вопрос Найти декомпозицию дерева минимальной ширины - это NP-Hard, поэтому ваша проблема несколько некорректна (кажется). Я предполагаю, что можно задать это для ограниченного случая длины дерева или в смысле приближения.

Чандра Чекури

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

Суреш Венкат

@SureshVenkat: я понимаю, что ему дают разложение дерева минимальной ширины, но как вы можете даже убедиться, что оно верно? Кроме того, декомпозиция на основе бережливого дерева локально адаптируется к ширине дерева различных частей графа, поэтому оптимальная декомпозиция дерева глобального графа не избавляет от проблемы нахождения ширины дерева локальных кусков, что сложно.

Чандра Чекури

Гладкие разбиения дерева (где все мешки имеют одинаковый размер, а два смежных мешка отличаются ровно на одну вершину) гораздо проще обрабатывать, чем обычные разбиения дерева, и легко видеть, что всегда есть разложение дерева минимальной ширины, которое является гладким , Так что, возможно, вы можете получить эффективную конструкцию, ограничив одну из известных конструкций этими. Всегда ли существует разложение дерева минимальной ширины, которое является гладким и скудным?

Диего де Эстрада

@ChandraChekuri Я предполагаю, что проблема проверки исчезнет, если вы сформулируете ее как проблему обещания, но я вижу вашу точку зрения о том, что разложение по одному дереву не обязательно даст вам достаточно информации для адаптации. Но следующий вопрос может быть правдоподобным: есть ли способ «локально» изменить разложение данного дерева, чтобы оно «наклонилось» без увеличения ширины дерева?

Суреш Венкат

Вот формальная причина, по которой проблема не решается за многократное время, если P = NP. Мы знаем, что нахождение ширины дерева данного графа является NP-Hard. Для данного графа мы можем добавить непересекающуюся клику размера чтобы создать новый граф . A Минимальная шириной дерева-разложение может быть получено следующим образом : он имеет два узла с одного мешком , содержащего все узлы клики , а другие , содержащие все узлы . Теперь делая это дерево-разложение мяса потребовало бы найти разложение обедненных дерева исходного графа , который бы, в качестве побочного продукта, получая древесную ширину от . $G$ $V(G)+1$ $G'$ $G'$ $G$ $G$ $G$

Чандра Чекури
источник

Хорошая точка зрения. Знаете ли вы, что-нибудь известно о параметризованных и / или умеренно экспоненциальных алгоритмах времени для нахождения разложения по бережному дереву?

Барт Янсен

Прибавление разложения дерева минимальной ширины за полиномиальное время

Ответы: