Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
Moritz Lichter, Benedikt Pago
We show that various recent algorithms for finite-domain constraint satisfaction problems (CSP), which are based on solving their affine integer relaxations, do not solve all tract…
cs.CC2024
Computational complexity of the Weisfeiler-Leman dimension
Moritz Lichter, Simon RaÃmann, Pascal Schweitzer
The Weisfeiler-Leman dimension of a graph is the least number such that the -dimensional Weisfeiler-Leman algorithm distinguishes from every other non-isomorphic gra…