Konrad K. Dabrowski

Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak et al.

We show optimal FPT-approximability results for solving almost satisfiable systems of modular linear equations, completing the picture of the parameterized complexity and FPT-approximability landscape for the Min-$r$-Lin$(\mathbb{Z}_m)$ problem for every $r$ and $m$. In Min-$r$-Lin$(\mathbb{Z}_m)$, we are given a system $S$ of linear equations modulo $m$, each on at most $r$ variables, and the goal is to find a subset $Z \subseteq S$ of minimum cardinality such that $S - Z$ is satisfiable. The problem is UGC-hard to approximate within any constant factor for every $r \geq 2$ and $m \geq 2$, which motivates studying it through the lens of parameterized complexity with solution size as the parameter. From previous work (Dabrowski et al. SODA'23/TALG and ESA'25) we know that Min-$r$-Lin$(\mathbb{Z}_m)$ is W[1]-hard to FPT-approximate within any constant factor when $r \geq 3$, and that Min-$2$-Lin$(\mathbb{Z}_m)$ is in FPT when $m$ is prime and W[1]-hard when $m$ has at least two distinct prime factors. The case when $m = p^d$ for some prime $p$ and $d \geq 2$ has remained an open problem. We resolve this problem in this paper and prove the following: (1) We prove that Min-$2$-Lin$(\mathbb{Z}_{p^d})$ is in FPT for every prime $p$ and $d \geq 1$. This implies that Min-$2$-Lin$(\mathbb{Z}_{m})$ can be FPT-approximated within a factor of $ω(m)$, where $ω$ is the number of distinct prime factors of $m$. (2) We show that, under the ETH, Min-$2$-Lin$(\mathbb{Z}_m)$ cannot be FPT-approximated within $ω(m) - ε$ for any $ε> 0$. Our main algorithmic contribution is a new technique coined balanced subgraph covering, which generalizes important balanced subgraphs of Dabrowski et al. (SODA'23/TALG) and shadow removal of Marx and Razgon (STOC'11/SICOMP). For the lower bounds, we develop a framework for proving optimality of FPT-approximation factors under the ETH.

Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak et al.

The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau [J. Comput. System. Sci. 79(1), 2013] and Huang et al. [Artif. Intell. 195, 2013] proved that CSP$(Γ)$ can be solved in $n^{f(w)}$ time (where $n$ is the size of the instance, $w$ is the treewidth of the primal graph and $f$ is a computable function) for certain classes of constraint languages $Γ$. We improve this bound to $f(w) \cdot n^{O(1)}$, where the function $f$ only depends on the language $Γ$, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmau's algorithm but not by ours, and we begin investigating ways of generalising our results to larger families of languages. We also analyse our algorithm with respect to its running time and show that it is optimal (under the Exponential Time Hypothesis) for certain languages such as Allen's Interval Algebra.