## Abstract

In the parameterized problem MaxLin2-AA[k], we are given a system with variables ^{x1},.,^{xn} consisting of equations of the form ∝_{iεI} ^{xi}=b, where ^{xi},bε{-1,1} and IâŠ†[n], each equation has a positive integral weight, and we are to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2+k, where W is the total weight of all equations and k is the parameter (it is always possible for k=0). We show that MaxLin2-AA[k] has a kernel with at most O(^{k2}logk) variables and can be solved in time 2^{O(klogk)}(^{nm)O(1)}. This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,r] is the same as MaxLin2-AA[k] with two differences: each equation has at most r variables and r is the second parameter. We prove that Max-r-Lin2-AA[k,r] has a kernel with at most (2k-1)r variables.

Original language | English |
---|---|

Journal | Journal of Computer and System Sciences |

Volume | 80 |

Issue number | 4 |

Pages (from-to) | 687-696 |

ISSN | 0022-0000 |

DOIs | |

Publication status | Published - 2014 |

Externally published | Yes |

## Keywords

- Fixed-parameter tractable
- Kernel
- MaxLin