Bulatov, Andrei A. ;
Dyer, Martin ;
Goldberg, Leslie Ann ;
Jerrum, Mark
Logsupermodular functions, functional clones and counting CSPs
Abstract
Motivated by a desire to understand the computational complexity of counting constraint satisfaction problems (counting CSPs), particularly the complexity of approximation, we study functional clones of functions on the Boolean domain, which are analogous to the familiar relational clones constituting Post's lattice. One of these clones is the collection of logsupermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In our study, we assume that nonnegative unary functions (weights) are available. Given this, we prove that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial nonlsm function is computationally as hard as any problem in #P. Furthermore, any nontrivial functional clone (in a sense that will be made precise below) contains the binary function "implies". As a consequence, all nontrivial counting CSPs (with nonnegative unary weights assumed to be available) are computationally at least as difficult as #BIS, the problem of counting independent sets in a bipartite graph. There is empirical evidence that #BIS is hard to solve, even approximately.
BibTeX  Entry
@InProceedings{bulatov_et_al:LIPIcs:2012:3407,
author = {Andrei A. Bulatov and Martin Dyer and Leslie Ann Goldberg and Mark Jerrum},
title = {{Logsupermodular functions, functional clones and counting CSPs}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {302313},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3407},
URN = {urn:nbn:de:0030drops34078},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2012.302},
annote = {Keywords: counting constraint satisfaction problems, approximation, complexity}
}
Keywords: 

counting constraint satisfaction problems, approximation, complexity 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

24.02.2012 