Talks and Poster Presentations (with Proceedings-Entry):

J. Fichte, M. Hecher, M. Kieler:
"Treewidth-Aware Quantifier Elimination and Expansion for {QCSP}";
Talk: CP 2020 - 26th International Conference - Principles and Practice of Constraint Programming, Louvain-laNeuve, Belgium; 2020-09-07 - 2020-09-11; in: "Principles and Practice of Constraint Programming - 26th International Conference, {CP} 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings", (2020), 248 - 266.

English abstract:
Research on the constraint satisfaction problem (CSP) is an active field both in theory and practice. An extension of CSP even considers universal and existential quantification of domain variables, known as QCSP, for which also solvers exist. The number of alternations between existential and universal quantifications is usually called quantifier rank. While QCSP is PSPACE-complete for bounded domain size, one can consider additional structural restrictions that make the problem tractable, for example, bounded treewidth. Chen [14] showed that one can solve QCSP instances of size n, quantifier rank ℓ, bounded treewidth k, and bounded domain size d in poly(n)⋅tower(ℓ−1,dk), where tower are exponentials of height ℓ−1 with dk on top. We follow up on Chenīs result and develop a treewidth-aware quantifier elimination technique that reduces the rank without an exponential blow-up in the instance size at the cost of exponentially increasing the treewidth. With this reduction at hand we show that one cannot significantly improve the blow-up of the treewidth assuming the exponential time hypothesis (ETH). Further, we lift a recently introduced technique for treewidth-decreasing quantifier expansion from the Boolean domain to QCSP.

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Related Projects:
Project Head Stefan Woltran:

Project Head Stefan Woltran:

Created from the Publication Database of the Vienna University of Technology.