@inproceedings{c364d001534b4aa3b2c5624dbef2b07d,
title = "Dichotomies for \#CSP on Graphs That Forbid a Clique as a Minor",
abstract = "We establish complexity dichotomies for \#CSP and \#RD-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 \#RD-CSP over graph classes that forbid a complete graph as a minor. Notably, our algorithms apply not only to \#CSP and \#RD-CSP problems but also directly to the Holant setting.",
keywords = "Computational Complexity, Constraint Satisfaction Problem, Counting, Graph Minor, Holant, Matchgate, Tree Decomposition",
author = "Boning Meng and Yicheng Pan",
note = "Publisher Copyright: {\textcopyright} Boning Meng and Yicheng Pan.; 34th Annual European Symposium on Algorithms, ESA 2026 ; Conference date: 31-08-2026 Through 04-09-2026",
year = "2026",
month = aug,
day = "25",
doi = "10.4230/LIPIcs.ESA.2026.47",
language = "英语",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Philip Bille and Seth Pettie and Sabine Storand",
booktitle = "34th Annual European Symposium on Algorithms, ESA 2026",
address = "德国",
}