Guarantees and Limits of Preprocessing in Constraint Satisfaction and Reasoning

Serge Gaspers, Stefan Szeider

We present a first theoretical analysis of the power of polynomial-time preprocessing for important combinatorial problems from various areas in AI. We consider problems from Const…