Fixed-Parameter Tractability of Dependency QBF with Structural Parameters
Fixed-Parameter Tractability of Dependency QBF with Structural Parameters
复制标题
具有结构参数的依赖 QBF 的固定参数可处理性
DOI：
10.24963/kr.2020/40
复制
发表时间：
2020
影响因子：
1.2
通讯作者：
Stefan Szeider
中科院分区：
文献类型：
--
作者：
R. Ganian;Tomáš Peitl;Friedrich;Slivovsky;Stefan Szeider
我们研究依赖性量化布尔公式（DQBF），这是 QBF 的扩展，其中存在变量的依赖性被显式列出，而不是隐含在量词的顺序中。 DQBF 评估是一个典型的 NEXPTIME 完全问题，是一个复杂性类别，包含知识表示和推理中出现的许多突出问题。解决此类难题的一种方法是识别和利用数值参数捕获的结构特性，从而限制这些参数产生有效的算法。固定参数易处理性（FPT）的概念体现了这个想法。我们从固定参数易处理性的角度开始对 DQBF 的研究，并表明评估问题在两种自然参数化下变成了 FPT：DQBF 实例的原始图的树宽与依赖集之间的相互作用相结合，以及由表示依赖集的边增强的原始图的树深。
We study dependency quantified Boolean formulas (DQBF), an extension of QBF in which dependencies of existential variables are listed explicitly rather than being implicit in the order of quantifiers. DQBF evaluation is a canonical NEXPTIME-complete problem, a complexity class containing many prominent problems that arise in Knowledge Representation and Reasoning. One approach for solving such hard problems is to identify and exploit structural properties captured by numerical parameters such that bounding these parameters gives rise to an efficient algorithm. This idea is captured by the notion of fixed-parameter tractability (FPT). We initiate the study of DQBF through the lens of fixed-parameter tractability and show that the evaluation problem becomes FPT under two natural parameterizations: the treewidth of the primal graph of the DQBF instance combined with a restriction on the interactions between the dependency sets, and also the treedepth of the primal graph augmented by edges representing dependency sets.
DOI：
10.1007/s10817-008-9114-5
发表时间：
2009-01-01
期刊：
JOURNAL OF AUTOMATED REASONING
影响因子：
--
作者：
Samer, Marko;Szeider, Stefan
通讯作者：
Szeider, Stefan