Dichotomies for \#CSP on graphs that forbid a clique as a minor

We prove complexity dichotomies for \#CSP problems (not necessarily symmetric) with Boolean domain and complex range on several typical minor-closed graph classes. These dichotomies give a complete characterization of the complexity of \#CSP on graph classes that forbid a complete graph as a minor. In particular, we also demonstrate that, whether the maximum degree of vertices is bounded may influence the complexity on specific minor-closed graph classes, and this phenomenon has never been observed in the previous related studies. Furthermore, our proofs integrate the properties of each graph class with the techniques from counting complexity, and develop a systematic approach for analyzing the complexity of \#CSP on these graph classes.

Publication Details

Journal
ArXiv.org
Published
2025-04-02
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Dichotomies for \#CSP on graphs that forbid a clique as a minor

ArXiv.org
Advanced Graph Theory Research
article

Dichotomies for \#CSP on graphs that forbid a clique as a minor

article en

Abstract

We prove complexity dichotomies for \#CSP problems (not necessarily symmetric) with Boolean domain and complex range on several typical minor-closed graph classes. These dichotomies give a complete characterization of the complexity of \#CSP on graph classes that forbid a complete graph as a minor. In particular, we also demonstrate that, whether the maximum degree of vertices is bounded may influence the complexity on specific minor-closed graph classes, and this phenomenon has never been observed in the previous related studies. Furthermore, our proofs integrate the properties of each graph class with the techniques from counting complexity, and develop a systematic approach for analyzing the complexity of \#CSP on these graph classes.

ArXiv.org
Openalex Percentile: Top 47%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Dichotomies for \#CSP on graphs that forbid a clique as a minor · ArXiv.org (2025) | TGRS Research Map | TGRS