## Abstrakt

The problem MaxLin2 can be stated as follows. We are given a system S of m equations in variables x_{1},...,x_{n}, where each equation ∑_{iεIj}x_{i} = b_{j} is assigned a positive integral weight w_{j} and b_{j} ε F_{2}, I_{j}⊆{1,2,...,n} for j=1,...,m. We are required to find an assignment of values in F_{2} 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 w_{j} 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.

Originalsprog | Engelsk |
---|---|

Tidsskrift | Theory of Computing Systems |

Vol/bind | 52 |

Udgave nummer | 4 |

Sider (fra-til) | 719-728 |

ISSN | 1432-4350 |

DOI | |

Status | Udgivet - 2013 |

Udgivet eksternt | Ja |