Hypergraph invariants for computational complexity

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 of instances that exhibit bounded semantic submodular width. Second, we propose a unifying theoretical framework for tractable hypergraph width checking. Following that, we utilize this framework and give some novel results in fractional (hyper)graph theory to resolve important open problems on tractable width checking from the literature. Most important of which, we prove the tractability of deciding low fractional hypertree width for hypergraph 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.