Какую ширину дерева может иметь дерево плюс половина ребер?

14

Пусть G дерево на 2n вершинах. Ширина дерева G, tw (G) = 1. Теперь предположим, что мы добавляем n ребер в G, чтобы получить граф H. Легкая верхняя граница для tw (H) равна n + 1. Является ли это по существу наилучшим возможным?

Как-то кажется, что tw (H) должно быть O (sqrt (n)), но это лишь смутное предположение. Знаем ли мы лучшие верхние оценки, чем O (n) для ширины дерева графа, полученного путем добавления n ребер к дереву на 2n вершинах?

upper-bounds treewidth gphilip
источник

Ответы:

18

Ваша модель на самом деле не менее общая, чем вопрос о произвольных 3-регулярных графах, а 3-регулярные графы расширителей имеют линейную ширину дерева. Так что я не знаю о постоянных факторах, но Θ (n) лучше, да.

Дэвид Эппштейн
источник
3
Спасибо, это отвечает на мой вопрос. Чтобы уточнить ответ Дэвида, пусть H - связный 3-регулярный граф на 2n вершинах. H тогда имеет 3n ребер. Пусть G - дерево на 2n вершинах, полученное путем удаления n + 1 ребер из H. Добавление n этих ребер обратно в G даст нам H '= (H минус одно ребро). Допустим, что H - граф экспандера с treewidth \ theta (n), мы видим, что H 'также имеет treewidth \ theta (n).
gphilip
8

Как указал Дэвид, вы в основном запрашиваете границы на ширине дерева связного графа со средней степенью 3. Для более частного случая 3-регулярных графов могут быть получены следующие нижняя и верхняя границы. Обозначая pw (G) ширину пути графа G, ясно, что

(1) tw (G) <= pw (G) для любого графа G (поскольку разложение по путям - это разложение по дереву)

В [1] доказано, что

(2) Для каждого \ epsilon> 0 существует такое целое число n_0, что для любого 3-регулярного графа G на n> = n_0 вершинах pw (G) <= n / 6 + \ epsilon * n.

Это дает верхнюю границу примерно n / 6 для ширины трех регулярных графов.

Для почти точной оценки снизу приведу цитату из [2]:

«Поскольку случайные кубические графы почти наверняка имеют ширину деления пополам по крайней мере 0,101 n (Kostochka, Melnikov, 1992), они почти наверняка не имеют разделителя с размером меньше n / 20» и, таким образом, почти наверняка нет разложения дерева шириной меньше n / 20 ,

Для «надежной» нижней границы ширины деления пополам [3] было показано бесконечное семейство 3-регулярных графов, так что каждый граф G = (V, E) в этом семействе имеет ширину деления пополам не менее 0,082 * | V |.

[1] Федор В. Фомин, Кьяртан Хойе: Путь кубических графов и точные алгоритмы. Inf. Процесс. Lett. 97 (5): 191-196 (2006)

[2] Ярослав Несетрил, Патрис Оссона де Мендес: Град и классы с ограниченным расширением II. Алгоритмические аспекты. Евро. J. Comb. 29 (3): 777-791 (2008)

[3] Сергей Л. Безруков, Роберт Эльзассер, Буркхард Моньен, Роберт Прейс, Жан-Пьер Тиллих: Новые спектральные нижние оценки ширины биссектрис графов. Теор. Вычи. Sci. 320 (2-3): 155-174 (2004)

Серж Гасперс
источник
Спасибо, Серж. На данном этапе мне, вероятно, более доступна привязка через траекторию, чем через графы расширителей; Хотя я еще не прочитал ни одного доказательства.
gphilip