DC FieldValueLanguage
dc.contributor.advisorPichler, Reinhard-
dc.contributor.authorLanzinger, Matthias Paul-
dc.date.accessioned2021-04-12T13:00:15Z-
dc.date.issued2020-
dc.date.submitted2021-04-
dc.identifier.urihttps://doi.org/10.34726/hss.2021.90042-
dc.identifier.urihttp://hdl.handle.net/20.500.12708/17183-
dc.description.abstractIn 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.en
dc.formatxii, 184 Seiten-
dc.languageEnglish-
dc.language.isoen-
dc.subjecthypergraphsen
dc.subjecthypertree decompositionsen
dc.subjectconjunctive queriesen
dc.subjectnest-set widthen
dc.subjectconstraint satisfaction problemsen
dc.subjectcomputational complexityen
dc.subjectparameterized complexityen
dc.titleHypergraph invariants for computational complexityen
dc.typeThesisen
dc.typeHochschulschriftde
dc.identifier.doi10.34726/hss.2021.90042-
dc.publisher.placeWien-
tuw.thesisinformationTechnische Universität Wien-
tuw.publication.orgunitE192 - Institut für Logic and Computation-
dc.type.qualificationlevelDoctoral-
dc.identifier.libraryidAC16183692-
dc.description.numberOfPages184-
dc.thesistypeDissertationde
dc.thesistypeDissertationen
item.openairetypeThesis-
item.openairetypeHochschulschrift-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.fulltextwith Fulltext-
item.cerifentitytypePublications-
item.cerifentitytypePublications-
item.grantfulltextopen-
item.languageiso639-1en-
crisitem.author.orcid0000-0002-7601-3727-
Appears in Collections:Thesis

Files in this item:

Show simple item record

Page view(s)

18
checked on Jun 3, 2021

Download(s)

22
checked on Jun 3, 2021

Google ScholarTM

Check


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