Width functions for hypertree decompositions

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. <br> <br>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. <br> <br>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. <br> <br>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. <br> <br>We also prove an analogue of the compactness property of tree-width of infinite graphs for (generalised) hypertree-width, under a reasonable condition. <br> <br>Finally, we explore possibilities to obtain even larger tractable classes, e.g. by defining an invariant directly for structures and exploiting functional dependencies.

Author dc:creator

• Adler, Isolde

Contributors dc:contributor

• Flum, Jörg

• Hyperbaumweite
• Homomorphieproblem
• Räuber-und-Gendarm-Spiel
• gerichteter Hypergraph
• Kompaktheit
• hypertree-width
• homomorphism problem
• robber and cops game
• directed hypergraph
• compactness

Repository record source_url

https://freidok.uni-freiburg.de/data/2468

OAI identifier oai:identifier

oai:freidok.uni-freiburg.de:2468