Aufzählung planarer Graphen der begrenzten Baumbreite

9

Ich suche nach Referenzen für das folgende Problem: Wenn die ganzen Zahlen und , werden alle nicht isomorphen planaren Graphen auf Eckpunkten und der Baumbreite aufgelistet . Ich interessiere mich sowohl für theoretische als auch für praktische Ergebnisse, aber hauptsächlich für praktische Algorithmen, mit denen möglichst große Werte von und und ausgeführt werden können (denken Sie an und ). Wenn Sie bereits eine Antwort haben, ignorieren Sie die folgenden Streifzüge.nknknkk5n15

Der folgende Ansatz funktioniert in Ordnung, um alle nicht-isomorphen Graphen auf Eckpunkten und Baumbreite aufzulisten (dh wenn die Planaritätsbeschränkung aufgehoben wird):nk

(a) Zählen Sie alle nicht-isomorphen Graphen auf Eckpunkten und Baumbreite .n1k

(b) Für jeden Scheitelpunkt auf Scheitelpunkten und jede Baumbreite , jede Clique auf Scheitelpunkten in und jede Teilmenge von Kanten in wird aus durch Hinzufügen eines neuen Scheitelpunkts benachbart . Fügen Sie zur Liste von Grahs auf Eckpunkten und Baumbreite .Gn1kCkGSCGGSvCGLnk

(c) Schneiden Sie indem Sie Kopien desselben Diagramms entfernen.L

Eine verlockende Möglichkeit, dies zu erweitern, um planare Diagramme der Baumbreite aufzulisten, besteht darin, die nicht planaren Diagramme bei jeder Iteration einfach herauszufiltern. Leider werden dadurch nicht alle planaren Graphen von treewidth generiert (zum Beispiel, weil nur -degenerierte Graphen aufgelistet werden).kk4

Natürlich könnten wir alle Graphen auf Eckpunkten und Baumbreite aufzählen und erst dann die nicht planaren herausfiltern, aber dies nutzt nicht aus, dass die meisten Graphen nicht planar sind und sehr suboptimal erscheinen.nk

Daniello
quelle
Sind Sie sicher, dass Sie es implementieren und das Ergebnis testen möchten? Die Anzahl der nicht isomorphen Bäume ist bereits exponentiell.
Saeed
@Saeed: sicher - für 20 Knoten beträgt die Anzahl der Bäume weniger als eine Million, daher erwarte ich, dass dies zumindest für machbar ist . n15
Daniello
1
Wie wäre es, wenn Sie von Vertex-Akkordgraphen der maximalen Cliquengröße und Kanten entfernen, um sie planar zu machen? k + 1nk+1
Yixin Cao
@Yixin Cao dies sieht ähnlich aus wie das Aufzählen von Graphen + Baumzerlegungen davon (dh das gleiche Diagramm wird einmal pro Baumdez. Davon gesehen). Bisher war das ziemlich langsam (aber einige Optimierungen könnten diesen Ansatz praktikabel machen)
Daniello
2
@daniello, ich verstehe Ihren Standpunkt, aber haben Sie diese Anwendung gesehen: cs.anu.edu.au/~bdm/plantri , sie behaupten, dass sie 1M planare Graphen in einer Sekunde erzeugen können (in Bezug auf Isomorphismus). (Es ist jedoch nicht genau das, was Sie wollen. Für 1-2-3 verbundene planare Diagramme scheint es perfekt zu sein. Es gibt jedoch nicht viele 4-5 verbundene planare Diagramme auf 15 Eckpunkten.)
Saeed

Antworten:

2

Es gibt eine nette Software , die kleine planare Graphen in Bezug auf Isomorphismus erzeugt, die helfen könnten. Wie ich sehe, bestand eines der Probleme darin, nicht-isomorphe planare Graphen zu erzeugen, und die meisten dieser planaren Graphen (auf weniger als 15 Eckpunkten) haben eine kleine Baumbreite.

Um zu überprüfen, ob ihre Baumbreite kleiner als der gegebene Wert , besteht eine Möglichkeit darin, heuristische Algorithmen zu verwenden, um diese Berechnung zu beschleunigen, nur für den Fall, dass genaue Algorithmen nicht praktikabel sind. zB in einem planaren Graphen können wir zuerst einen Durchmesser von und den entsprechenden Pfad der Länge (der ein Durchmesser ist) finden. Finden Sie dann einen Scheitelpunkt der den kürzesten längsten Abstand ( ) zu einem anderen Scheitelpunkt unter allen Scheitelpunkten . Die Baumbreite von beträgt höchstens , wenn diese kleiner alsG G P d v P l u G P w P G d + l kkGGPdvPluGPwPGd+lk Dann wenden wir entweder andere heuristische Algorithmen an oder führen den genauen Algorithmus aus.

Für weniger als 3 verbundene Diagramme ist es auch möglich, Heuristiken anzuwenden, indem geschnittene Scheitelpunkte gefunden und dann diese Scheitelpunkte korrigiert und die Baumbreite eines verbleibenden Diagramms ermittelt werden. Aber da die Anzahl der Knoten klein ist ( ), wenn der Graph verbunden ist, ist der Durchmesser nicht groß und ich denke, die erste Heuristik sollte dort funktionieren. (Ich weiß nicht, ob es auf höchstens 15 Eckpunkten 5 verbundene planare Graphen gibt, aber wie wir wissen, gibt es keinen verbundenen planaren Graphen für )4 t t > 5154tt>5

Da die Größe des größten Hindernisses für die Baumbreite nicht bekannt ist, können wir den oberen Grenzwert der Baumbreite eines gegebenen Graphen nicht einfach erraten . Aber es scheint, dass es zumindest für planare Graphen nicht so groß sein sollte (man sollte einen Beweis dafür geben).G.kG

Saeed
quelle
1

Man kann alle Paare aufzählen wobei ein planarer Graph mit einer Baumbreite von höchstens , ein Beutel der Größe so dass eine Baumzerlegung von mit als Beutel existiert.G k B k G B.G,BGkBkGB

Nun für jedes Paar , wo hat Vertices bauen wir einen neuen Graphen für jede Teilmenge von durch einen Scheitelpunkt Zugabe mit als Nachbarn und lassen wird , um eine Größe Teilmenge von . Addiere wenn planar und nicht isomorph zu einem bereits gefundenen Paar ist.G n - 1 G ' S B v S B ' k B v G ' , B ' G 'G,BGn1GSBvSBkBvG,BG

Eine einfache Obergrenze für die Anzahl der zu speichernden Einträge ist fache der Anzahl der aufgezählten Diagramme, dies ist jedoch eine pessimistische Grenze. Für die meisten Graphen der Baumbreite k können die meisten Teilmengen der Größe k keinen Beutel haben, z. B. hat ein Gitter nur mögliche Beutel.(nk)k×nn3k1

Ich glaube, dass dies genauso gut funktioniert wie der Algorithmus für nicht planare Graphen, da wir für jedes Paar G, B einen Graphen erhalten, indem wir B zu einer Clique machen. Die meisten dieser Graphen sind nicht isomorph.

Es gibt verschiedene Tricks, die man anwenden kann, um dies zu beschleunigen. Ich würde vorschlagen, sie zu untersuchen: http://www.siam.org/meetings/alenex04/abstacts/HBodlaender.pdf

Martin Vatshelle
quelle
Haben nicht alle aufgezählten Graphen die Pfadbreite und nicht die Baumbreite begrenzt?
Daniello
Ich glaube, Du hast recht. Die Wahl von B 'ist zu begrenzt.
Martin Vatshelle