Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
R. Ganian, T. Peitl, F. Slivovsky, S. Szeider:
"Fixed-Parameter Tractability of Dependency QBFwith Structural Parameters";
Vortrag: 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020,
Rhodes, Greece;
12.09.2020
- 18.09.2020; in: "Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020",
(2020),
ISSN: 2334-1033;
S. 392
- 402.
Kurzfassung englisch:
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.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.24963/kr.2020/40
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_293796.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.