  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 PSPACEcomplete
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.
