Article ID Journal Published Year Pages File Type
437423 Theoretical Computer Science 2016 12 Pages PDF
Abstract

We investigate the computational complexity of the problem of counting the locally maximal satisfying assignments of a Constraint Satisfaction Problem (CSP) over the Boolean domain {0,1}{0,1}. A satisfying assignment is locally maximal   if any new assignment which is obtained from it by changing a 0 to a 1 is unsatisfying. For each constraint language Γ, #LocalMaxCSP(Γ)#LocalMaxCSP(Γ) denotes the problem of counting the locally maximal satisfying assignments, given an input CSP with constraints in Γ. We give a complexity dichotomy for the problem of exactly counting the locally maximal satisfying assignments and a complexity trichotomy for the problem of approximately   counting them. Relative to the problem #CSP(Γ)#CSP(Γ), which is the problem of counting all satisfying assignments, the locally maximal version can sometimes be easier but never harder. This finding contrasts with the recent discovery that approximately counting locally maximal independent sets in a bipartite graph is harder (under the usual complexity-theoretic assumptions) than counting all independent sets.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,