高木と一定度のある部分グラフの検索

treewidth $ k $と任意の次数でグラフ$ G $を与えられました。 $ H
$が一定の次数を持ち、その幅ができるだけ大きいような部分グラフ$ H $/$ G
$(必ずしも誘導された部分グラフではない)を見つける。正式には私の問題は、次のようなものです: mathbb {N}
$での次数を選択したところ、$ f: mathbb {N} から mathbb {N} $までの “任意のグラフ$ G $と$
w $を結ぶと、最大次数$ leq d $と$ f(k)$を持つ$ G $の部分グラフ$ H
$を(うまくいけば効率的に)見つけることができます。

Obviously we should take $d geq 3$ as there are no high
treewidth graphs with maximal degree $<3$. For $d = 3$ I know
that you can take $f$ such that $f(k) = Omega(k^{1/100})$ or so,
by appealing to Chekuri and Chuzhoy’s grid minor
extraction result
(and using it to extract a high-treewidth
degree-3 graph, e.g., a wall, as a topological minor), with the
computation of the subgraph being feasible (in RP). However, this
is a very powerful result with an elaborate proof, so it feels
wrong to use it for what looks like a much simpler problem: I would
just like to find any constant-degree, high-treewidth
subgraph, not a specific one like in their result. Further, the
bound on $f$ is not as good as I would have hoped. Sure, it is
known that it can be made $Omega(k^{1/20})$ (up
to giving up efficiency of the computation), but I would hope for
something like $Omega(k)$. So, is it possible to show
that, given a graph $G$ of treewidth $k$, there is a subgraph of
$G$ with constant degree and linear treewidth in $k$?

私はまたtreewidthではなく、パス幅の全く同じ質問に興味があります。パス幅については、グリッドマイナー抽出のアナログはわかりません。そのため、この問題はさらに謎に思えます…

ベストアンサー

Julew ChuzhoyとTreewidth sparsifiersの論文を参照してください。 ここで、$ k $は$ G
$の幅であり、$ Omega(k/polylog(k))$の部分次数を得ることができることを示す。 https://arxiv.org/abs/1410.1016 証明は証明書よりも短く
グリッド未成年者のために、それはまだ簡単ではなく、いくつかの以前の ツール。

Suppose you settle for an easier target – degree 4 and treewidth
$Omega(k^{1/4})$ then you can get it much more easily via result
of Reed and Wood on grid-like minors. https://arxiv.org/abs/0809.0724

あなたが得ることができるもう1つの簡単な結果は、より複雑な証拠のいくつかの出発点である次のものです。 degre $ log
^ 2(k)$の部分グラフを得ることができます $ オメガ(k/ mathsf
{ポリロッグ}(k))$である。あなたはこれを達成するための議論のためにtreewidth
sparsifierペーパーを見ることができます。

コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です