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. The equations are defined over Euclidean domains -- an abstract algebraic structure generalizing finite and infinite fields including the rationals, the ring of integers, and many other structures. We find that the problem is W[1]-hard when three or more variables are allowed in an equation. The remaining case with two-variable equations is more interesting since it generalizes many eminent graph separation problems like Bipartization, Multiway Cut and Multicut parameterized by the solution size. We provide an fixed-parameter tractable algorithm for this case. On the technical side, we introduce the notion of important balanced subgraphs and an fpt algorithm for their enumeration. The method is used as a more efficient alternative to the sampling of important separators [Marx and Razgon, SICOMP'14]. Further, we use recent results on parameterized MinCSP [Kim et al., SODA'21] to solve a generalization of Multicut with disjunctive cut requests.

The talk is based on joint (unpublished) work with Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, and Magnus Wahlström.