[Back]

R. Ganian, A. Schidler, M. Sorge, S. Szeider:
"Threshold Treewidth and Hypertree Width";
Talk: IJCAI - International Joint Conference on Artificial Intelligence, Yokohama, Japan; 2021-01-07 - 2021-01-15; in: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)", (2021), ISBN: 978-0-9992411-6-5; 1898 - 1904.

Treewidth and hypertree width have proven to be
highly successful structural parameters in the context
of the Constraint Satisfaction Problem (CSP).
When either of these parameters is bounded by a
constant, then CSP becomes solvable in polynomial
time. However, here the order of the polynomial
in the running time depends on the width, and this
is known to be unavoidable; therefore, the problem
is not fixed-parameter tractable parameterized by
either of these width measures. Here we introduce
an enhancement of tree and hypertree width through
a novel notion of thresholds, allowing the associated
decompositions to take into account information
about the computational costs associated with solving
the given CSP instance. Aside from introducing
these notions, we obtain efficient theoretical as well
as empirical algorithms for computing threshold
treewidth and hypertree width and show that these
parameters give rise to fixed-parameter algorithms
for CSP as well as other, more general problems.
We complement our theoretical results with experimental
evaluations in terms of heuristics as well as
exact methods based on SAT/SMT encodings.

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

https://publik.tuwien.ac.at/files/publik_292357.pdf