The complexity of counting locally maximal satisfying assignments of Boolean CSPs

Journal article

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}. 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(Γ) 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(Γ), 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.

Authors: Goldberg, L; Jerrum, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Theoretical Computer Science
• Volume: 634
• Pages: 35-46
• Publication date: 2016-04-11
• Acceptance date: 2016-04-05
• DOI: 10.1016/j.tcs.2016.04.008
• ISSN: 0304-3975
• Keywords: approximate computation; constraint satisfaction problem; computational complexity of counting problems