Dichotomy result on 3-regular bipartite non-negative functions

DOI10.1007/978-3-030-79416-3_6OpenAlexW3177479752MaRDI QIDQ5918629

Jin-Yi Cai, Austen Z. Fan

Publication date: 21 March 2022

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

bipartite graphdichotomy theoremholant problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Bipartite 3-regular counting problems with mixed signs ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Bipartite 3-regular counting problems with mixed signs

Cites Work

• Unnamed Item
• Holant problems for 3-regular graphs with complex edge functions
• Clustering to minimize the maximum intercluster distance
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• 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
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Holographic Algorithms
• The Complexity of Boolean Holant Problems with Nonnegative Weights
• Complexity Dichotomies for Counting Problems
• Complexity of Counting CSP with Complex Weights
• Holant Clones and the Approximability of Conservative Holant Problems
• Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
• The complexity of the counting constraint satisfaction problem