Change search
ReferencesLink to record
Permanent link

Direct link
A Dichotomy for Real Weighted Holant Problems
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-1600-5290
2012 (English)In: 2012 IEEE 27th Annual Conference On Computational Complexity (CCC), IEEE , 2012, 96-106 p.Conference paper (Refereed)
Abstract [en]

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as #CSP and Graph Homomorphism. An effective dichotomy for such frameworks can immediately settle the complexity of all combinatorial problems expressible in that framework. Both #CSP and Graph Homomorphism can be viewed as sub-families of Holant with the additional assumption that the equality constraints are always available. Other subfamilies of Holant such as Holant* and Holant(c) problems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, complexity dichotomy for a variety of sub-families of Holant such as #CSP, Graph Homomorphism, Holant* and Holant(c) were proved. The dichotomy for the general Holant framework, which is the most desirable, still remains open. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions. This setting already captures most of the interesting combinatorial problems defined by local constraints, such as (perfect) matching, independent set, vertex cover and so on. This is the first time a dichotomy is obtained for general Holant Problems without any auxiliary functions. One benefit of working with Holant framework is some powerful new reduction techniques such as Holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail, thus this new idea of reduction might also be of independent interest. Besides proving dichotomy and developing new technique, we also obtained some interesting by-products. We prove a dichotomy for #CSP restricting to instances where each variable appears a multiple of d times for any d. We also prove that counting the number of Eulerian-Orientations on 2k-regular graphs is #P-hard for any k >= 2.

Place, publisher, year, edition, pages
IEEE , 2012. 96-106 p.
, IEEE Conference on Computational Complexity. Proceedings, ISSN 1093-0159
Keyword [en]
Holant problem, #CSP, complexity dichotomy, reduction technique
National Category
Computer Science
URN: urn:nbn:se:kth:diva-104718DOI: 10.1109/CCC.2012.16ISI: 000308976600010ScopusID: 2-s2.0-84866508430ISBN: 978-0-7695-4708-4OAI: diva2:566827
27th Annual IEEE Conference on Computational Complexity (CCC), JUN 26-29, 2012, Porto, Portugal

QC 20121109

Available from: 2012-11-09 Created: 2012-11-09 Last updated: 2012-11-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Huang, Sangxia
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 20 hits
ReferencesLink to record
Permanent link

Direct link