The algebraic structure of the densification and the sparsification tasks for CSPs
Takhanov R.
March 2023Springer
Constraints
2023#28Issue 113 - 44 pp.
The tractability of certain CSPs for dense or sparse instances is known from the 90s. Recently, the densification and the sparsification of CSPs were formulated as computational tasks and the systematical study of their computational complexity was initiated. We approach this problem by introducing the densification operator, i.e. the closure operator that, given an instance of a CSP, outputs all constraints that are satisfied by all of its solutions. According to the Galois theory of closure operators, any such operator is related to a certain implicational system (or, a functional dependency) Σ. We are specifically interested in those classes of fixed-template CSPs, parameterized by constraint languages Γ, for which there is an implicational system Σ whose size is a polynomial in the number of variables n. We show that in the Boolean case, such implicational systems exist if and only if Γ is of bounded width. For such languages, Σ can be computed in log-space or in a logarithmic time with a polynomial number of processors. Given an implicational system Σ, the densification task is equivalent to the computation of the closure of input constraints. The sparsification task is equivalent to the computation of the minimal key.
Bounded width , Datalog , Densification of CSP , Horn formula minimization , Implicational system , Polynomial densification operator , Sparsification of CSP
Text of the article Перейти на текст статьи
Nazarbayev University, School of Sciences and Humanities, Mathematics Department, 53 Kabanbay Batyr Ave, Nur-Sultan, 010000, Kazakhstan
Nazarbayev University
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026