Approximate counting CSP seen from the other side
作者： Stanislav Zivny , Andrei A. Bulatov
DOI: 10.1145/3389390
关键词:
摘要: In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) form #CSP($\mathcal{C}$,-), in which goal is, given a relational structure $\mathbf{A}$ from class $\mathcal{C}$ structures and an arbitrary $\mathbf{B}$, to find number homomorphisms $\mathbf{B}$. Flum Grohe showed that #CSP($\mathcal{C}$,-) is solvable polynomial time if has bounded treewidth [FOCS'02]. Building on work [JACM'07] decision CSPs, Dalmau Jonsson then that, recursively enumerable arity, assuming FPT $\neq$ #W[1], there are no other cases exactly (or even fixed-parameter time) [TCS'04]. We show W[1] (under randomised parametrised reductions) for satisfying certain general conditions, not approximately unbounded treewidth; fixed parameter tractable (and thus also fully polynomial) approximation scheme #CSP($\mathcal{C}$,-). particular, our condition generalises case when closed under taking minors.
arxiv.org
sci-hub.st 参考文章(42)
J. Flum, M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series) ,(2006)
Tommy Färnqvist, Exploiting Structure in CSP-related Problems Linköping University Electronic Press. ,(2013)
Tomás Feder, Pavol Hell, Wing Xie, Matrix Partitions with Finitely Many Obstructions Electronic Journal of Combinatorics. ,vol. 14, pp. 58- ,(2007) , 10.37236/976
V. Arvind, Venkatesh Raman, Approximation Algorithms for Some Parameterized Counting Problems Algorithms and Computation. pp. 453- 464 ,(2002) , 10.1007/3-540-36136-7_40
Mark Jerrum, Leslie Ann Goldberg, Andreas Galanis, Approximately Counting H-Colourings is #BIS-Hard arXiv: Computational Complexity. ,(2015) , 10.1137/15M1020551
Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby, The complexity of approximating conservative counting CSPs Journal of Computer and System Sciences. ,vol. 81, pp. 311- 329 ,(2015) , 10.1016/J.JCSS.2014.06.006
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, An approximation trichotomy for Boolean #CSP Journal of Computer and System Sciences. ,vol. 76, pp. 267- 277 ,(2010) , 10.1016/J.JCSS.2009.08.003
Martin Dyer, David Richerby, An Effective Dichotomy for the Counting Constraint Satisfaction Problem SIAM Journal on Computing. ,vol. 42, pp. 1245- 1274 ,(2013) , 10.1137/100811258
Pavol Hell, Jiří Sgall, Daniel Král, Tomás Feder, Two algorithms for general list matrix partitions symposium on discrete algorithms. pp. 870- 876 ,(2005) , 10.5555/1070432.1070554
Rodney G. Downey, Michael R. Fellows, Kenneth W. Regan, Parameterized circuit complexity and the W hierarchy Theoretical Computer Science. ,vol. 191, pp. 97- 115 ,(1998) , 10.1016/S0304-3975(96)00317-9