|Title:||Hypergraph invariants for computational complexity||Language:||English||Authors:||Lanzinger, Matthias Paul||Qualification level:||Doctoral||Advisor:||Pichler, Reinhard||Issue Date:||2020||Citation:||
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||Abstract:||
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:
checked on Oct 22, 2021
checked on Oct 22, 2021
Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.