NDLI: A Complexity Dichotomy For Hypergraph Partition Functions

Content Provider	Springer Nature Link
Author	Dyer, Martin Goldberg, Leslie Ann Jerrum, Mark
Copyright Year	2010
Abstract	We consider the complexity of counting homomorphisms from an r-uniform hypergraph G to a symmetric r-ary relation H. We give a dichotomy theorem for r > 2, showing for which H this problem is in FP and for which H it is #P-complete. This generalizes a theorem of Dyer and Greenhill (2000) for the case r = 2, which corresponds to counting graph homomorphisms. Our dichotomy theorem extends to the case in which the relation H is weighted, and the goal is to compute the partition function, which is the sum of weights of the homomorphisms. This problem is motivated by statistical physics, where it arises as computing the partition function for particle models in which certain combinations of r sites interact symmetrically. In the weighted case, our dichotomy theorem generalizes a result of Bulatov and Grohe (2005) for graphs, where r = 2. When r = 2, the polynomial time cases of the dichotomy correspond simply to rank-1 weights. Surprisingly, for all r > 2 the polynomial time cases of the dichotomy have rather more structure. It turns out that the weights must be superimposed on a combinatorial structure defined by solutions of an equation over an Abelian group. Our result also gives a dichotomy for a closely related constraint satisfaction problem.
Starting Page	605
Ending Page	633
Page Count	29
File Format	PDF
ISSN	10163328
Journal	Computational complexity
Volume Number	19
Issue Number	4
e-ISSN	14208954
Language	English
Publisher	Birkhäuser-Verlag
Publisher Date	2010-12-06
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Dichotomy hypergraph partition functions Algorithm Analysis and Problem Complexity Computational Mathematics and Numerical Analysis
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Dichotomy for Real Weighted Holant Problems

Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

Halfspace Matrices

Every Linear Threshold Function has a Low-Weight Approximator

2-Local Random Reductions to 3-Valued Functions

Circuits on cylinders

Communication vs. Computation

A complexity dichotomy for hypergraph partition functions

Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

A Complexity Dichotomy For Hypergraph Partition Functions

Similar Documents

A Dichotomy for Real Weighted Holant Problems

Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

Halfspace Matrices

Every Linear Threshold Function has a Low-Weight Approximator

2-Local Random Reductions to 3-Valued Functions

Circuits on cylinders

Communication vs. Computation

A complexity dichotomy for hypergraph partition functions

Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

A Complexity Dichotomy For Hypergraph Partition Functions