[Zurück]

H. Chen, G. Gottlob, M. Lanzinger, R. Pichler:
"Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems";
Vortrag: IJCAI 2020, Yokohama; 01.01.2021 - 10.01.2021; in: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, {IJCAI} 2020", (2021), S. 1726 - 1733.

Constraint satisfaction problems (CSPs) are an im-portant formal framework for the uniform treatmentof various prominent AI tasks, e.g., coloring orscheduling problems. Solving CSPs is, in general,known to be NP-complete and fixed-parameter in-tractable when parameterized by their constraintscopes. We give a characterization of those classesof CSPs for which the problem becomes fixed-parameter tractable. Our characterization signifi-cantly increases the utility of the CSP frameworkby making it possible to decide the fixed-parametertractability of problems via their CSP formulations.We further extend our characterization to the eval-uation of unions of conjunctive queries, a funda-mental problem in databases. Furthermore, we pro-vide some new insight on the frontier of PTIMEsolvability of CSPs. In particular, we observe thatbounded fractional hypertree width is more generalthan bounded hypertree width only for classes thatexhibit a certain type of exponential growth. Thepresented work resolves a long-standing open prob-lem and yields powerful new tools for complexityresearch in AI and database theory.

http://dx.doi.org/10.24963/ijcai.2020/239

Projektleitung Reinhard Pichler:
HyperTrac