文章基本信息

标题：Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction
本地全文：下载
作者：Marvin K{"u}nnemann ; D{'a}niel Marx
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：169
页码：27:1-27:28
DOI：10.4230/LIPIcs.CCC.2020.27
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：To study the question under which circumstances small solutions can be found faster than by exhaustive search (and by how much), we study the fine-grained complexity of Boolean constraint satisfaction with size constraint exactly k. More precisely, we aim to determine, for any finite constraint family, the optimal running time f(k)n^g(k) required to find satisfying assignments that set precisely k of the n variables to 1. Under central hardness assumptions on detecting cliques in graphs and 3-uniform hypergraphs, we give an almost tight characterization of g(k) into four regimes: 1) Brute force is essentially best-possible, i.e., g(k) = (1 Â± o(1))k, 2) the best algorithms are as fast as current k-clique algorithms, i.e., g(k) = (Ï/3 Â± o(1))k, 3) the exponent has sublinear dependence on k with g(k) â^^ [Î©(â^>k), O(â^Sk)], or 4) the problem is fixed-parameter tractable, i.e., g(k) = O(1). This yields a more fine-grained perspective than a previous FPT/W[1]-hardness dichotomy (Marx, Computational Complexity 2005). Our most interesting technical contribution is a f(k)n^(4â^Sk)-time algorithm for SubsetSum with precedence constraints parameterized by the target k - particularly the approach, based on generalizing a bound on the Frobenius coin problem to a setting with precedence constraints, might be of independent interest.
关键词：Fine-grained complexity theory; algorithmic classification theorem; multivariate algorithms and complexity; constraint satisfaction problems; satisfiability