Talks and Poster Presentations (with Proceedings-Entry):
R. Ganian, T. Peitl, F. Slivovsky, S. Szeider:
"Fixed-Parameter Tractability of Dependency QBFwith Structural Parameters";
Talk: 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020,
- 2020-09-18; in: "Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020",
We studydependency quantified Boolean formulas(DQBF),an extension of QBF in which dependencies of existentialvariables are listed explicitly rather than being implicit inthe order of quantifiers. DQBF evaluation is a canonicalNEXPTIME-complete problem, a complexity class contain-ing many prominent problems that arise in Knowledge Rep-resentation and Reasoning.One approach for solving such hard problems is to identifyand exploit structural properties captured by numerical pa-rameters such that bounding these parameters gives rise toan efficient algorithm. This idea is captured by the notionof fixed-parameter tractability (FPT). We initiate the studyof DQBF through the lens of fixed-parameter tractabilityand show that the evaluation problem becomes FPT undertwo natural parameterizations: the treewidth of the primalgraph of the DQBF instance combined with a restriction onthe interactions between the dependency sets, and also thetreedepth of the primal graph augmented by edges represent-ing dependency sets.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.