Best-Case and Worst-Case Sparsifiability of Boolean CSPs
Tóm tắt
We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, such that a bound on the number of resulting constraints can be given in terms of the number of variables n. We investigate how the worst-case sparsification size depends on the types of constraints allowed in the problem formulation—the constraint language—and identify constraint languages giving the best-possible and worst-possible behavior for worst-case sparsifiability. Two algorithmic results are presented. The first result essentially shows that for any arity k, the only constraint type for which no nontrivial sparsification is possible has exactly one falsifying assignment, and corresponds to logical OR (up to negations). Our second result concerns linear sparsification, that is, a reduction to an equivalent instance with
$$O(n)$$
constraints. Using linear algebra over rings of integers modulo prime powers, we give an elegant necessary and sufficient condition for a constraint type to be captured by a degree-1 polynomial over such a ring, which yields linear sparsifications. The combination of these algorithmic results allows us to prove two characterizations that capture the optimal sparsification sizes for a range of Boolean CSPs. For NP-complete Boolean CSPs whose constraints are symmetric (the satisfaction depends only on the number of 1 values in the assignment, not on their positions), we give a complete characterization of which constraint languages allow for a linear sparsification. For Boolean CSPs in which every constraint has arity at most three, we characterize the optimal size of sparsifications in terms of the largest OR that can be expressed by the constraint language.
Tài liệu tham khảo
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277–305 (2014). https://doi.org/10.1137/120880240
Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011). https://doi.org/10.1016/j.tcs.2011.04.039
Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720–742 (2005). https://doi.org/10.1137/S0097539700376676
Chen, H.A.: A rendezvous of logic, complexity, and algebra. ACM Comput. Surv. (2009). https://doi.org/10.1145/1189056.1189076
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). https://doi.org/10.1007/978-3-319-21275-3
Dell, H., Marx, D.: Kernelization of packing problems. In: Proceedings of 23rd SODA, pp. 68–81 (2012). https://doi.org/10.1137/1.9781611973099.6
Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1–23:27 (2014). https://doi.org/10.1145/2629620
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlim (2013). https://doi.org/10.1007/978-1-4471-5559-1
Drucker, A.: New limits to classical and quantum instance compression. SIAM J. Comput. 44(5), 1443–1479 (2015). https://doi.org/10.1137/130927115
Gockenbach, M.: Finite-Dimensional Linear Algebra. Discrete Mathematics and Its Applications. Taylor & Francis, Abingdon (2011)
Jansen, B.M.P.: On sparsification for computing treewidth. Algorithmica 71(3), 605–635 (2015). https://doi.org/10.1007/s00453-014-9924-2
Jansen, B.M.P., Pieterse, A.: Optimal sparsification for some binary CSPs using low-degree polynomials. In: Proceedings of 41st MFCS, pp. 71:1–71:14 (2016). https://doi.org/10.4230/LIPIcs.MFCS.2016.71
Jansen, B.M.P., Pieterse, A.: Optimal data reduction for graph coloring using low-degree polynomials. In: Proceedings of 12th IPEC, pp. 22:1–22:12 (2017). https://doi.org/10.4230/LIPIcs.IPEC.2017.22
Jansen, B.M.P., Pieterse, A.: Sparsification upper and lower bounds for graph problems and not-all-equal SAT. Algorithmica 79(1), 3–28 (2017). https://doi.org/10.1007/s00453-016-0189-9
Jansen, B.M.P., Pieterse, A.: Optimal sparsification for some binary CSPs using low-degree polynomials. CoRR abs/1606.03233 (2018). arXiv:1606.03233v2
Kannan, R., Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput. 8(4), 499–507 (1979). https://doi.org/10.1137/0208040
Kratsch, S., Philip, G., Ray, S.: Point line cover: the easy kernel is essentially tight. ACM Trans. Algorithms 12(3), 40:1–40:16 (2016). https://doi.org/10.1145/2832912
Lagerkvist, V.: Weak bases of Boolean co-clones. Inf. Process. Lett. 114(9), 462–468 (2014). https://doi.org/10.1016/j.ipl.2014.03.011
Lagerkvist, V., Wahlström, M.: Kernelization of constraint satisfaction problems: a study through universal algebra. In: Proceedings of 23rd CP, pp. 157–171 (2017). https://doi.org/10.1007/978-3-319-66158-2_11
Lagerkvist, V., Wahlström, M.: Kernelization of constraint satisfaction problems: a study through universal algebra. CoRR abs/1706.05941 (2017). arXiv:1706.05941
Lagerkvist, V., Wahlström, M.: Which NP-hard SAT and CSP problems admit exponentially improved algorithms? CoRR abs/1801.09488 (2018). arXiv:1801.09488v1
Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization—preprocessing with a guarantee. In: The Multivariate Algorithmic Revolution and Beyond, pp. 129–161 (2012). https://doi.org/10.1007/978-3-642-30891-8_10
Lovász, L.: Chromatic number of hypergraphs and linear algebra. In: Studia Scientiarum Mathematicarum Hungarica 11, pp. 113–114 (1976). http://real-j.mtak.hu/5461/
Nordh, G., Zanuttini, B.: Frozen Boolean partial co-clones. In: Proceedings of 39th International Symposium on Multiple-Valued Logic, pp. 120–125. IEEE Computer Society (2009). https://doi.org/10.1109/ISMVL.2009.10
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of 10th STOC, pp. 216–226 (1978). https://doi.org/10.1145/800133.804350