Holant problems and counting CSP

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Holant problems and counting CSP

Full text

Pdf (570 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 41st annual ACM symposium on Theory of computing table of contents

Bethesda, MD, USA

SESSION: Complexity III table of contents

Pages 715-724

Year of Publication: 2009

ISBN:978-1-60558-506-2

Authors

Jin-Yi Cai	University of Wisconsin, Madison, WI, USA
Pinyan Lu	Microsoft Research Asia, Beijing, China
Mingji Xia	University of Wisconsin, Madison, WI, USA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 27, Downloads (12 Months): 114, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1536414.1536511 What is a DOI?

ABSTRACT

We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant Problems. Compared to counting Constrained Satisfaction Problems (CSP), it is a refinement with a more explicit role for the function constraints. Both graph homomorphism and CSP can be viewed as special cases of Holant Problems. We prove complexity dichotomy theorems in this framework. Because the framework is more stringent, previous dichotomy theorems for CSP problems no longer apply. Indeed, we discover surprising tractable subclasses of counting problems, which could not have been easily specified in the CSP framework. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations. The study of Holant Problems led us to discover and prove a complexity dichotomy theorem for the most general form of Boolean CSP where every constraint function takes values in the complex number field {C}.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Andrei A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a 3-element set, Journal of the ACM (JACM), v.53 n.1, p.66-120, January 2006 [doi>10.1145/1120582.1120584]
	2	Andrei A. Bulatov, The Complexity of the Counting Constraint Satisfaction Problem, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_53]
	3	Andrei A. Bulatov , Víctor Dalmau, Towards a dichotomy theorem for the counting constraint satisfaction problem, Information and Computation, v.205 n.5, p.651-678, May, 2007 [doi>10.1016/j.ic.2006.09.005]
	4	Andrei A. Bulatov and Martin Grohe. The complexity of partition functions. In ICALP, volume 3142 of Lecture Notes in Computer Science, pages 294--306. Springer, 2004.
	5	Andrei Bulatov , Martin Grohe, The complexity of partition functions, Theoretical Computer Science, v.348 n.2, p.148-186, 8 December 2005 [doi>10.1016/j.tcs.2005.09.011]
	6	Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem. manuscript, 2009.
	7	Jin-Yi Cai , Pinyan Lu, Holographic algorithms: from art to science, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250850]
	8	Jin-Yi Cai and Pinyan Lu. On symmetric signatures in holographic algorithms. In STACS, volume 4393 of Lecture Notes in Computer Science, pages 429--440. Springer, 2007.
	9	Jin-Yi Cai , Pinyan Lu , Mingji Xia, Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.644-653, October 25-28, 2008 [doi>10.1109/FOCS.2008.34]
	10	Nadia Creignou , Sanjeev Khanna , Madhu Sudan, Complexity classifications of boolean constraint satisfaction problems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
	11	Paul Dagum , Michael Luby, Approximating the permanent of graphs with large factors, Theoretical Computer Science, v.102 n.2, p.283-305, 10 Aug. 1992 [doi>10.1016/0304-3975(92)90234-7]
	12	C. T. J. Dodson and T. Poston. Tensor Geometry. Graduate Texts in Mathematics 130. Springer-Verlag, New York, 1991.
	13	Martin E. Dyer, Leslie Ann Goldberg, and Mark Jerrum. The complexity of weighted boolean CSP. CoRR, abs/0704.3683, 2007.
	14	Martin E. Dyer, Leslie Ann Goldberg, and Mike Paterson. On counting homomorphisms to directed acyclic graphs. In ICALP (1), volume 4051 of Lecture Notes in Computer Science, pages 38--49. Springer, 2006.
	15	Martin Dyer , Leslie Ann Goldberg , Mike Paterson, On counting homomorphisms to directed acyclic graphs, Journal of the ACM (JACM), v.54 n.6, p.27-es, December 2007 [doi>10.1145/1314690.1314691]
	16	Martin Dyer , Catherine Greenhill, The complexity of counting graph homomorphisms (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.246-255, January 09-11, 2000, San Francisco, California, United States
	17	Martin Dyer , Catherine Greenhill, Corrigendum: the complexity of counting graph homomorphisms, Random Structures & Algorithms, v.25 n.3, p.346-352, October 2004 [doi>10.1002/rsa.20036]
	18	Tomás Feder , Moshe Y. Vardi, The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory, SIAM Journal on Computing, v.28 n.1, p.57-104, Feb. 1999 [doi>10.1137/S0097539794266766]
	19	M. Freedman, L. Lovász, and A. Schrijver. Reflection positivity, rank connectivity, and homomorphism of graphs. J. AMS, 20:37--51, 2007.
	20	Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs. CoRR, abs/0804.1932, 2008.
	21	Pavol Hell , Jaroslav Nešetřil, On the complexity of H-coloring, Journal of Combinatorial Theory Series B, v.48 n.1, p.92-110, Feb. 1990 [doi>10.1016/0095-8956(90)90132-J]
	22	P. W. Kasteleyn. The statistics of dimers on a lattice. Physica, 27:1209--1225, 1961.
	23	P. W. Kasteleyn. Graph theory and crystal physics. In Graph Theory and Theoretical Physics, pages 43--110. Academic Press, London, 1967.
	24	H. N. V. Temperley and M. E. Fisher. Dimer problem in statistical mechanics -- an exact result. Philosophical Magazine, 6:1061--1063, 1961.
	25	Salil P. Vadhan, The Complexity of Counting in Sparse, Regular, and Planar Graphs, SIAM Journal on Computing, v.31 n.2, p.398-427, 2001 [doi>10.1137/S0097539797321602]
	26	Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410--421, 1979.
	27	Leslie G. Valiant, Holographic Algorithms (Extended Abstract), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.306-315, October 17-19, 2004 [doi>10.1109/FOCS.2004.34]
	28	Leslie G. Valiant, Accidental Algorthims, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.509-517, October 21-24, 2006 [doi>10.1109/FOCS.2006.7]
	29	Mingji Xia, Peng Zhang, and Wenbo Zhao. Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci., 384(1):111--125, 2007.