{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:06:37Z","timestamp":1770739597560,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,3,1]],"date-time":"2012-03-01T00:00:00Z","timestamp":1330560000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,11]]},"DOI":"10.1007\/s00453-012-9626-6","type":"journal-article","created":{"date-parts":[[2012,2,29]],"date-time":"2012-02-29T11:43:24Z","timestamp":1330515804000},"page":"511-533","source":"Crossref","is-referenced-by-count":26,"title":["From Holant to #CSP and Back: Dichotomy for Holant c Problems"],"prefix":"10.1007","volume":"64","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sangxia","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,3,1]]},"reference":[{"key":"9626_CR1","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A.A. Bulatov","year":"2006","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53, 66\u2013120 (2006)","journal-title":"J. ACM"},{"key":"9626_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1007\/978-3-540-70575-8_53","volume-title":"Proceedings of 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Part I: Track A: Algorithms, Automata, Complexity, and Games","author":"A.A. Bulatov","year":"2008","unstructured":"Bulatov, A.A.: The complexity of the counting constraint satisfaction problem. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) Proceedings of 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Part I: Track A: Algorithms, Automata, Complexity, and Games, Reykjavik, Iceland, July 7\u201311, 2008. Lecture Notes in Computer Science, vol. 5125, pp. 646\u2013661. Springer, Berlin (2008)"},{"issue":"5","key":"9626_CR3","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/j.ic.2006.09.005","volume":"205","author":"A.A. Bulatov","year":"2007","unstructured":"Bulatov, A.A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. Inf. Comput. 205(5), 651\u2013678 (2007)","journal-title":"Inf. Comput."},{"key":"9626_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1007\/978-3-540-27836-8_27","volume-title":"Proceedings of 31st International Colloquium on Automata, Languages and Programming: ICALP 2004","author":"A.A. Bulatov","year":"2004","unstructured":"Bulatov, A.A., Grohe, M.: The complexity of partition functions. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) Proceedings of 31st International Colloquium on Automata, Languages and Programming: ICALP 2004, Turku, Finland, July 12\u201316, 2004. Lecture Notes in Computer Science, vol. 3142, pp. 294\u2013306. Springer, Berlin (2004)"},{"issue":"2\u20133","key":"9626_CR5","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"A.A. Bulatov","year":"2005","unstructured":"Bulatov, A.A., Grohe, M.: The complexity of partition functions. Theor. Comput. Sci. 348(2\u20133), 148\u2013186 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9626_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/978-3-642-14165-2_24","volume-title":"Proceedings of 37th International Colloquium on Automata, Languages and Programming, Part I, ICALP 2010","author":"J.y. Cai","year":"2010","unstructured":"Cai, J.y., Chen, X., Lu, P.: Graph homomorphisms with complex values: A dichotomy theorem. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der\u00a0Heide, F., Spirakis, P.G. (eds.): Proceedings of 37th International Colloquium on Automata, Languages and Programming, Part I, ICALP 2010, Bordeaux, France, July 6\u201310, 2010. Lecture Notes in Computer Science, vol. 6198, pp. 275\u2013286. Springer, Berlin (2010)"},{"issue":"1","key":"9626_CR7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.jcss.2010.06.005","volume":"77","author":"J.y. Cai","year":"2011","unstructured":"Cai, J.y., Lu, P.: Holographic algorithms: From art to science. J. Comput. Syst. Sci. 77(1), 41\u201361 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9626_CR8","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/FOCS.2008.34","volume-title":"49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008","author":"J.y. Cai","year":"2008","unstructured":"Cai, J.y., Lu, P., Xia, M.: Holographic algorithms by Fibonacci gates and holographic reductions for hardness. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, October 25\u201328, 2008, pp. 644\u2013653. IEEE Computer Society, Los Alamitos (2008)"},{"key":"9626_CR9","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1145\/1536414.1536511","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009","author":"J.Y. Cai","year":"2009","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Holant problems and counting CSP. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31\u2013June 2, 2009, pp. 715\u2013724. ACM, New York (2009)"},{"issue":"23","key":"9626_CR10","doi-asserted-by":"crossref","first-page":"2468","DOI":"10.1016\/j.tcs.2010.10.039","volume":"412","author":"J.y. Cai","year":"2011","unstructured":"Cai, J.y., Lu, P., Xia, M.: A computational proof of complexity of some restricted counting problems. Theor. Comput. Sci. 412(23), 2468\u20132485 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9626_CR11","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classifications of Boolean Constraint Satisfaction Problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. Society for Industrial and Applied Mathematics, Philadelphia (2001)"},{"key":"9626_CR12","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-10514-2","volume-title":"Tensor Geometry: the Geometric Viewpoint and Its Uses","author":"C.T.J. Dodson","year":"1991","unstructured":"Dodson, C.T.J., Poston, T.: Tensor Geometry: the Geometric Viewpoint and Its Uses. Graduate Texts in Mathematics. Springer, Berlin (1991)"},{"issue":"5","key":"9626_CR13","doi-asserted-by":"crossref","first-page":"1970","DOI":"10.1137\/070690201","volume":"38","author":"M.E. Dyer","year":"2009","unstructured":"Dyer, M.E., Goldberg, L.A., Jerrum, M.: The complexity of weighted Boolean CSP. SIAM J. Comput. 38(5), 1970\u20131986 (2009)","journal-title":"SIAM J. Comput."},{"key":"9626_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/11786986_5","volume-title":"Proceedings of 33rd International Colloquium, on Automata, Languages and Programming, Part I, ICALP 2006","author":"M.E. Dyer","year":"2006","unstructured":"Dyer, M.E., Goldberg, L.A., Paterson, M.: On counting homomorphisms to directed acyclic graphs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) Proceedings of 33rd International Colloquium, on Automata, Languages and Programming, Part I, ICALP 2006, Venice, Italy, July 10\u201314, 2006. Lecture Notes in Computer Science, vol. 4051, pp. 38\u201349. Springer, Berlin (2006)"},{"key":"9626_CR15","doi-asserted-by":"crossref","unstructured":"Dyer, M.E., Goldberg, L.A., Paterson, M.: On counting homomorphisms to directed acyclic graphs. J.\u00a0ACM 54(6) (2007)","DOI":"10.1145\/1314690.1314691"},{"key":"9626_CR16","first-page":"246","volume-title":"Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M.E. Dyer","year":"2000","unstructured":"Dyer, M.E., Greenhill, C.S.: The complexity of counting graph homomorphisms (extended abstract). In: Shmoys, David B. (ed.) Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, January 9\u201311, 2000, pp. 246\u2013255. ACM\/SIAM, New York (2000)"},{"issue":"3","key":"9626_CR17","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1002\/rsa.20036","volume":"25","author":"M.E. Dyer","year":"2004","unstructured":"Dyer, M.E., Greenhill, C.S.: Corrigendum: The complexity of counting graph homomorphisms. Random Struct. Algorithms 25(3), 346\u2013352 (2004)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"9626_CR18","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput. 28(1), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"key":"9626_CR19","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1090\/S0894-0347-06-00529-7","volume":"20","author":"M. Freedman","year":"2007","unstructured":"Freedman, M., Lov\u00e1sz, L., Schrijver, A.: Reflection positivity, rank connectivity, and homomorphism of graphs. J. Am. Math. Soc. 20, 37\u201351 (2007)","journal-title":"J. Am. Math. Soc."},{"issue":"7","key":"9626_CR20","doi-asserted-by":"crossref","first-page":"3336","DOI":"10.1137\/090757496","volume":"39","author":"L.A. Goldberg","year":"2010","unstructured":"Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput. 39(7), 3336\u20133402 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9626_CR21","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of h-coloring. J. Comb. Theory, Ser. B 48(1), 92\u2013110 (1990)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9626_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1007\/978-3-642-02882-3_47","volume-title":"Proceedings of 15th Annual International Conference on Computing and Combinatorics, COCOON 2009","author":"M. Kowalczyk","year":"2009","unstructured":"Kowalczyk, M.: Classification of a class of counting problems using holographic reductions. In: Ngo, Hung Q. (ed.) Proceedings of 15th Annual International Conference on Computing and Combinatorics, COCOON 2009, Niagara Falls, NY, USA, July 13\u201315, 2009. Lecture Notes in Computer Science, vol. 5609, pp. 472\u2013485. Springer, Berlin (2009)"},{"key":"9626_CR23","series-title":"LIPIcs","first-page":"525","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010","author":"M. Kowalczyk","year":"2010","unstructured":"Kowalczyk, M., Cai, J.y.: Holant problems for regular graphs with complex edge functions. In: Marion, J.-Y., Schwentick, T. (eds.) 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, Nancy, France, March 4\u20136, 2010, LIPIcs, vol. 5, pp. 525\u2013536. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Dagstuhl (2010)"},{"key":"9626_CR24","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/FOCS.2006.7","volume-title":"Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006)","author":"L.G. Valiant","year":"2006","unstructured":"Valiant, L.G.: Accidental algorithms. In: Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Berkeley, California, USA, 21\u201324 October 2006, pp. 509\u2013517. IEEE Comput. Soc., Los Alamitos (2006)"},{"issue":"5","key":"9626_CR25","doi-asserted-by":"crossref","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"L.G. Valiant","year":"2008","unstructured":"Valiant, L.G.: Holographic algorithms. SIAM J. Comput. 37(5), 1565\u20131594 (2008)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9626_CR26","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.tcs.2007.05.023","volume":"384","author":"M. Xia","year":"2007","unstructured":"Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci. 384(1), 111\u2013125 (2007)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9626-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9626-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9626-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:09Z","timestamp":1559123109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9626-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,1]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["9626"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9626-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,1]]}}}