Parameterised Complexity of Almost Satisfiable Systems of Linear Equations

George Osipov ( Linköping University )

Well-known algorithms such as Gaussian elimination can efficiently solve systems of linear equations over various rings. However, such algorithms reject systems that do not admit a perfect solution without providing any information on "how far" the instances are from being satisfiable. This motivates studying the MinLin(R) problem: given a system of linear equations over a ring R, find an assignment that minimises the number of unsatisfied equations. This problem is notoriously hard: under the Unique Games Conjecture, even Min2Lin(Z2), i.e. the special case over the two-element ring with two variables per equation, is NP-hard to approximate within any constant factor.

Towards solving almost satisfiable instances, we study parameterised complexity of MinLin(R) with the parameter k being the minimum number of equations that need to be removed to make the system satisfiable. We obtain a comprehensive picture:

(1) Even over Z2, if three or more variables are allowed in each equation, the problem is W[1]-hard to approximate, implying that the trivial algorithm that guesses the set of k equations to remove is essentially optimal.

(2) However, if every equation has at most two variables, the problem becomes fixed parameter tractable over various rings, such as the rationals, the integers, any finite field, and over the integer modulo any prime power.

(3) For linear equations over the integers modulo m, we show that in FPT time one can compute an omega(m)-approximation, where omega counts the number of prime factors of m, and show that this approximation factor is essentially optimal under the Exponential Time Hypothesis.

In my talk I will assume no prior knowledge of parameterised complexity and try to provide a gentle introduction to the subject.

Based on joint work with Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak and Magnus Wahlström.