Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-24684
URL: http://www.freidok.uni-freiburg.de/volltexte/2468/


Adler, Isolde

Width functions for hypertree decompositions

Weitefunktionen für Hyperbaumzerlegungen

Dokument1.pdf (945 KB) (md5sum: 36a100154894b2b2e0de11e464c95c16)

Kurzfassung in Englisch

Tree-width, a fundamental notion in graph structure theory, measures how far a graph is from being acyclic. When applied to the underlying graph of a hypergraph or a model-theoretic structure (such as a database, a database query, or an instance of a constraint satisfaction problem) it also gives rise to important algorithmic results: Many problems that are NP-complete in general become polynomially tractable when restricted to instances of bounded tree-width. By a result of Grohe, tree-width is the best graph invariant for this purpose.

Therefore, in order to obtain even larger tractable classes, it is necessary to define invariants directly for structures, or at least for hypergraphs. This was done by Gottlob, Leone and Scarcello, who defined hypertree-width of hypergraphs.

Tree-width is defined in terms of the cardinalities of the pieces of tree-decompositions. Hypertree-width can be understood as a variant of tree-width which results from applying a measure other than cardinality to the pieces. This idea gives rise to a unifying framework (f-hypertree-width) for tree-width, hypertree-width and variants thereof, which we establish and use in this thesis.

Tree-width is very robust in the sense of having many equivalent definitions, e.g. in terms of brambles, havens, or winning strategies in a robber and cops game. We give answers to related robustness questions for hypertree-width and f-hypertree-width.

We also prove an analogue of the compactness property of tree-width of infinite graphs for (generalised) hypertree-width, under a reasonable condition.

Finally, we explore possibilities to obtain even larger tractable classes, e.g. by defining an invariant directly for structures and exploiting functional dependencies.


Kurzfassung in Deutsch

Baumweite, ein grundlegender Begriff in der Strukturtheorie von Graphen, misst, wie weit ein Graph davon entfernt ist, azyklisch zu sein. Angewendet auf den zu Grunde liegenden Graphen eines Hypergraphen oder einer modelltheoretischen Struktur (z.B. einer Datenbank, einer Datenbankanfrage oder einer Instanz von CSP), führt er auch zu wichtigen algorithmischen Resultaten: Viele Probleme, die im Allgemeinen NP-vollständig sind, werden durch Einschränkung auf eine Klasse von beschränkter Baumweite polynomiell berechenbar. Nach einem Resultat von Grohe ist Baumweite die beste Grapheninvariante für diesen Zweck.

Um noch größere polynomiell berechenbare Klassen zu erhalten, ist es daher nötig, Invarianten direkt für Strukturen zu definieren, oder zumindest für Hypergraphen. Gottlob, Leone und Scarcello haben das mit der Definition der Hyperbaumweite von Hypergraphen geleistet.

Baumweite wird über die Mächtigkeiten der Blöcke von Baumzerlegungen definiert. Hyperbaumweite kann man als eine Variante der Baumweite auffassen, bei der die Blöcke anders als durch ihre Mächtigkeit gemessen werden. Diese Idee führt zu einem einheitlichen Framework (f-Hyperbaumweite) für Baumweite, Hyperbaumweite und Varianten davon, welches wir in dieser Arbeit einführen und benutzen.

Baumweite ist in dem Sinne sehr robust, dass sie viele äquivalente Definitionen hat, z.B. über Brambles, Havens oder Gewinnstrategien in einem Räuber-und-Polizisten-Spiel. Wir beantworten damit zusammenhängende Fragen zur Robustheit von Hyperbaumweite und f-Hyperbaumweite.

Wir beweisen auch ein Analogon zur Kompaktheitseigenschaft der Baumweite unendlicher Graphen für die (verallgemeinerte) Hyperbaumweite, und zwar unter einer sinnvollen Bedingung.

Schließlich erkunden wir Möglichkeiten, noch größere polynomiell berechenbare Klassen zu erhalten, z.B. durch die Definition von Invarianten direkt für Strukturen und das Ausnutzen funktionaler Abhängigkeiten.


SWD-Schlagwörter: Hypergraph , Baumweite , Graphentheorie , Datenbank , Constraint-Erfüllung , NP-vollständiges Problem
Freie Schlagwörter (deutsch): Hyperbaumweite , Homomorphieproblem , Räuber-und-Gendarm-Spiel , gerichteter Hypergraph , Kompaktheit
Freie Schlagwörter (englisch): hypertree-width , homomorphism problem , robber and cops game , directed hypergraph , compactness
MSC Klassifikation 91A43 , 68P15 , 05C75 , 05C65 , 03C13
Institut: Institut f. Math. Logik u. Grundlagen d. Mathematik
Fakultät: Fakultät für Mathematik und Physik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Erstgutachter: Flum, Jörg (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 18.04.2006
Erstellungsjahr: 2006
Publikationsdatum: 23.05.2006
Indexliste