Baumweite

Die Baumweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie baum-ähnlich ein Graph ist. Da viele Algorithmen auf Bäumen effizient laufen, die dies auf allgemeinen Graphen nicht tun, ist es interessant, die Baumweite und eine zugehörige minimale Baumzerlegung eines Graphen zu kennen. Ein verwandter Begriff ist die Pfadweite.

Der Begriff wurde 1972 von Umberto Bertelè und Francesco Brioschi eingeführt, unabhängig von Rudolf Halin 1976 und erneut unabhängig von Neil Robertson und Paul Seymour 1984.

Formale Definition

Eine Baumzerlegung eines Graphen ${\displaystyle G=(V,E)}$ ist ein Paar ${\displaystyle (X,T)}$, wobei ${\displaystyle T=(I,F)}$ ein Baum und ${\displaystyle X=\{X_{i}~|~i\in I\}}$ eine Familie von Untermengen der Knotenmenge ${\displaystyle V}$ des Graphen ist, sodass folgende Bedingungen gelten, wobei 3 und 4 Äquivalent zueinander sind:

1. ${\displaystyle \bigcup _{i\in I}X_{i}=V}$.
2. Für alle Kanten ${\displaystyle \{v,w\}\in E}$ gibt es ein ${\displaystyle i\in I}$ mit ${\displaystyle v,w\in X_{i}}$.
3. Für alle ${\displaystyle i,j,k\in I}$ gilt: wenn ${\displaystyle j}$ auf dem Pfad von ${\displaystyle i}$ zu ${\displaystyle k}$ in ${\displaystyle T}$ ist, dann ${\displaystyle X_{i}\cap X_{k}\subseteq X_{j}}$.
4. Für alle ${\displaystyle v\in V}$ induziert die Menge ${\displaystyle I_{v}=\{i\in I|v\in X_{i}\}}$ einen zusammenhängenden Teilbaum in ${\displaystyle T}$.

Die Weite der Baumzerlegung ${\displaystyle (X,T)}$ von ${\displaystyle G}$ ist definiert als ${\displaystyle \max _{i\in I}|X_{i}|-1}$ und die Baumweite ${\displaystyle \operatorname {tw} (G)}$ eines Graphen ${\displaystyle G}$ ist definiert als die kleinste Weite aller möglichen Baumzerlegungen von ${\displaystyle G}$.

Die Subtraktion von 1 in dieser Definition bewirkt, dass Bäume (und Wälder) die Baumweite 1 haben. Ohne diese Subtraktion hätten nur Graphen ohne Kanten die Baumweite 1.

Eigenschaften

Berechnung

Zur Berechnung der Baumweite eines Graphen existieren mehrere Algorithmen, darunter gibt es kombinatorische Ansätze, wie den Bodländer Algorithmus oder ganzzahlige lineare Ansätze. Allen Ansätzen ist gemein, dass sie nur für kleine Instanzen, bzw. kleine und beschränkte Baumweite schnelle Ergebnisse liefern.

Preprocessing

Das Preprocessing beschreibt eine Vorberechnung, vor der Ausführung des eigentlichen Lösungsalgorithmus. Ziel ist es dabei, die gegebene Graphen Instanz zu verkleinern/reduzieren, damit der Hauptalgorithmus auf jener kleineren Instanz schneller eine Lösung finden kann. Beim Preprocessing wird die gesuchte Eigenschaft (hier Baumweite) nicht verändert oder bereits eine Lösung ausgegeben.

Für das Baumweite Problem existieren Preprocessing Regeln, die hierarchisch aufeinander stehen und in der Lage sind, Graphen bis zu einer Baumweite von 3 zu erkennen oder eine reduzierte Instanz mit Baumweite von mindestens 4 zu erzeugen.

Baumweite 0

Reduktionsregel 0: Inselchen Regel (engl. Islet rule)
Sei ${\displaystyle v}$ ein Knoten mit Grad 0.
Entferne ${\displaystyle v}$.

Baumweite 1

Reduktionsregel 1: Zweig-Regel (engl. Twig rule)
Sei ${\displaystyle v}$ ein Knoten mit Grad 1.
Entferne ${\displaystyle v}$.

Baumweite 2

Reduktionsregel 2: Serien Regel (engl. Series rule)
Sei ${\displaystyle v}$ ein Knoten mit Grad 2.
Füge eine Kante zwischen den Nachbarn von ${\displaystyle v}$ ein, falls sie noch nicht existiert.
Entferne ${\displaystyle v}$.

Baumweite 3

Reduktionsregel 3a: Dreiecks Regel (engl. Triangle rule)
Sei ${\displaystyle v}$ ein Knoten mit Grad 3, wobei mindestens zwei Nachbarn durch eine Kante miteinander verbunden sind.
Vervollständige die 3 Nachbarn von ${\displaystyle v}$ zu einer Clique.
Entferne ${\displaystyle v}$.

Reduktionsregel 3b: Kumpel Regel (engl. Buddy rule)
Seien ${\displaystyle v,w}$ Knoten mit Grad 3 mit den gleichen Nachbarn.
Vervollständige die 3 Nachbarn von ${\displaystyle v}$ und ${\displaystyle w}$ zu einer Clique.
Entferne ${\displaystyle v}$ und ${\displaystyle w}$.

Reduktionsregel 3c: Würfel Regel (engl. Cube rule)
Seien ${\displaystyle a,b,c,d,x,v,w}$ Knoten, die Knoten ${\displaystyle a,b,c,d}$ besitzen Grad 3, ${\displaystyle C=(a,v,b,x,c,w,a)}$ ist ein ${\displaystyle 6}$-Kreis und ${\displaystyle a,b,c}$ sind mit ${\displaystyle d}$ verbunden.
Vervollständige ${\displaystyle v,w,x}$ zu einer Clique.
Entferne ${\displaystyle a,b,c,d}$.

Aus der Anwendung der Preprocessing Regeln lassen sich folgende Aussage ableiten:

Für einen Graphen ${\displaystyle G}$ wende die Preprocessing Regeln zwischen ${\displaystyle 0}$ und ${\displaystyle k,k\in \{0,1,2,3\}}$ an, bis dies nicht mehr möglich ist. Erhält man als Endergebnis den leeren Graphen, so gilt ${\displaystyle \operatorname {tw} (G)\leq k}$,
erhält man nicht den leeren Graphen, so gilt für den entstandenen Graphen ${\displaystyle G'}$, als auf für ${\displaystyle G}$ die Ungleichung ${\displaystyle \operatorname {tw} (G),\operatorname {tw} (G')>k}$.

Literatur

• Reinhard Diestel: Graphentheorie. 5. Auflage. Springer-Verlag, Berlin, Heidelberg 2010, ISBN 978-3-96134-004-0, 10. Minoren, S. 287–330. 
• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exakte Algorithmen für schwere Graphenprobleme. Springer-Verlag, Berlin, Heidelberg 2010, ISBN 978-3-642-04499-1. 
• Hans L. Bodlaender: Fixed-Parameter Tractability of Treewidth and Pathwidth. In: Bodlaender H.L., Downey R., Fomin F.V., Marx D. (Hrsg.): The Multivariate Algorithmic Revolution and Beyond. LNCS 7370. Springer, Berlin, Heidelberg 2012, ISBN 978-3-642-30890-1, S. 196–227, doi:10.1007/978-3-642-30891-8_12. 

Einzelnachweise

1. ↑ Bertelè, Brioschi, Nonserial Dynamic Programming, Academic Press 1972, dort Dimension genannt
2. ↑ Halin, S-functions for graphs, J. Geom., 8, 1976, 171–186
3. ↑ Robertson, Seymour: Graph minors III: Planar tree-width, Journal of Combinatorial Theory, Series B, Band 36, 1984, S. 49–64
4. ↑ Hans L. Bodlaender, Arie M. C. A. Koster: Treewidth computations I. Upper bounds. In: Information and Computation. Band 208, Nr. 3, 1. März 2010, ISSN 0890-5401, S. 259–275, doi:10.1016/j.ic.2009.03.008. 
5. ↑ S. Arnborg; D. Corneil; A. Proskurowski: Complexity of finding embeddings in a k-tree. SIAM Journal on Matrix Analysis and Applications, 8 (2) 1987, S. 277–284
6. ↑ Hans L. Bodlaender: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25 (6) 1996, S. 1305–1317
7. ↑ Fedor V. Fomin, Dimitrios M. Thilikos: New upper bounds on the decomposability of planar graphs. In: Journal of Graph Theory. Band 51, Nr. 1, 2006, S. 53–81, doi:10.1002/jgt.20121. 
8. ↑ Hans L. Bodlaender: A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing (= STOC '93). Association for Computing Machinery, New York, NY, USA 1993, ISBN 978-0-89791-591-5, S. 226–234, doi:10.1145/167088.167161 (acm.org [abgerufen am 3. Oktober 2025]). 
9. ↑ Sven Mallach: On integer linear programs for treewidth based on perfect elimination orderings (extended version). In: Acta Informatica. Band 62, Nr. 3, 26. August 2025, ISSN 1432-0525, S. 34, doi:10.1007/s00236-025-00505-y. 
10. 1 2 Hans L. Bodlaender and Arie M.C.A. Koster and Frank van den Eijkhof and Linda C. van der Gaag: Pre-processing for Triangulation of Probabilistic Networks. Hrsg.: ZIB. Berlin 2001, S. 01–39.