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