2026-08-25T18:47:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27183 2026-08-25T13:18:17Z ddc:004 open_access

Dichotomies for #CSP on Graphs That Forbid a Clique as a Minor Meng, Boning Pan, Yicheng Graph Minor Tree Decomposition Computational Complexity Counting Constraint Satisfaction Problem Holant Matchgate We establish complexity dichotomies for #CSP and #R_D-CSP problems (not necessarily symmetric) with Boolean domain and complex range over several key minor-closed graph classes. These dichotomies give a complete characterization of the complexity of #CSP and #R_D-CSP over graph classes that forbid a complete graph as a minor. Notably, our algorithms apply not only to #CSP and #R_D-CSP problems but also directly to the Holant setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boning Meng and Yicheng Pan 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.47 urn:nbn:de:0030-drops-271834 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.47 eng https://creativecommons.org/licenses/by/4.0/legalcode