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

При постоянная , можно определить в линейное время, учитывая входной граф , является ли его древесной шириной есть . Однако, когда оба и даны в качестве входных данных, проблема NP-трудна. ( Источник ). $k \in \mathbb{N}$ $G$ $\leq k$ $k$ $G$

Однако, когда входной граф является плоским , кажется, гораздо меньше известно о сложности. Проблема, по-видимому, была открыта в 2010 году. Заявление также появилось в этом обзоре в 2007 году и на странице Википедии о разложении ветвей . И наоборот, проблема была заявлена NP-hard (без подтверждения ссылки) в более ранней версии ранее упомянутого опроса, но я предполагаю, что это ошибка.

Открыто ли все еще, чтобы определить сложность задачи, учитывая, что и планарный граф определения имеют длину дерева ? Если это так, было ли это заявлено в недавней газете? Известны ли какие-либо частичные результаты? Если нет, то кто это решил? $k \in \mathbb{N}$ $G$ $G$ $\leq k$

reference-request graph-theory np-hardness open-problem treewidth a3nm
источник

Интересный вопрос, ура за перезагрузку опроса. Чтобы включить мои 2 цента, я полагаю, что исходный источник для линейного доказательства времени - Бодлаендер, но постоянный фактор, скрытый в асимптотической записи сложности, огромен. Возможно, интересным побочным эффектом / расширением вашего вопроса было бы то, учитывает ли плоское ограничение более практичный постоянный фактор в этом контексте?

Fasermaler

Я думаю, что это «известная и старая проблема», поэтому, если вы не найдете бумагу, это, вероятно, все еще открытая проблема. Другие «доказательства»: лекция из курса « Алгоритмы графов, приложения и реализации» (2015 г.), лекция из курса « Графики и алгоритмы: продвинутые темы» (2014 г.), энциклопедия алгоритмов (2008 г.).

Марцио Де Биаси

@Sariel: он может быть аппроксимирован с постоянным коэффициентом (3/2), используя тот факт, что он и ширина ветви находятся в пределах друг от друга, а плоскую ширину ветви можно вычислить за полиномиальное время Также это может быть аппроксимировано в журнале для всех графиков, используя Лейтон-Рао; см. kintali.wordpress.com/2010/01/28/approximating-treewidth

Дэвид Эппштейн

@Fasermaler первый шаг в алгоритме Бодлендера (и предыдущих алгоритмах, которые были FPT, но не линейным временем) состоит в том, чтобы вычислить приблизительное разложение дерева, на котором можно использовать динамическое программирование, чтобы найти оптимальное разложение. Чем теснее приближение, тем быстрее будет второй шаг. Таким образом, тот факт, что более узкие приближения к плоской ширине дерева можно найти с использованием ширины ветви, вероятно, приведет к лучшей зависимости от параметра (за счет возврата к линейному полиному). Но я не знаю документов, которые тщательно анализируют это.

Дэвид Эппштейн

Относительно проблемы аппроксимации древовидной ширины.

-аппроксимация для нахождения разреженного / сбалансированного узел-разделителей дадут

-аппроксимация для древесной ширина. Таким образом, в общих графах мы получим

α

$\alpha$

O (α)

$O(\alpha)$

через ARV / Feige-Lee-Hajiaghayi и

в плоских и правильных минорных семьях. Для общих графов можно получить

O (\sqrt{\log n})

$O(\sqrt{\log n})$

O (1)

$O(1)$

где

- это длина дерева.

O (\sqrt{\log k})

$O(\sqrt{\log k})$

k

$k$

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

Насколько я знаю, NP-полнота вычисления длины дерева плоского графа все еще открыта. Самая свежая справка, которую я знаю, это опрос Bodlaender, проведенный в 2012 году, под названием «Трактабельность с фиксированным параметром длины и ширины пути», который появился в festschrift для 65-летия Майка Феллоунса. Проблема указана в заключении опроса.

Барт Янсен
источник

Благодарность! (И спасибо также @MarzioDeBiasi за то, что они предложили другие ссылки.) Просто из любопытства кто-то случайно узнал, когда проблема была впервые поставлена?

a3nm

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

Ответы: