Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912123717681152 |
|---|---|
| author | Dabrowski, Konrad K. Jonsson, Peter Ordyniak, Sebastian Osipov, George Wahlström, Magnus |
| author_facet | Dabrowski, Konrad K. Jonsson, Peter Ordyniak, Sebastian Osipov, George Wahlström, Magnus |
| contents | We consider the MIN-r-LIN(R) problem: given a system S of length-r linear equations over a ring R, find a subset of equations Z of minimum cardinality such that S-Z is satisfiable. The problem is NP-hard and UGC-hard to approximate within any constant even when r=|R|=2, so we focus on parameterized approximability with solution size as the parameter. For a large class of infinite rings R called Euclidean domains, Dabrowski et al. [SODA-2023] obtained an FPT-algorithm for MIN-2-LIN(R) using an LP-based approach based on work by Wahlström [SODA-2017]. Here, we consider MIN-r-LIN(R) for finite commutative rings R, initiating a line of research with the ultimate goal of proving dichotomy theorems that separate problems that are FPT-approximable within a constant from those that are not. A major motivation is that our project is a promising step for more ambitious classification projects concerning finite-domain MinCSP and VCSP.
Dabrowski et al.'s algorithm is limited to rings without zero divisors, which are only fields among finite commutative rings. Handling zero divisors seems to be an insurmountable obstacle for the LP-based approach. In response, we develop a constant-factor FPT-approximation algorithm for a large class of finite commutative rings, called Bergen rings, and thus prove approximability for chain rings, principal ideal rings, and Z_m for all m>1. We complement the algorithmic result with powerful lower bounds. For r>2, we show that the problem is not FPT-approximable within any constant (unless FPT=W[1]). We identify the class of non-Helly rings for which MIN-2-LIN(R) is not FPT-approximable. Under ETH, we also rule out (2-e)-approximation for every e>0 for non-lineal rings, which includes e.g. rings Z_{pq} where p and q are distinct primes. Towards closing the gaps between upper and lower bounds, we lay the foundation of a geometric approach for analysing rings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_09932 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings Dabrowski, Konrad K. Jonsson, Peter Ordyniak, Sebastian Osipov, George Wahlström, Magnus Data Structures and Algorithms F.2.2; G.2 We consider the MIN-r-LIN(R) problem: given a system S of length-r linear equations over a ring R, find a subset of equations Z of minimum cardinality such that S-Z is satisfiable. The problem is NP-hard and UGC-hard to approximate within any constant even when r=|R|=2, so we focus on parameterized approximability with solution size as the parameter. For a large class of infinite rings R called Euclidean domains, Dabrowski et al. [SODA-2023] obtained an FPT-algorithm for MIN-2-LIN(R) using an LP-based approach based on work by Wahlström [SODA-2017]. Here, we consider MIN-r-LIN(R) for finite commutative rings R, initiating a line of research with the ultimate goal of proving dichotomy theorems that separate problems that are FPT-approximable within a constant from those that are not. A major motivation is that our project is a promising step for more ambitious classification projects concerning finite-domain MinCSP and VCSP. Dabrowski et al.'s algorithm is limited to rings without zero divisors, which are only fields among finite commutative rings. Handling zero divisors seems to be an insurmountable obstacle for the LP-based approach. In response, we develop a constant-factor FPT-approximation algorithm for a large class of finite commutative rings, called Bergen rings, and thus prove approximability for chain rings, principal ideal rings, and Z_m for all m>1. We complement the algorithmic result with powerful lower bounds. For r>2, we show that the problem is not FPT-approximable within any constant (unless FPT=W[1]). We identify the class of non-Helly rings for which MIN-2-LIN(R) is not FPT-approximable. Under ETH, we also rule out (2-e)-approximation for every e>0 for non-lineal rings, which includes e.g. rings Z_{pq} where p and q are distinct primes. Towards closing the gaps between upper and lower bounds, we lay the foundation of a geometric approach for analysing rings. |
| title | Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings |
| topic | Data Structures and Algorithms F.2.2; G.2 |
| url | https://arxiv.org/abs/2410.09932 |