[Back]


Talks and Poster Presentations (with Proceedings-Entry):

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



English abstract:
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.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.24963/ijcai.2020/239



Related Projects:
Project Head Reinhard Pichler:
HyperTrac


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