Journal
THEORETICAL COMPUTER SCIENCE
Volume 982, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2023.114256
Keywords
Holant problems; Computational complexity; Dichotomy; SLOCC
Categories
Ask authors/readers for more resources
This paper investigates the computational complexity classification of Holant problems on 3-regular graphs and provides corresponding conclusions.
Holant problem is a framework to study counting problems, which is expressive enough to contain Counting Graph Homomorphisms (#GH) and Counting Constraint Satisfaction Problems (#CSP) as special cases. In the present paper, we classify the computational complexity of Holant problems on 3-regular graphs, where the signature is complex valued and not necessarily symmetric. In details, we prove that Holant problem on 3-regular graphs is #P-hard except for the signature is not genuinely entangled, A-transformable, P-transformable or vanishing, in which cases the problem is tractable.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available