[Back]

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, Rhodes, Greece; 2020-09-12 - 2020-09-18; in: "Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020", (2020), ISSN: 2334-1033; 392 - 402.

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.

http://dx.doi.org/10.24963/kr.2020/40

https://publik.tuwien.ac.at/files/publik_293796.pdf