Означает ли ширина дерева

12

Пусть k фиксировано, и пусть G (связный) граф. Если я не ошибаюсь, из работы Бодлендера [1, теорема 3.11] следует, что если ширина дерева G примерно равна 2k3 , то G содержит звезду K1,k в качестве минора.

Можем ли мы сделать срок 2k3 меньше? То есть, говорит ли ширина дерева, по крайней мере, k уже подразумевает существование K1,k -минора? Есть ли где-нибудь доказательства?


[1] Bodlaender, HL (1993). На линейном времени второстепенные тесты с поиском по глубине. Журнал Алгоритмов, 14 (1), 1-23.

Юхо
источник
2
Слабосвязанный результат Демейна и Гаджиагайи : для фиксированного графа H любой H минорный граф с шириной дерева w имеет младший граф сетки Ω(w)×Ω(w) .
Мм
1
@mhum постоянная в Ω экспоненциально зависит от |H|, так что непосредственное применение этого даст худшую оценку, чем 2k3 .
Даниелло
@daniello Это действительно так. Константа не очень хорошая, и специализация на минорных графах также не велика. Я просто хотел указать на неопределенно связанный результат. H
Мм

Ответы:

15

Действительно, каждый граф без K 1 , k минора имеет ширину дерева не более k - 1 . Мы докажем это ниже, сначала несколько определений:GK1,kk1

Пусть является древесная ширина из G и & omega ( G ) быть максимальный размер клики в G . Граф H является триангуляцией G, если G является подграфом H, а H хордовый (т. Е. Не имеет индуцированных циклов по крайней мере в 4 вершинах). Триангуляцией Н из G является минимальной триангуляции , если нет надлежащего подграф H не является также триангуляция G . Подмножество X вершин группы Gtw(G)Gω(G)GHGGHH4HGHGXGHGXHH G

tw(G)=minHω(H)1
HG

Из приведенной выше формулы следует, что для доказательства того, что достаточно доказать, что все потенциальные максимальные клики в имеют размер не более . Теперь докажем это. Пусть - потенциальная максимальная клика группы , и пусть .G k X G | X | k + 1tw(G)k1GkXG|X|k+1

Мы будем использовать следующую характеристику потенциальных максимальных клик: множество вершин является потенциальной максимальной кликой в если и только если для каждой пары , несмежных (различных) вершин в существует путь из в в со всеми его внутренними вершинами наружу из . Эту характеристику можно найти в статье Treewidth и Minimum Fill-in: группировка минимальных разделителей по Bouchitte и Todinca.G u v X P u , v u v G XXGuvXPu,vuvGX

С этой характеристикой легко вывести минор из . Пусть . Для каждой вершины , либо является ребром или существует путь из в со всеми внутренними вершинами вне . Для всех , несмежных с все внутренние вершины в . В итоге мы получаем минор в котором смежна со всем , и X u X v X { u } u v G P u , v u v X v X u P u , v u G u X | X | k + 1 u kK1,kXuXvX{u}uvGPu,vuvXvXuPu,vuGuX|X|k+1 . Таким образом, степень в этом миноре составляет не менее , что завершает доказательство.uk

Даниелло
источник
Спасибо, Даниэль! Вы случайно не знаете, был ли опубликован тот же самый аргумент (или результат, действительно) где-то?
Юхо
У меня нет ссылки, но я, кажется, помню, что где-то записан похожий (возможно, менее жесткий) аргумент для свободных графов . К сожалению, у меня нет более конкретного указателя. K2,r
Даниелло