Treelike and Chordal Graphs: Algorithms and Generalizations

  • Many graph problems that are NP-hard on general graphs have polynomial-time solutions on trees. Usually, one traverses a tree bottom-up and collects all necessary information such that an optimal solution is found at the root of the tree. Algorithms on trees are simple because every vertex v in a tree is the only connection between its descendants and the remaining vertices; in other words, every inner vertex v defines a so-called separator {v}. In 1984, Robertson and Seymour generalized this technique on trees to general graphs by introducing so-called tree decompositions, which are--intuitively speaking--packings of a graph into a tree such that almost every node of the tree corresponds to a separator in the graph. For a fast algorithm that generalizes an algorithm on trees, it is not enough to have several separators since the performance of an algorithm depends strongly on the size of the separators used: the smaller the separators, the better the algorithm. To denote the maximalMany graph problems that are NP-hard on general graphs have polynomial-time solutions on trees. Usually, one traverses a tree bottom-up and collects all necessary information such that an optimal solution is found at the root of the tree. Algorithms on trees are simple because every vertex v in a tree is the only connection between its descendants and the remaining vertices; in other words, every inner vertex v defines a so-called separator {v}. In 1984, Robertson and Seymour generalized this technique on trees to general graphs by introducing so-called tree decompositions, which are--intuitively speaking--packings of a graph into a tree such that almost every node of the tree corresponds to a separator in the graph. For a fast algorithm that generalizes an algorithm on trees, it is not enough to have several separators since the performance of an algorithm depends strongly on the size of the separators used: the smaller the separators, the better the algorithm. To denote the maximal size of a separator guaranteed by a tree decomposition, Robertson and Seymour therefore introduced a parameter called the width of a tree decomposition. The so-called treewidth of a graph G is the smallest width of a tree decomposition of G. The asymptotic fastest algorithm for finding a tree decomposition on graphs with constant treewidth k was presented 1996 by Bodlaender. He solved the problem in linear time. However, his algorithm is not practical already for very small values k>=4. One of the most efficient algorithms that, for each n-vertex graph G with constant treewidth k, computes a tree decomposition for G of width O(k) is Reed's algorithm of 1992 whose running time is O(n log n). After the introduction of tree decomposition and treewidth, many results were published describing a linear-time algorithm for solving an NP-hard graph problem on every graph class whose treewidth is bounded by a constant. Examples are 3-coloring, maximum independent set, maximum triangle matching, minimum edge dominating set, minimum dominating set, minimum maximal matching, and minimum vertex cover. From a theoretical point of view, using Bodlaender's algorithm, we can solve all problems listed above in linear time on every graph class with bounded treewidth. However, practical linear-time algorithms for these problems on graphs of bounded treewidth do not exist because there are no practical algorithms for computing the tree decomposition. But for planar graphs--one of the most important subclass of the general graphs--with n vertices and constant treewidth k, we show how to find a tree decomposition of width O(k) in linear time. On planar graphs, all the problems mentioned above remain NP-hard. Thus, many problems that are NP-hard on planar graphs can be solved in linear time if the given graph is planar and has constant treewidth. By using the so-called outerplanarity index, we present a second approach to find a tree decomposition on planar graphs in linear time. Many problems solvable on graphs of bounded treewidth have something in common: they can be formulated in so-called monadic second order logic (MSOL). In 1990, Courcelle showed that all MSOL problems can be solved in polynomial time on graphs with constant treewidth. His approach is also to generalize an algorithm on trees to an algorithm on graphs of bounded treewidth. This only works if the graph problem under consideration can be solved on a tree in polynomial time. Using a new complexity parameter we show for three coloring problems that polynomial-time solvability on trees generalizes to polynomial-time solvability on graphs of bounded treewidth. We also consider another subclass of the general graphs called chordal graphs, which do not have small treewidth in general, but they have a special tree decomposition called a clique tree. Many NP-hard problems can be solved on chordal graphs using clique trees. By combining techniques on (clique) trees with a so-called sparsification technique, we obtain the first linear time algorithm for a fixed r that solves the so-called r-disjoint path problem on chordal graphs. Chordal graphs, which are already generalizations of trees by their clique tree, can be further generalized by three partly new complexity parameters measuring the similarity to chordal graphs. These parameters are used to construct new and simple polynomial-time approximation algorithms for many NP-hard problems if they are restricted to graphs bounded with respect to one of the three complexity parameters.show moreshow less
  • Viele Graphprobleme, die auf allgemeinen Graphen NP-hart sind, haben Polynomialzeit-Lösungen auf Bäumen. Üblicherweise findet man eine Lösung auf einem Baum, indem man ihn von unten nach oben durchläuft und an der Wurzel eine Lösung findet. Probleme auf Bäumen sind einfach, da jeder Knoten in einem Baum die einzige Verbindung zwischen seinen Vor- und Nachfahren ist. Somit ist jeder innere Knoten v des Baumes ein sogenannter Separator {v}. Robertson und Seymour verallgemeinerten 1984 diese Technik von Bäumen auf allgemeine Graphen, indem sie sogenannte Baumzerlegungen einführten. Eine Baumzerlegung für einen Graphen ist intuitiv ein Baum, in dem fast jeder Knoten einem Separator im Graphen entspricht. Die Laufzeit eines solchen Algorithmus, der aus der Verallgemeinerung eines Algorithmus auf Bäumen entsteht, hängt stark von der Größe der verwendeten Separatoren ab, wobei gilt: Kleinere Separatoren führen zu schnelleren Algorithmen. Für die maximale Größe eines garantierten SeparatorsViele Graphprobleme, die auf allgemeinen Graphen NP-hart sind, haben Polynomialzeit-Lösungen auf Bäumen. Üblicherweise findet man eine Lösung auf einem Baum, indem man ihn von unten nach oben durchläuft und an der Wurzel eine Lösung findet. Probleme auf Bäumen sind einfach, da jeder Knoten in einem Baum die einzige Verbindung zwischen seinen Vor- und Nachfahren ist. Somit ist jeder innere Knoten v des Baumes ein sogenannter Separator {v}. Robertson und Seymour verallgemeinerten 1984 diese Technik von Bäumen auf allgemeine Graphen, indem sie sogenannte Baumzerlegungen einführten. Eine Baumzerlegung für einen Graphen ist intuitiv ein Baum, in dem fast jeder Knoten einem Separator im Graphen entspricht. Die Laufzeit eines solchen Algorithmus, der aus der Verallgemeinerung eines Algorithmus auf Bäumen entsteht, hängt stark von der Größe der verwendeten Separatoren ab, wobei gilt: Kleinere Separatoren führen zu schnelleren Algorithmen. Für die maximale Größe eines garantierten Separators führten deshalb Robertson und Seymour als neuen Parameter die Bezeichnung Weite einer Baumzerlegung ein. Außerdem definierten sie die Baumweite eines Graphen G als die kleinste Weite einer Baumzerlegung von G. Der asymptotisch schnellste Algorithmus auf Graphen mit n Knoten und konstanter Baumweite k zum Berechnen einer Baumzerlegung der Weite O(k) ist der Linearzeit-Algorithmus von Bodlaender. Dieser Algorithmus ist jedoch schon für alle k>=4 nicht mehr praktikabel. Einer der effizientesten Algorithmen ist der Algorithmus von Reed mit einer Laufzeit von O(n log n). Nach der Einführung von Baumzerlegungen und der Baumweite wurden viele Linearzeit-Algorithmen veröffentlicht, die NP-harte Probleme auf Graphen mit beschränkter Baumweite in Linearzeit lösen. Beispiele sind 3-Coloring, Maximum Independent Set, Maximum Triangle Matching, Minimum Edge Dominating Set, Minimum Dominating Set, Minimum Maximal Matching und Minimum Vertex Cover. Theoretisch erlaubt Bodlaenders Algorithmus somit alle diese Probleme auf Graphen mit beschränkter Baumweite in Linearzeit zu lösen. Praktikable Linearzeit-Algorithmen existieren jedoch nicht, da kein solcher Algorithmus zum Berechnen einer Baumzerlegung existiert. Wir beschreiben für planare Graphen - eine der wichtigsten Subklassen der allgemeinen Graphen - mit n Knoten und konstanter Baumweite k einen Algorithmus zum Berechnen einer Baumzerlegung in linearer Zeit. Obwohl alle oben erwähnten Probleme auf planaren Graphen NP-hart bleiben, lassen sich diese Probleme somit in Linearzeit lösen, sofern die Graphen beschränkte Baumweite haben. Mithilfe des sogenannten Outerplanarity-Indexes stellen wir eine weitere Möglichkeit vor, wie eine Baumzerlegung auf planaren Graphen in Linearzeit gefunden werden kann. Viele der Probleme, die sich auf Graphen mit beschränkter Baumweite lösen lassen, haben eines gemeinsam: Sie lassen sich mithilfe von monadischer Logik zweiter Ordnung (MSOL) formulieren. Courcelle zeigte 1990, dass alle MSOL-Probleme auf Graphen mit beschränkter Baumweite in Polynomialzeit gelöst werden können, indem er ebenfalls einen Algorithmus von Bäumen auf Graphen beschränkter Baumweite verallgemeinerte. Folglich funktioniert sein Ansatz nur für Graphprobleme, die auch auf Bäumen in Polynomialzeit gelöst werden können. Mithilfe eines neuen Komplexitätsparameters wird für drei Färbungsprobleme gezeigt, dass sich die Polynomialzeit-Lösbarkeit dieser Probleme wieder von Bäumen auf Graphen mit beschränkter Baumweite verallgemeinert. Eine weitere Subklasse der allgemeinen Graphen sind die chordalen Graphen. Deren Baumweite ist zwar nicht immer beschränkt, aber sie haben eine ganz spezielle Baumzerlegung, die Clique-Baum genannt wird. Viele NP-harte Probleme können unter Verwendung des Clique-Baumes auf chordalen Graphen gelöst werden. Wir kombinieren die Technik auf (Clique-)Bäumen mit einer sogenannten Sparsification-Technik, um für ein festes r das sogenannte r-disjunkte Pfade Problem in Linearzeit zu lösen. Chordale Graphen, die durch ihre Clique-Bäume bereits Verallgemeinerungen von Bäumen sind, können mithilfe von drei teilweise neuen Komplexitätsparametern noch weiter verallgemeinert werden. Es wird gezeigt, dass auf Graphklassen, in denen mindestens einer dieser Komplexitätsparameter beschränkt ist, Approximationsalgorithmen mit polynomieller Laufzeit für viele NP-harte Probleme existieren.show moreshow less

Download full text files

Export metadata

Statistics

Number of document requests

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Frank Kammer
URN:urn:nbn:de:bvb:384-opus-18365
Frontdoor URLhttps://opus.bibliothek.uni-augsburg.de/opus4/1606
Title Additional (German):Baumähnliche und Chordale Graphen: Algorithmen und Verallgemeinerungen
Advisor:Torben Hagerup
Type:Doctoral Thesis
Language:English
Publishing Institution:Universität Augsburg
Granting Institution:Universität Augsburg, Fakultät für Angewandte Informatik
Date of final exam:2010/10/22
Release Date:2012/01/27
Tag:Graphenalgorithmen; Baumzerlegungen; chordale Graphen
graph algorithms; tree decompositions; chordal graphs
GND-Keyword:Graphentheorie; Baumweite; Approximationsalgorithmus; NP-hartes Problem; Planarer Graph; Divide-and-conquer-Verfahren
Institutes:Fakultät für Angewandte Informatik
Fakultät für Angewandte Informatik / Institut für Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):Deutsches Urheberrecht