Parameterized Approximability for Modular Linear Equations

Let $p_1^{n_1}\mathrm{\cdots }{p}_{\mathrm{\ell }}^{n_{\mathrm{\ell }}}$ be the prime factorization of $m\in {\mathbb{Z}}_{+}$. It is well known that ${\mathbb{Z}}_m$ is isomorphic to the direct sum ${⨁}_{i=1}^{\mathrm{\ell }}{\mathbb{Z}}_{p_i^{n_i}}$, and we can reduce the problem to the prime power case.

Now, consider the ring ${\mathbb{Z}}_{p^n}$ for a prime $p$ and positive integer $n$. We start with a simplification step. An equation over a ring $R$ is simple if it is either a binary equation of the form $u=rv$ for some $r\in R$ or a crisp unary equation $u=r$ for some $r\in R$. An instance $S$ of $2$-Lin($R$) is simple if every equation in $S$ is simple.

Now, suppose $n=1$, i.e. we are working over a field ${\mathbb{Z}}_p$. Min-2-Lin(${\mathbb{Z}}_p$) can be solved exactly in FPT time (see. [8]); we will show a $2$-approximation because it is illustrative of our approach. For an instance $S$ of $2$-Lin(${\mathbb{Z}}_p$), we construct a graph $G=G(S)$ with vertices $x_i$ for every $x\in V(G)$ and $1\le i\le p-1$ and special vertices $s$ and $t$. For unary equations $x=r$ in $S$, add crisp edges $s{x}_r$ if $r\ne 0$, and crisp edges $x_{r}t$ for every $1\le r\le p-1$ if $r=0$. For every binary equation $e$ of the form $x=r\cdot y$, construct an edge bundle $B_e=\{x_{ri}{y}_i:1\le i\le p-1\}$ and add these edges to $G$. This completes the construction. We establish a correspondence between conformal $st$-cuts in $G(S)$ and assignments to $S$. Formally, for a set of vertices $X\subseteq V(G)$, let $\delta (X)$ be the set of edges with exactly one endpoint in $X$, i.e. $\delta (X)$ is the cut separating $X$ and $\overline{X}$. If $U\subseteq V(G)$ is such that $s\in U$, $t\notin U$ and there is at most one vertex $x_i\in U$ for any $x\in V(S)$, we say that $\delta (U)$ is a conformal $st$-cut. To construct an assignment from a conformal cut $U$, map $x\mapsto i$ whenever $x_i\in U$ for some $i\in \{1,\mathrm{\dots },p-1\}$, and otherwise $x\mapsto 0$; the reverse direction of the correspondence is obvious.

Let $b(U)$ be the number of edge bundles $B_e$ intersected by $\delta (U)$. Then $R$ being a field implies that $b(U)$ is exactly the cost of the assignment corresponding to $U$. More specifically, consider an equation $e=(x=r\cdot y)$, suppose $x_i,y_j\in U$ and $B_e\cap \delta (U)=\mathrm{\varnothing }$. Then $i=rj$ because the edge $x_{rj}{y}_j$ is uncut and both its endpoints are reachable from $s$, so the assignment corresponding to $U$ satisfies $e$. This guarantee is represented by $B_e$ being a matching: view an edge $x_i{y}_j$ as encoding “$x=i$ if and only if $y=j$”. To complete the algorithm for fields, we compute a conformal cut $\delta (U)$ with $b(U)\le k$. Observe that $b(U)\le k$ implies $\delta (U)\le 2k$ because $U$ contains at most one vertex per variable so $\delta (U)$ may intersect at most two edges of any bundle. Thus, for $2$-approximation it suffices to compute a conformal cut of size $2k$, which is guaranteed to exist for yes-instances. However, when translating it back into a set of equations, we may delete $2k$ equations because all edges of our conformal cut may intersect distinct bundles. Finally, to compute a conformal cut in FPT time, we may use branching in the style of Digraph Pair Cut [24]: compute the closest $st$-cut (which is unique by submodularity of cuts), and if it is not conformal, then branch.

If we use the same approach naïvely over ${\mathbb{Z}}_{p^n}$, $n\ge 2$, then the bundles $B_e$ stop being matchings. Consider the equation $e=(x=2y)$ over ${\mathbb{Z}}_8$ (second graph from the left in Figure 1). Note that both $y_2$ and $y_6$ are adjacent to $x_4$ in $B_e$. Moreover, if $x=4$ then either $y=2$ or $y=6$ so the dependencies cannot be captured by binary edges (even if one were to use directed graphs). Thus, we lose the connection between the number of bundles intersected by a conformal cut and the cost of the corresponding assignment. One idea for solving Min-$2$-Lin(${\mathbb{Z}}_{p^n}$) is to retain the “if and only if” semantics of an edge by matching sets of values rather than individual values. More specifically, let us partition $\{1,\mathrm{\dots },p^n-1\}$ into classes $C_1,\mathrm{\dots },C_{\mathrm{\ell }}$ and build $G(S)$ with vertices $s$, $t$ and $x_{C_1},\mathrm{\dots },x_{C_{\mathrm{\ell }}}$ for all $x\in V(S)$. To keep the matching structure for an equation $e$, we want an edge $x_{C_i}{y}_{C_j}$ in $B_e$ to mean “$x\in C_i$ if and only if $y\in C_j$”. For fields, we have used the most refined partition (every nonzero element is a class of its own). For other rings, a coarser partition is needed: e.g. if $R={\mathbb{Z}}_8$, then $2$ and $6$ have to be in the same class (think of $x=2y$). However, simply taking a coarser partition is not sufficient: indeed, the coarsest partition (putting all non-zero elements in the same class) has the required structure, but it only distinguishes between zero and nonzero values, and is not very useful algorithmically. Intuitively, we want to a partition such that a class assignment over ${\mathbb{Z}}_{p^n}$ allows us to rewrite our input as a set of equations over ${\mathbb{Z}}_{p^{n-1}}$ without increasing the cost too much.

A useful partition is obtained by viewing the elements of ${\mathbb{Z}}_{p^n}$ represented in base-$p$. Formally, every element $a\in {\mathbb{Z}}_{p^n}$ equals ${\sum }_{i=0}^{p-1}{a}_i{p}^i$, where the coefficients $a_0,\mathrm{\dots },a_{p-1}\in {\mathbb{Z}}_p$ uniquely define $a$. Let $\overrightarrow{a}=(a_0,\mathrm{\dots },a_{p-1})$, and for every $a\ne 0$, define $\mathrm{ord}(a)=\min \{i:a_i\ne 0\}$ to be the index of the first nonzero coordinate in $\overrightarrow{a}$, and $\mathrm{lsu}(a)=r_{\mathrm{ord}(a)}$ to be the least significant unit in $\overrightarrow{a}$. For completeness, let $\mathrm{ord}(0)=\mathrm{lsu}(0)=0$. Let

This equivalence relation has two important properties. First, it is matching, i.e. $\{0\}$ is an equivalence class, and for every $i,j\in {\mathbb{Z}}_{p^n}$ and $r\in {\mathbb{Z}}_{p^n}$,

• $\mathrm{■}$

  if $i\equiv j$ then $ri\equiv rj$,

• $\mathrm{■}$

  if $i\not\equiv j$, then either $ri\not\equiv rj$ or $ri=rj=0$.

Moreover, it is absorbing, meaning that

• $\mathrm{■}$

  $i\equiv j⟹p\text{ divides }i-j$ for all $i,j\in {\mathbb{Z}}_{p^n}$.

Let ${\mathrm{\Gamma }}_{p^n}$ denote the set of equivalence classes of $\equiv$, and ${\mathrm{\Gamma }}_{p^n}^{\ne 0}={\mathrm{\Gamma }}_{p^n}\setminus \{\{0\}\}$. We will drop the subscript when it is clear from the context. The name “matching” comes from considering bipartite graphs $G_r^{\ne 0}$ defined by binary equations $u=rv$ for every $r\in R$ as follows: let $V(G_r)={\mathrm{\Gamma }}^{\ne 0}\uplus {\mathrm{\Gamma }}^{\ne 0}$ and let there be an edge between two classes $C_1$ on the left and $C_2$ on the right if and only if $i=rj$ for some $i\in C_1$ and $j\in C_2$. Then $\equiv$ being matching implies that $G_r^{\ne 0}$ is a matching for every $r$, i.e. every vertex has degree at most $1$.

The matching property of $\equiv$ is crucial for the main algorithmic lemma, which we state below and prove in Section 3.2. A value assignment $\alpha :V(S)\to {\mathbb{Z}}_{p^n}$ agrees with a class assignment $\tau :V(S)\to \mathrm{\Gamma }$ if $\alpha (v)\in \tau (v)$ for all $v\in V(S)$. A class assignment $\tau$ respects an equation $e$ if it admits a satisfying assignment that agrees with $\tau$, otherwise we say that $\tau$ violates $e$. Define the cost of a class assignment $\tau$ to be the number of equations in $S$ that it violates. Note that every value assignment $\alpha$ uniquely defines a class assignment ${\tau }_{\alpha }:V(S)\to {\mathrm{\Gamma }}_{p^n}$, so we say that $\alpha$ strongly violates an equation $e$ if ${\tau }_{\alpha }$ violates $e$. Clearly, an optimal assignment can violate at most $k$ equations in $S$, and we can guess the number $q\in \{0,\mathrm{\dots },k\}$ of strongly violated equations.

While technical details are deferred to Section 3.2, we remark that we can no longer use branching in the style of Digraph Pair Cut when working over non-fields since some conformal cuts of low cost correspond to class assignments of high cost. For an extreme example over ${\mathbb{Z}}_8$, consider the system of equations $\mathrm{△}=\{x=4,2a=x,3a=b,3b=c,3c=a\}$. By the construction of $G(\mathrm{△})$, the vertex $t$ is isolated and the connected component $U$ of $s$ contains vertices $s$, $x_{\{4\}}$, $a_{\{2,6\}}$, $b_{\{2,6\}}$ and $c_{\{2,6\}}$. Hence, $\delta (U)$ is empty and conformal, but the cost of $\mathrm{△}$ is at least $1$ because the system is inconsistent (this follows from considering both possible values for $a$, which are $2$ and $6$). In fact, the cost is exactly $1$ because it is sufficient to delete $2a=x$. To mitigate this issue of “invisible” future costs, we use shadow removal in the class assignment graph followed by branching on the shadow components.

Now, to explain how the absorbing property of $\equiv$ is used, we need some definitions. Choose an arbitrary representative element $C^{\sim }$ from every equivalence class $C\in \mathrm{\Gamma }$. Consider a simple equation $e$ and a class assignment $\tau :V(e)\to \mathrm{\Gamma }$ to its variables that respects $e$. For unary equations $e=(u=r)$, define $e^{\prime }=\mathrm{next}(e,\tau )$ to be

For binary equations $e=(u=rv)$, define $e^{\prime }=\mathrm{next}(e,\tau )$ to be

The absorbing property implies that $\mathrm{next}(e,\tau )$ is defined in both cases. Indeed, if $e=(u=r)$ and $\tau$ respects $e$, then $r\in \tau (u)$ and $r\equiv \tau {(u)}^{\sim }$, so $p$ divides $r-\tau {(u)}^{\sim }$. If $e=(u=rv)$ and $\tau$ respects $e$, then there is an assignment $\alpha :\{u,v\}\to {\mathbb{Z}}_{p^n}$ such that $\alpha (u)=r\alpha (v)$, $\alpha (u)\in \tau (u)$ and $\alpha (v)\in \tau (v)$. Equivalently, $\alpha (u)-r\alpha (v)=0$ and $p$ divides both $\tau {(u)}^{\sim }-\alpha (u)$ and $\tau {(v)}^{\sim }-\alpha (v)$, hence $p$ also divides any linear combination of these two values, particularly

Now we combine all ingredients to prove the main theorem.

This subsection is devoted to a proof of Lemma 7. To achieve this we introduce the class assignment graph (Section 3.2.1) and show that certain cuts in this graph correspond to class assignments (Section 3.2.2), which themselves correspond to solutions of Min-$2$-Lin(${\mathbb{Z}}_{p^n}$). We then use shadow removal and branching to compute these cuts (Section 3.2.3). Throughout this section, we consider the ring ${\mathbb{Z}}_{p^n}$ for prime number $p$ and integer $n$.