一句话：为 QSAT 在关联图等结构参数下建立紧下界并给出新 FPT 算法，基本补齐其参数化复杂度图景。
本文研究量化布尔公式求值问题 QSAT 的结构参数化复杂度。已有工作表明，即使原图树宽为常数，QSAT 仍是 PSPACE 完全问题，但以顶点覆盖数为参数存在双指数 FPT 算法；然而关联图等其他自然表示下的复杂度尚不清楚。作者提出结构感知归约，对关联图有界 treedepth 或 feedback vertex number 等高度受限实例给出本质紧的下界，并设计新的 QSAT 算法作为补充。这些结果在标准图论参数化下勾画出近乎完整的复杂度图景，还给出其他图表示的推论，并获得原图更细粒度参数化下的新上界与下界。
The QSAT problem, which asks to evaluate a quantified Boolean formula (QBF), is of fundamental interest in approximation, counting, decision, and probabilistic complexity and is also considered the prototypical PSPACE-complete problem. As such, it has previously been studied under various structural restrictions (parameters), most notably parameterizations of the primal graph representation of instances. Indeed, it is known that QSAT remains PSPACE-complete even when restricted to instances with constant treewidth of the primal graph, but the problem admits a double-exponential fixed-parameter algorithm parameterized by the vertex cover number (primal graph).However, prior works have left a gap in our understanding of the complexity of QSAT when viewed from the perspective of other natural representations of instances, most notably via incidence graphs. In this paper, we develop structure-aware reductions which allow us to obtain essentially tight lower bounds for highly restricted instances of QSAT, including instances whose incidence graphs have bounded treedepth or feedback vertex number. We complement these lower bounds with novel algorithms for QSAT which establish a nearly-complete picture of the problem's complexity under standard graph-theoretic parameterizations. We also show implications for other natural graph representations, and obtain novel upper as well as lower bounds for QSAT under more fine-grained parameterizations of the primal graph.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{abs-2304-13896,
title = {Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF},
author = {Johannes K. Fichte and Robert Ganian and Markus Hecher and Friedrich Slivovsky and Sebastian Ordyniak},
booktitle = {LICS},
year = {2023},
doi = {10.1109/lics56636.2023.10175675}
}