Suche nach Teilgraphen mit hoher Baumbreite und konstantem Grad

9

Ich erhalte einen Graphen mit einer Baumbreite k und einem beliebigen Grad und möchte einen Teilgraphen H von G (nicht unbedingt einen induzierten Teilgraphen) finden, so dass H einen konstanten Grad hat und seine Baumbreite so hoch wie möglich ist. Formal ist mein Problem das Folgende: Nachdem ich eine Gradgrenze d N gewählt habe , was ist die "beste" Funktion f : NN, so dass ich in jedem Graphen G mit der Baumbreite k (hoffentlich effizient) einen Teilgraphen H von finden kann G mit maximalem Grad dG kHGHdNf:NNGkHGdund Baumbreite .f(k)

Offensichtlich sollten wir da es keine Graphen mit hoher Baumbreite mit maximalem Grad < 3 gibt . Für d = 3 weiß ich , dass Sie ergreifen können , f , so daß f ( k ) = Ω ( k 1 / 100 ) oder so, um zu Chekuri und tschuschoj des ansprechend kleinere Absaugergebnis Gitterd3<3d=3ff(k)=Ω(k1/100)(und Verwenden, um einen Graphen mit hoher Baumbreite Grad 3, z. B. eine Wand, als topologisches Nebenfach zu extrahieren), wobei die Berechnung des Teilgraphen möglich ist (in RP). Dies ist jedoch ein sehr starkes Ergebnis mit einem aufwendigen Beweis, so fühlt es sich falsch es zu benutzen , was aussieht wie ein viel einfacheres Problem: Ich möchte nur finden jeden konstanten Grad, High-Baumweite Subgraphen, kein spezifisches wie in ihrem Ergebnis. Außerdem ist die Bindung an nicht so gut, wie ich es mir erhofft hätte. Sicher, es ist bekannt , dass es gemacht werden kann Ω ( k 1 / 20 ) (bis zu Effizienz der Berechnung Aufgeben), aber ich würde für so etwas wie Hoffnung Ω ( k )fΩ(k1/20)Ω(k). So ist es möglich , dass zu zeigen, da ein Graph von Baumweite k gibt es ein Teilgraph von G mit einem konstanten Grad und lineare Baumweite in k ?GkGk

Ich interessiere mich auch für genau die gleiche Frage für die Pfadbreite und nicht für die Baumbreite. Für die Pfadbreite kenne ich kein Analogon zur Extraktion kleinerer Netze, daher scheint das Problem noch mysteriöser zu sein ...

a3nm
quelle

Antworten:

12

Siehe das Papier von Julia Chuzhoy und mir über Treewidth-Sparsifiers. Wir zeigen, dass man mit der Baumbreite Gradgraphen von höchstens 3 erhalten kann, wobei k die Baumbreite von G ist . https://arxiv.org/abs/1410.1016 Der Beweis ist kürzer als der für Grid Minors, aber es ist immer noch nicht so einfach und baut auf mehreren früheren Tools auf.Ω(k/polylog(k))kG

Angenommen , Sie regeln für ein leichteres Ziel - Grad 4 und Baumweite , dann können Sie es viel leichter über Ergebnis von Reed und Holz auf rasterartige Minderjährigen. https://arxiv.org/abs/0809.0724Ω(k1/4)

Ein weiteres einfaches Ergebnis, das Sie erzielen können, ist das Folgende, das als Ausgangspunkt für einige der komplexeren Beweise dient. Sie können einen Teilgraph von Degre erhalten und Baumweite Ω ( k / p o l y l o g ( k ) ) . Sie können das Baumbreite-Sparsifier-Papier für das Argument sehen, um dies zu erreichen.log2(k)Ω(k/polylog(k))

Chandra Chekuri
quelle
1
Ω(k)nΘ(n/logn)Θ(logn)
Ω(l4polylog(l))Ω(l)Kl
Auch dies ist sehr hilfreich, danke. Es ist interessant, dass die Frage nach der linearen Baumbreite noch offen ist. (Wenn ich das richtig verstehe, handelt es sich bei Conjecture 1.2 in Ihrem Sparsifier-Papier jedoch um ein etwas anderes Problem: Der Untergraph muss eine Unterteilung von einem H mit einer Polynomgröße in k sein, während ich nicht danach frage und nur möchte Der Untergraph soll einen konstanten Grad haben.) Eine letzte Sache: Wissen Sie, ob etwas über dieses offene Problem bekannt ist, außer für die Pfadbreite und nicht für die Baumbreite? Danke noch einmal!
A3nm
tw(G)pw(G)O(logn)tw(G)
Chandra Chekuri
Vielen Dank für Ihre Erklärungen zum Status der linearen Dreibreite und auch für die Erklärungen zur Sparsifikation der Pfadbreite. Das Letzte, was Sie erwähnt haben, sind die Ergebnisse, die wir benötigt hätten. Schade, dass die Frage noch offen ist. Auf jeden Fall nochmals vielen Dank für Ihre Erklärungen!
A3NM