  Checking whether a system of linear equations is consistent is a basic
computational problem with ubiquitous applications. When dealing with
inconsistent systems, one may seek an assignment that minimizes the number of
unsatisfied equations. This problem is NP-hard and UGC-hard to approximate
within any constant even for two-variable equations over the two-element field.
We study this problem from the point of view of parameterized complexity, with
the parameter being the number of unsatisfied equations. We consider equations
defined over Euclidean domains - a family of commutative rings that generalize
finite and infinite fields including the rationals, the ring of integers, and
many other structures. We show that if every equation contains at most two
variables, the problem is fixed-parameter tractable. This generalizes many
eminent graph separation problems such as Bipartization, Multiway Cut and
Multicut parameterized by the size of the cutset. To complement this, we show
that the problem is W[1]-hard when three or more variables are allowed in an
equation, as well as for many commutative rings that are not Euclidean domains.
On the technical side, we introduce the notion of important balanced subgraphs,
generalizing important separators of Marx [Theor. Comput. Sci. 2006] to the
setting of biased graphs. Furthermore, we use recent results on parameterized
MinCSP [Kim et al., SODA 2021] to efficiently solve a generalization of
Multicut with disjunctive cut requests.
