Title: Hypergraph invariants for computational complexity
Language: English
Authors: Lanzinger, Matthias Paul  
Qualification level: Doctoral
Advisor: Pichler, Reinhard 
Issue Date: 2020
Lanzinger, M. P. (2020). Hypergraph invariants for computational complexity [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2021.90042
Number of Pages: 184
Qualification level: Doctoral
In the study of computational complexity, we search for lower and upper bounds for the effort – be it time, space, or something else – necessary to perform specific algorithmic tasks with a machine. Early efforts in the field focused on the separation of tasks into tractable and intractable problems. One prominent branch of such research is concerned with parameters that express the intricacy of the structure of an instance (we refer to such parameters as widths). In this thesis, we continue this thread of study with a particular focus on problems whose underlying structure is naturally expressed by hypergraphs. First, we study the structure of conjunctive queries (CQs) and Constraint Satisfaction Problems (CSPs) modulo equivalence. That is, we are not only interested in the hypergraph structure of the query, but the simplest (w.r.t. some width measure) hypergraph structure of any equivalent formulation of the query, thus capturing the complexity of the question itself rather than the complexity of the formulation. Building on these characterizations, we show that the parameterized tractability of CQs and unions of CQs (UCQs) is fully captured by the problem structure. Specifically, we demonstrate for CQs and UCQs that their evaluation is fixed-parameter tractable exactly for classes ofinstances that exhibit bounded semantic submodular width. Second, we propose a unifying theoretical framework for tractable hyper- graph width checking. Following that, we utilize this framework and give some novel results in fractional (hyper)graph theory to resolve important open prob- lems on tractable width checking from the literature. Most important of which, we prove the tractability of deciding low fractional hypertree width for hyper- graph classes with bounded intersection. Finally, we propose a novel width parameter – nest-set width – that generalizes hypergraph β-acyclicity. In contrast to existing parameters that generalize β-acyclicity, our proposed width is recognizable in polynomial time and yields important new islands of tractability. In particular, we show that propositional satisfiability is fixed-parameter tractable when parameterized by nest-set width and that the evaluation of CQs with negation is tractable under bounded nest- set width.
Keywords: hypergraphs; hypertree decompositions; conjunctive queries; nest-set width; constraint satisfaction problems; computational complexity; parameterized complexity
URI: https://doi.org/10.34726/hss.2021.90042
DOI: 10.34726/hss.2021.90042
Library ID: AC16183692
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Page view(s)

checked on Oct 22, 2021


checked on Oct 22, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.