pith. machine review for the scientific record. sign in

arxiv: 2604.10369 · v1 · submitted 2026-04-11 · 💻 cs.DS

Optimal FPT-Approximability for Modular Linear Equations

Konrad K. Dabrowski , Peter Jonsson , Sebastian Ordyniak , George Osipov , Magnus Wahlstr\"om This is my paper

Pith reviewed 2026-05-10 15:00 UTC · model grok-4.3

classification 💻 cs.DS
keywords FPT approximationmodular linear equationsparameterized complexityexponential time hypothesisprime powergraph covering
0
0 comments X

The pith

Min-2-Lin(Z_m) admits an FPT approximation within factor ω(m) that is tight under the ETH

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper resolves the remaining open case for two-variable modular linear equations by proving that the minimum deletion problem is fixed-parameter tractable when the modulus is any prime power p^d. This immediately yields an FPT-time approximation algorithm for arbitrary modulus m whose ratio equals the number of distinct prime factors of m. A matching conditional lower bound shows that, assuming the exponential time hypothesis, no FPT algorithm can achieve any strictly smaller approximation factor. The results together complete the parameterized approximability classification for the entire Min-r-Lin(Z_m) family.

Core claim

We prove that Min-2-Lin(Z_{p^d}) is in FPT for every prime p and d ≥ 1. This implies that Min-2-Lin(Z_m) can be FPT-approximated within a factor of ω(m), where ω is the number of distinct prime factors of m. We show that, under the ETH, Min-2-Lin(Z_m) cannot be FPT-approximated within ω(m) - ε for any ε > 0. The main algorithmic contribution is a new technique called balanced subgraph covering.

What carries the argument

balanced subgraph covering, a generalization of prior balanced-subgraph and shadow-removal methods that reduces the prime-power case to tractable subproblems by covering the equation graph while preserving balance conditions

Load-bearing premise

The FPT upper bound holds only if the balanced subgraph covering procedure can be executed in f(k) n^c time and correctly produces a small set of deletable equations.

What would settle it

A family of Min-2-Lin(Z_{p^2}) instances with deletion parameter k for which every algorithm requires n^ω(1) time even when k is fixed, or an FPT algorithm that approximates Min-2-Lin(Z_m) within ratio ω(m) - 1 for some composite m.

Figures

Figures reproduced from arXiv: 2604.10369 by George Osipov, Konrad K. Dabrowski, Magnus Wahlstr\"om, Peter Jonsson, Sebastian Ordyniak.

Figure 1
Figure 1. Figure 1: An illustration of an instance of Min-2-Lin(Z4) on the left and a solution on the right. The nodes represent the variables of the instance. Every edge xy is an equation of the form 3x = y mod 4 on its endpoints. A node v coloured black is equipped with an equation 2v = 2 mod 4. On the right, the red dashed edges and the red node show the equations deleted by the solution; the orange region encloses the set… view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of two instance of Min-2-Lin(Z8) with common equations s = 1, 2s = w, 2u1 = 2, 2u2 = 2, v1 = 2u1, v2 = 2u1 and v1 = 7v2. The one on the left additionally has an equation u1 = 5u2 and the one on the right has u1 = 3u2. Note that the equations u = av and au = v are equivalent for a ∈ {1, 3, 5, 7}, so we depict them as undirected edges. The first instance is unsatisfiable, while the second one… view at source ↗
Figure 3
Figure 3. Figure 3: An illustration for the reduction from Multicoloured Subgraph Isomorphism to Paired Min Cut. The graph represents a choice gadget for a vertex a in H. The gadget consists of segments, each representing a possible image of a vertex from H in the graph G. Each segment is a union of |E(H)| (which is 5 in the illustration) internally disjoint paths between a pair of vertices. A cut corresponding to choosing u … view at source ↗
Figure 4
Figure 4. Figure 4: Note that a theta graph contains three cycles, each formed by the union of two out of the [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 4
Figure 4. Figure 4: The structure of a theta graph. depend on the starting point or direction of traversal of C, and so is a well-defined notion. We have the following result. Lemma 7. Let G be a graph with edges labelled by elements of a finite group Γ. Let B be the set of identity cycles in G. Then (G, B) is a biased graph and B has a polynomial-time membership oracle. Proof. Zaslavsky [Zas89, Proposition 5.1] has proven th… view at source ↗
Figure 5
Figure 5. Figure 5: Algorithm for computing balanced subgraph covers We argue that we can dispose of balanced connected components of G. If G contains some connected component K that is balanced, note that for every v ∈ K we have Xv = {K} with cleaning set FK = ∅. Thus F contains no edge of K, and K ⊆ S by design. Now let H be a balanced subgraph of G, let G′ be the union of unbalanced components of G, and let H′ = H[V (G′ )]… view at source ↗
Figure 6
Figure 6. Figure 6: 4.1 Reduction to Special Instances An instance of Min-2-Lin(R) is simple if all binary equations are of the form a · u = v and all unary equations are crisp and of the form v = b for some a, b ∈ R. By using iterative compression, homogenization and branching in FPT time, Dabrowski et al. have shown the following. Proposition 18 (See Lemma 5 in [DJO+25b]). If Min-2-Lin(Zp d ) restricted to simple instances … view at source ↗
Figure 6
Figure 6. Figure 6: Algorithm for Min-2-Lin(Zpd ) on simple instances. We conclude the proof by verifying that the algorithm runs in FPT time. Step 1. Transforming the input (I, k) into special form takes polynomial time (by Section 4.1) since we assume that I is a simple instance. Step 2. Computing IB takes polynomial time by Section 4.2. Step 3. The dominant factor comes from procedure RandomCover. It runs in O∗ (42k ) time… view at source ↗
Figure 7
Figure 7. Figure 7: Reduction chain in hardness proof sparse version of the Gapε Max-2-CSP problem1 , and the non-approximability of this problem follows from Theorem 4.1 of [GLR+24a] combined with a result concerning parallel repetition in projection games [Rao11]. They use a straightforward probabilistic argument for showing that the same non-approximability result holds for instances with bipartite primal graphs, and this … view at source ↗
Figure 8
Figure 8. Figure 8: An illustration of the parts Ui and Uj of H and the parts Vi,1, . . . , Vi,k and Vj,1, . . . , Vj,k of G and their relation with respect to the homomorphism χ from G to H, which is represented by directed edges, for an instance of Gapε Ht-MSI. 2. We construct the homomorphism χ : G → H as follows. Consider the homomorphism λ from G′ to H′ . Recall that G is the disjoint union of t copies of G′ while H is t… view at source ↗
Figure 9
Figure 9. Figure 9: System of equations obtained from a tuple of edges {u1v1, . . . , u4v4} ∈ P. Red equations are crisp and the green equation is soft. Edges are illustrated by dashed lines. definition, the only soft equations in S are the gadget equations xB = yB for bundles B ∈ B. Define Y ′ = S {t | (xt = yt) ∈ Y } and note that Y ′ intersects exactly |Y | tuples in B. We claim that Y ′ is an st-cut in G. Suppose, with th… view at source ↗
read the original abstract

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 $\omega(m)$, where $\omega$ 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 $\omega(m) - \epsilon$ for any $\epsilon > 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper resolves the remaining open case for Min-2-Lin(Z_m) by proving that Min-2-Lin(Z_{p^d}) is FPT for every prime p and d ≥ 1. This yields an FPT-approximation algorithm for general m with factor ω(m). Under the ETH it shows a matching lower bound: no FPT-approximation within ω(m) − ε exists for any ε > 0. The central algorithmic contribution is a new balanced-subgraph-covering technique that generalizes the balanced-subgraph and shadow-removal methods of prior work; the ETH lower-bound framework reduces from a known tight ETH-hard problem while preserving the exact gap.

Significance. If the results hold, the manuscript completes the FPT-approximability landscape for Min-r-Lin(Z_m) when r = 2, closing the gap between the prime-modulus FPT result and the multiple-prime W[1]-hardness result. The balanced-subgraph-covering technique maintains an FPT-bounded search tree whose size depends only on the solution size k (independent of p and d) and may be reusable for other p-adic or modular problems. The ETH optimality framework is a methodological strength that directly produces tight approximation factors rather than merely constant-factor gaps.

minor comments (3)
  1. [§1] §1, paragraph 3: the sentence claiming that the new technique 'generalizes important balanced subgraphs of Dabrowski et al. and shadow removal of Marx and Razgon' would benefit from a one-sentence pointer to the precise technical difference (e.g., how the p-adic lifting avoids the dependence on d that appeared in earlier attempts).
  2. [§5] §5, Theorem 5.1: the ETH reduction is stated to preserve the exact ω(m) gap; a short remark confirming that no hidden polynomial factor in m enters the parameter would make the optimality claim immediately verifiable from the statement alone.
  3. Figure 2 (or the corresponding running-time plot): the y-axis label 'search-tree size' should explicitly note that the plotted quantity is independent of p and d, as this is the key FPT property.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment, accurate summary of our results, and recommendation to accept the manuscript. The report correctly identifies the resolution of the remaining open case for Min-2-Lin(Z_{p^d}) and the resulting optimal FPT-approximability for general m.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central algorithmic result for Min-2-Lin(Z_{p^d}) rests on a newly introduced balanced subgraph covering technique that generalizes (but does not reduce to) prior balanced-subgraph and shadow-removal ideas from the authors' own earlier work. Self-citations to Dabrowski et al. (SODA'23/TALG and ESA'25) are used only to establish the known landscape for other m, while the new FPT membership and the ETH-based lower bound for the ω(m) factor are derived independently via the fresh technique and an external hypothesis. No equations or definitions in the provided text reduce the claimed approximation factor or FPT status to quantities fitted or defined inside the present paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the standard ETH assumption for the conditional lower bound and introduces a new algorithmic technique whose internal details are not visible in the abstract.

axioms (1)
  • domain assumption Exponential Time Hypothesis (ETH)
    Invoked to establish that no FPT algorithm can achieve an approximation factor better than ω(m) - ε.

pith-pipeline@v0.9.0 · 5801 in / 1360 out tokens · 64074 ms · 2026-05-10T15:00:02.019676+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two

    cs.DS 2026-04 unverdicted novelty 7.0

    A new coordinatewise balanced covering theorem for linear gain graphs yields a randomized algorithm for Coset-List Min-2-Lin over powers of two with runtime exponential in k squared times the cycle-label rank rho.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · cited by 1 Pith paper

  1. [1]

    Complexity of local search for CSPs parameterized by constraint difference

    [ACd+25] Aditya Anand, Vincent Cohen-Addad, Tommaso d’Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi, and Sijin Peng. Complexity of local search for CSPs parameterized by constraint difference. InProc. 20th International Symposium on Parameterized and Exact Computation (IPEC-2025),

    work page 2025

  2. [2]

    [AV05] Vikraman Arvind and T. C. Vijayaraghavan. The complexity of solving linear equations over a finite ring. InProc. 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS-2005), pages 472–484,

    work page 2005

  3. [3]

    Fixed-parameter approx- imability of boolean MinCSPs.arXiv preprint arXiv:1601.04935,

    [BELM16] ´Edouard Bonnet, L´ aszl´ o Egri, Bingkai Lin, and D´ aniel Marx. Fixed-parameter approx- imability of boolean MinCSPs.arXiv preprint arXiv:1601.04935,

    work page arXiv

  4. [4]

    Fixed-parameter approximability of Boolean MinCSPs

    [BEM16] ´Edouard Bonnet, L´ aszl´ o Egri, and D´ aniel Marx. Fixed-parameter approximability of Boolean MinCSPs. InProc. 24th Annual European Symposium on Algorithms (ESA-2016), pages 18:1–18:18,

    work page 2016

  5. [5]

    Bshouty and Ariel Gabizon

    [BG17] Nader H. Bshouty and Ariel Gabizon. Almost optimal cover-free families. InProc. 10th International Conference on Algorithms and Complexity (CIAC-2017), pages 140–151,

    work page 2017

  6. [6]

    S., and Dor Minzer

    [BKM25] Mitali Bafna, Karthik C. S., and Dor Minzer. Near optimal constant inapproximability under ETH for fundamental problems in parameterized complexity. InProc. 57th Annual ACM Symposium on Theory of Computing (STOC-2025), pages 2118–2129,

    work page 2025

  7. [7]

    Faster parameterized vertex multicut.arXiv preprint arXiv:2602.13981,

    [CLL+26] Huairui Chu, Yuxi Liu, Daniel Lokshtanov, Junqiang Peng, Kangyi Tian, and Mingyu Xiao. Faster parameterized vertex multicut.arXiv preprint arXiv:2602.13981,

    work page arXiv

  8. [8]

    Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, and Roohani Sharma

    [DJO+23] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, and Roohani Sharma. Parameterized complexity classification for interval constraints. InProc. 18th International Symposium on Parameterized and Exact Computation (IPEC-2023), pages 11:1–11:19,

    work page 2023

  9. [9]

    Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlstr¨ om

    [DJO+24] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlstr¨ om. Towards a parameterized approximation dichotomy of MinCSP for linear equations over finite commutative rings.CoRR, abs/2410.09932,

    work page arXiv

  10. [10]

    Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlstr¨ om

    [DJO+25b] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlstr¨ om. Parameterized approximability for modular linear equations. InProc. 33rd Annual European Symposium on Algorithms (ESA-2025), volume 351, pages 88:1–88:15,

    work page 2025

  11. [11]

    On the parameterized complexity of symmetric directed multicut

    [ERW22] Eduard Eiben, Cl´ ement Rambaud, and Magnus Wahlstr¨ om. On the parameterized complexity of symmetric directed multicut. InProc. 17th International Symposium on Parameterized and Exact Computation (IPEC-2022), pages 11:1–11:17,

    work page 2022

  12. [12]

    Almost optimal time lower bound for approximating parameterized clique, CSP, and more, under ETH.arXiv preprint arXiv:2404.08870,

    [GLR+24a] Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu. Almost optimal time lower bound for approximating parameterized clique, CSP, and more, under ETH.arXiv preprint arXiv:2404.08870,

    work page arXiv

  13. [13]

    Param- eterized inapproximability hypothesis under exponential time hypothesis

    46 [GLR+24b] Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu. Param- eterized inapproximability hypothesis under exponential time hypothesis. InProc. 56th Annual ACM Symposium on Theory of Computing (STOC-2024), pages 24–35,

    work page 2024

  14. [14]

    Baby PIH: parameterized inapproximability of MinCSP

    [GRS24] Venkatesan Guruswami, Xuandi Ren, and Sai Sandeep. Baby PIH: parameterized inapproximability of MinCSP. InProc. 39th Computational Complexity Conference (CCC-2024), pages 27:1–27:17,

    work page 2024

  15. [15]

    Lima, Tom´ as Masar´ ık, Marcin Pilipczuk, Roohani Sharma, and Manuel Sorge

    [HJL+23] Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tom´ as Masar´ ık, Marcin Pilipczuk, Roohani Sharma, and Manuel Sorge. Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow- augmentation. InProc. 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2023), pages...

    work page 2023

  16. [16]

    0/1/all CSPs, half-integral A- path packing, and linear-time FPT algorithms

    [IYY18] Yoichi Iwata, Yutaro Yamaguchi, and Yuichi Yoshida. 0/1/all CSPs, half-integral A- path packing, and linear-time FPT algorithms. InProc. IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS-2018), pages 462–473,

    work page 2018

  17. [17]

    Decomposition of domains based on the micro-structure of finite constraint-satisfaction problems

    [J´ eg93] Philippe J´ egou. Decomposition of domains based on the micro-structure of finite constraint-satisfaction problems. InProc. 11th National Conference on Artificial Intelligence (AAAI-1993), pages 731–736,

    work page 1993

  18. [18]

    On the power of unique 2-prover 1-round games

    [Kho02] Subhash Khot. On the power of unique 2-prover 1-round games. InProc. 24th Annual ACM Symposium on Theory of Computing (STOC-2002), pages 767–775,

    work page 2002

  19. [19]

    An improved parameterized algorithm for treewidth

    [KL23] Tuukka Korhonen and Daniel Lokshtanov. An improved parameterized algorithm for treewidth. InProc. 55th Annual ACM Symposium on Theory of Computing (STOC- 2023), pages 528–541,

    work page 2023

  20. [20]

    Candidate hard unique game

    [KM16] Subhash Khot and Dana Moshkovitz. Candidate hard unique game. InProc. 48th Annual ACM Symposium on Theory of Computing (STOC-2016), pages 63–76,

    work page 2016

  21. [21]

    On weighted graph separation problems and flow-augmentation.arXiv preprint arXiv:2208.14841,

    47 [KPSW22] Eun Jung Kim, Marcin Pilipczuk, Roohani Sharma, and Magnus Wahlstr¨ om. On weighted graph separation problems and flow-augmentation.arXiv preprint arXiv:2208.14841,

    work page arXiv

  22. [22]

    [LMR+21] Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. FPT-approximation for FPT problems. InProc. 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA-2021), pages 199–218,

    work page 2021

  23. [23]

    [LRSZ20] Daniel Lokshtanov, M. S. Ramanujan, Saket Saurab, and Meirav Zehavi. Parameterized complexity and approximability of directed odd cycle transversal. InProc. 40th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2020), pages 2181–2200,

    work page 2020

  24. [24]

    LP-branching algorithms based on biased graphs.CoRR, abs/1610.06060v2,

    [LW20] Euiwoong Lee and Magnus Wahlstr¨ om. LP-branching algorithms based on biased graphs.CoRR, abs/1610.06060v2,

    work page arXiv

  25. [25]

    [Mar06] D´ aniel Marx

    Updated and extended version of (Wahlstr¨ om, SODA-2017). [Mar06] D´ aniel Marx. Parameterized graph separation problems.Theoretical Computer Science, 351(3):394–406,

    work page 2017

  26. [26]

    Schulman, and Aravind Srinivasan

    [NSS95] Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. InProc. 36th Annual Foundations of Computer Science (FOCS-1995), pages 182–191,

    work page 1995

  27. [27]

    Parameterized complexity of MinCSP over the point algebra

    [OPW24] George Osipov, Marcin Pilipczuk, and Magnus Wahlstr¨ om. Parameterized complexity of MinCSP over the point algebra. InProc. 32nd Annual European Symposium on Algorithms (ESA-2024), volume 308, pages 93:1–93:15,

    work page 2024

  28. [28]

    Parameterized complexity of equality mincsp

    [OW23] George Osipov and Magnus Wahlstr¨ om. Parameterized complexity of equality mincsp. InProc. 31st Annual European Symposium on Algorithms (ESA-2023), volume 274, pages 86:1–86:17,

    work page 2023

  29. [29]

    Available at https://pacs2024.github.io/pacs2024-open-problems

    48 [PAC24] PACS 2024: Workshop on parameterized algorithms and constraint satisfaction: Open problems. Available at https://pacs2024.github.io/pacs2024-open-problems. pdf,

    work page 2024

  30. [30]

    Optimal algorithms and inapproximability results for every CSP? InProc

    [Rag08] Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? InProc. 40th Annual ACM Symposium on Theory of Computing (STOC-2008), pages 245–254,

    work page 2008

  31. [31]

    LP-branching algorithms based on biased graphs

    [Wah17] Magnus Wahlstr¨ om. LP-branching algorithms based on biased graphs. InProc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2017), pages 1559–1570,

    work page 2017

  32. [32]

    Matroids from gain graphs over quotient groups.arXiv preprint arXiv:2602.23066,

    [Wal26] Zach Walsh. Matroids from gain graphs over quotient groups.arXiv preprint arXiv:2602.23066,

    work page arXiv