Parameterized Complexity of Satisfying Almost All Linear Equations over F2
Robert Crowston, Gregory Gutin, Mark Jones, Anders Yeo · 2013
The problem MaxLin2 can be stated as follows. We are given a system S of m equations in variables x1, . . . , xn, where each equation ∑ i∈Ij xi = bj is assigned a positive integral weight wj and bj ∈ F2, Ij ⊆ {1,2, . . . , n} for j = 1, . . . ,m. We are required to find an assignment of values in F2 to the variables in order to maximize the total weight of the satisfied equations. Let W be the total weight of all equations in S. We consider the following parameterized version of MaxLin2: decide whether there is an assignment satisfying equations of total weight at least W − k, where k is a nonnegative parameter. We prove that this parameterized problem is W [1]-hard even if each equation of S has exactly three variables and every variable appears in exactly three equations and, moreover, each weight wj equals 1 and no two equations have the same left-hand side. We show the tightness of this result by proving that if each equation has at most two variables then the parameterized problem is fixed-parameter tractable. We also prove that if no variable appears in more than two equations then we can maximize the total weight of satisfied equations in polynomial time.