Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS

DOI10.1016/j.ic.2020.104589zbMath1496.68157arXiv1904.02362OpenAlexW3031765166MaRDI QIDQ2216112

Zhiguo Fu, Jin-Yi Cai, Shuai Shao

Publication date: 15 December 2020

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1904.02362

zbMATH Keywords

unique prime factorizationholant problemEulerian orientation\#CSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational aspects of satisfiability (68R07)

Related Items (1)

Complexity classification of the eight-vertex model

Uses Software

• ROBBINS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of complex weighted Boolean \#CSP
• The complexity of weighted and unweighted \(\#\)CSP
• Calculation of norms of Bethe wave functions
• The complexity of weighted Boolean \#CSP with mixed signs
• Alternating sign matrices and descending plane partitions
• On the evaluation at (3,3) of the Tutte polynomial of a graph
• Complexity classification of the six-vertex model
• Complexity of generalized satisfiability counting problems
• Proof of the alternating sign matrix conjecture
• On the number of Eulerian orientations of a graph
• A Complete Dichotomy Rises from the Capture of Vanishing Signatures
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
• Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• The Complexity of Boolean Holant Problems with Nonnegative Weights
• Complexity Dichotomies for Counting Problems
• Complexity of Counting CSP with Complex Weights
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• A New Holant Dichotomy Inspired by Quantum Computation
• The complexity of the counting constraint satisfaction problem

This page was built for publication: Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS