Нахождение подграфов с высокой шириной дерева и постоянной степенью

9

Мне дали график Gс шириной дерева kи произвольной степени, и я хотел бы найти подграф группы (не обязательно индуцированный подграф) такой, что имеет постоянную степень, а его ширина дерева максимально высока. Формально моя проблема заключается в следующем: выбрав границу степени , какова «лучшая» функция такая, что в любом графе с Treewidth , я могу найти (мы надеемся, эффективно) подграф группы с максимальной степенью и treewidth .HGHdNf:NNGkHGdf(k)

Очевидно, что мы должны взять как нет графов с высокой шириной дерева с максимальной степенью . Для я знаю, что вы можете взять , что f (k) = \ Omega (k ^ {1/100}) или около того, обратившись к Чекури и Чужому, чтобы получить незначительный результат извлечения (и использовать его для извлечения высокого - график степени ширины-3, например, стена, как топологический минор, с возможным вычислением подграфа (в RP). Тем не менее, это очень мощный результат с тщательно продуманным доказательством, поэтому неправильно использовать его для решения более простой задачи: я просто хотел бы найти любуюd3<3d=3fе(К)знак равноΩ(К1/100)постоянный градус, большой подграф ширины, а не конкретный, как в их результате. Кроме того, оценка е не так хороша, как я бы надеялся. Конечно, известно, что это можно сделать Ω(К1/20) (вплоть до отказа от эффективности вычислений), но я бы надеялся на что-то вроде Ω(К) . Итак, можно ли показать, что при заданном графе г ширины дерева К существует подграф графа г с постоянной степенью и линейной шириной дерева в К ?

Меня также интересует точно такой же вопрос о траектории, а не о ширине дерева. Что касается пропускной способности, я не знаю никакого аналога для мелкого извлечения сетки, поэтому проблема кажется еще более загадочной ...

a3nm
источник

Ответы:

12

Смотрите статью Юлии Чужой и меня о спарсификаторах Treewidth. Мы покажем , что можно получить подграф степени не более 3 с древесной шириной , где является древесной шириной из . https://arxiv.org/abs/1410.1016 Доказательство короче, чем доказательство для несовершеннолетних по сетке, но все же не так просто и основано на нескольких предыдущих инструментах.Ω(К/поLYLог(К))Кг

Предположим, что вы согласились на более легкую цель - степень 4 и ширина дерева тогда вы можете получить ее гораздо проще благодаря результату Рида и Вуда для несовершеннолетних, подобных решетке. https://arxiv.org/abs/0809.0724Ω(К1/4)

Другой простой результат, который вы можете получить, это следующее, что является отправной точкой для некоторых из более сложных доказательств. Вы можете получить подграф degre и treewidth . Вы можете увидеть бумагу спарсификатора treewidth в качестве аргумента для достижения этой цели.журнал2(К)Ω(К/поLYLог(К))

Чандра Чекури
источник
1
Дополнительный комментарий. Можно ли получить подграф с treewidth и постоянной степенью - очень интересная открытая проблема. Мы задаем этот вопрос в статье о спарсификаторе длины, но не имеем правильного представления о правильном ответе. Один интересный граф, о котором спрашивал Барт Янсен, - это гиперкуб на узлах, который имеет ширину дерева и начальную степень . Ω(k)nΘ(n/logn)Θ(logn)
Чандра Чекури
Спасибо за указание на Рида и Вуда! Я заполню детали. В 1.2 из их статьи говорится, что граф G с древовидной шириной содержит сеткообразный минор порядка l. Теперь сеткообразный минор M - это подграф группы G, образованный путями с двудольным графом пересечений H, поэтому каждая вершина в M принадлежит не более чем двум путям в M (в противном случае это треугольник в H), следовательно, M имеет максимальную степень 4. Кроме того, у M есть treewidth : на самом деле любое дерево dec с M шириной k дает дерево dec с H шириной <= 2k (заменяя каждую вершину на пути ее членов, не более 2), и H имеет как несовершеннолетний. Ω(L4поLYLог(L))Ω(L)КL
17
Опять же, это очень полезно, спасибо. Интересно, что вопрос о линейной ширине дерева все еще остается открытым. (Тем не менее, если я правильно понимаю, гипотеза 1.2 в вашей статье про спарсификатор имеет дело с немного другой проблемой: для этого требуется, чтобы подграф был подразделением некоторого H полиномиального размера в k, тогда как я не спрашиваю об этом и просто хочу у подграфа должна быть постоянная степень.) И последнее. Знаете ли вы, известно ли что-нибудь об этой открытой проблеме, кроме как о траектории, а не о ширине пути? Еще раз спасибо!
17
@ a3nm почему ты удивляешься, что вопрос о линейной длине дерева открыт? В настоящее время у нас нет постоянного коэффициента приближения для ширины дерева. Что касается ширины пути, то сейчас единственный способ приблизить путь - это соотношение между treewdith и шириной пути, которое показывает . С помощью разбивки по ширине также можно получить разброс по ширине пути, но мы теряем логарифмический коэффициент. Было бы неплохо, если бы это был только коэффициент log pw (G), но я не уверен, как это сделать или известно ли это. Tвес(г)пвес(г)О(журналN)Tвес(г)
Чандра Чекури,
Спасибо за разъяснения о состоянии линейной ширины линии, а также за разъяснения по поводу разграничения пропускной способности. Последнее, что вы упомянули, - это те результаты, которые нам нужны; Жаль, что вопрос все еще открыт. В любом случае, еще раз большое спасибо за ваши объяснения!
a3nm