{"id":{"repo_id":"freiburg-diss","oai_identifier":"oai:freidok.uni-freiburg.de:2468"},"canonical_url":"https://search.dev.ndltd.org/etd/freiburg-diss/oai:freidok.uni-freiburg.de:2468","repository":{"repo_id":"freiburg-diss","name":"University of Freiburg","base_url":"https://freidok.uni-freiburg.de/oai/oai2.php"},"display":{"title":"Width functions for hypertree decompositions","abstract":"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.","abstract_html":"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. &lt;br&gt; &lt;br&gt;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. &lt;br&gt; &lt;br&gt;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. &lt;br&gt; &lt;br&gt;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. &lt;br&gt; &lt;br&gt;We also prove an analogue of the compactness property of tree-width of infinite graphs for (generalised) hypertree-width, under a reasonable condition. &lt;br&gt; &lt;br&gt;Finally, we explore possibilities to obtain even larger tractable classes, e.g. by defining an invariant directly for structures and exploiting functional dependencies.","abstract_has_math":false,"creators":["Adler, Isolde"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Flum, Jörg"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-07-24T02:22:46Z","subjects":["Hyperbaumweite","Homomorphieproblem","Räuber-und-Gendarm-Spiel","gerichteter Hypergraph","Kompaktheit","hypertree-width","homomorphism problem","robber and cops game","directed hypergraph","compactness"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://freidok.uni-freiburg.de/data/2468","outbound_label":"Repository record","outbound_source":"source_url"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Flum, Jörg"]},{"key":"dc:creator","label":"Author","values":["Adler, Isolde"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:type","label":"Dc Type","values":["DoctoralThesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Hyperbaumweite","Homomorphieproblem","Räuber-und-Gendarm-Spiel","gerichteter Hypergraph","Kompaktheit","hypertree-width","homomorphism problem","robber and cops game","directed hypergraph","compactness"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.","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. <br> <br>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. <br> <br>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. <br> <br>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. <br> <br>Wir beweisen auch ein Analogon zur Kompaktheitseigenschaft der Baumweite unendlicher Graphen für die (verallgemeinerte) Hyperbaumweite, und zwar unter einer sinnvollen Bedingung. <br> <br>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."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Width functions for hypertree decompositions","Weitefunktionen für Hyperbaumzerlegungen"]}]}],"canonical_facts":{"dc:contributor":["Flum, Jörg"],"dc:creator":["Adler, Isolde"],"dc:description.abstract":["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.","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. <br> <br>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. <br> <br>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. <br> <br>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. <br> <br>Wir beweisen auch ein Analogon zur Kompaktheitseigenschaft der Baumweite unendlicher Graphen für die (verallgemeinerte) Hyperbaumweite, und zwar unter einer sinnvollen Bedingung. <br> <br>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."],"dc:format.medium":["application/pdf"],"dc:subject":["Hyperbaumweite","Homomorphieproblem","Räuber-und-Gendarm-Spiel","gerichteter Hypergraph","Kompaktheit","hypertree-width","homomorphism problem","robber and cops game","directed hypergraph","compactness"],"dc:title":["Width functions for hypertree decompositions","Weitefunktionen für Hyperbaumzerlegungen"],"dc:type":["DoctoralThesis"]},"updated_at":"2026-07-24T02:22:46Z"}