×

Beyond #CSP: a dichotomy for counting weighted Eulerian orientations with ARS. (English) Zbl 1496.68157

Summary: We define and explore a notion of unique prime factorization for constraint functions, and use this as a new tool to prove a complexity classification for counting weighted Eulerian orientation problems with arrow reversal symmetry (ars). We prove that all such problems are either polynomial-time computable or #P-hard. We show that the class of weighted Eulerian orientation problems subsumes all weighted counting constraint satisfaction problems (#CSP) on Boolean variables. More significantly, we establish a novel connection between #CSP and counting weighted Eulerian orientation problems that is global in nature. This connection is based on a structural determination of all half-weighted affine linear subspaces over \(\mathbb{Z}_2\), which is proved using Möbius inversion.

MSC:

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

Software:

ROBBINS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Backens, Miriam, A new Holant dichotomy inspired by quantum computation, (44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) (2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik) · Zbl 1441.68159
[2] Backens, Miriam, A complete dichotomy for complex-valued Holant^c, (45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik) · Zbl 1441.68159
[3] Baxter, Rodney J., Exactly Solved Models in Statistical Mechanics (2016), Elsevier · Zbl 0723.60120
[4] Bressoud, David M., Proofs and Confirmations: the Story of the Alternating-Sign Matrix Conjecture (1999), Cambridge University Press · Zbl 0944.05001
[5] Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Jerrum, Mark; Richerby, David, The complexity of weighted and unweighted #CSP, J. Comput. Syst. Sci., 78, 2, 681-688 (2012) · Zbl 1282.68110
[6] Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David, The complexity of weighted Boolean #CSP with mixed signs, Theor. Comput. Sci., 410, 38-40, 3949-3961 (2009) · Zbl 1171.68013
[7] Bulatov, Andrei A., The complexity of the counting constraint satisfaction problem, J. ACM, 60, 5, 1-41 (2013) · Zbl 1281.68130
[8] Cai, Jin-Yi; Chen, Xi, Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain (2017), Cambridge University Press · Zbl 06821418
[9] Cai, Jin-Yi; Chen, Xi, Complexity of counting CSP with complex weights, J. ACM, 64, 3, 1-39 (2017) · Zbl 1426.68114
[10] Cai, Jin-Yi; Chen, Xi; Lu, Pinyan, Nonnegative weighted #CSP: an effective complexity dichotomy, SIAM J. Comput., 45, 6, 2177-2198 (2016) · Zbl 1356.68094
[11] Cai, Jin-Yi; Fu, Zhiguo, Complexity classification of the eight-vertex model (2017), preprint
[12] Cai, Jin-Yi; Fu, Zhiguo, Holographic algorithm with matchgates is universal for planar #CSP over boolean domain, SIAM J. Comput., 17, 50-151 (2019) · Zbl 07516618
[13] Cai, Jin-Yi; Fu, Zhiguo; Xia, Mingji, Complexity classification of the six-vertex model, Inf. Comput., 259, 130-141 (2018) · Zbl 1388.68107
[14] Cai, Jin-Yi; Guo, Heng; Williams, Tyson, A complete dichotomy rises from the capture of vanishing signatures, SIAM J. Comput., 45, 5, 1671-1728 (2016) · Zbl 1350.68133
[15] Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji, Dichotomy for Holant^⁎ problems of Boolean domain, (Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (2011), SIAM), 1714-1728 · Zbl 1373.68256
[16] Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji, The complexity of complex weighted Boolean #CSP, J. Comput. Syst. Sci., 80, 1, 217-236 (2014) · Zbl 1311.68074
[17] Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji, Dichotomy for real Holant^c problems, (Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (2018), SIAM), 1802-1821 · Zbl 1403.68076
[18] Creignou, Nadia; Hermann, Miki, Complexity of generalized satisfiability counting problems, Inf. Comput., 125, 1, 1-12 (1996) · Zbl 0853.68110
[19] Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark, The complexity of weighted Boolean #CSP, SIAM J. Comput., 38, 5, 1970-1986 (2009) · Zbl 1191.68351
[20] Dyer, Martin; Richerby, David, An effective dichotomy for the counting constraint satisfaction problem, SIAM J. Comput., 42, 3, 1245-1274 (2013) · Zbl 1275.68077
[21] Korepin, Vladimir E., Calculation of norms of Bethe wave functions, Commun. Math. Phys., 86, 3, 391-418 (1982) · Zbl 0531.60096
[22] Kuperberg, Greg, Another proof of the alternative-sign matrix conjecture, Int. Math. Res. Not., 1996, 3, 139-150 (1996) · Zbl 0859.05027
[23] Las Vergnas, Michel, On the evaluation at \((3, 3)\) of the Tutte polynomial of a graph, J. Comb. Theory, Ser. B, 45, 3, 367-372 (1988) · Zbl 0674.05024
[24] Lieb, Elliott H., Residual entropy of square ice, Phys. Rev., 162, 1, 162 (1967)
[25] Lieb, Elliott H., Exact solution of the F model of an antiferroelectric, (Condensed Matter Physics and Exactly Soluble Models (2004), Springer), 453-455 · Zbl 1113.01026
[26] Lieb, Elliott H., Exact solution of the two-dimensional Slater KDP model of a ferroelectric, (Condensed Matter Physics and Exactly Soluble Models (2004), Springer), 457-459 · Zbl 1113.01026
[27] Lin, Jiabao; Wang, Hanpin, The complexity of Boolean Holant problems with nonnegative weights, SIAM J. Comput., 47, 3, 798-828 (2018) · Zbl 1397.68105
[28] Mihail, Milena; Winkler, Peter, On the number of Eulerian orientations of a graph, Algorithmica, 16, 4-5, 402-414 (1996) · Zbl 0861.68066
[29] Mills, William H.; Robbins, David P.; Rumsey, Howard, Alternating sign matrices and descending plane partitions, J. Comb. Theory, Ser. A, 34, 3, 340-359 (1983) · Zbl 0516.05016
[30] Pauling, Linus, The structure and entropy of ice and of other crystals with some randomness of atomic arrangement, J. Am. Chem. Soc., 57, 12, 2680-2684 (1935)
[31] Rys, Franz, Über ein zweidimensionales klassisches Konfigurationsmodell, Helv. Phys. Acta, 36, 5, 537-559 (1963) · Zbl 0119.44304
[32] Shao, Shuai; Cai, Jin-Yi, A dichotomy for real Boolean Holant problems (2020), preprint
[33] Slater, John C., Theory of the transition in \(\operatorname{K} \operatorname{H}_2 \operatorname{P} \operatorname{O}_4\), J. Chem. Phys., 9, 1, 16-33 (1941)
[34] Valiant, Leslie G., Holographic algorithms, SIAM J. Comput., 37, 5, 1565-1594 (2008) · Zbl 1152.05010
[35] Zeilberger, Doron, Proof of the alternating sign matrix conjecture, Electron. J. Comb., 3, 2, Article R13 pp. (1996) · Zbl 0858.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.