Dichotomies for \#CSP on graphs that forbid a clique as a minor
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915223228645376 |
|---|---|
| author | Meng, Boning Pan, Yicheng |
| author_facet | Meng, Boning Pan, Yicheng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01354 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dichotomies for \#CSP on graphs that forbid a clique as a minor Meng, Boning Pan, Yicheng Computational Complexity 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. |
| title | Dichotomies for \#CSP on graphs that forbid a clique as a minor |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2504.01354 |