Name
Title | ||
|---|---|---|
Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average. |
Abstract | ||
|---|---|---|
In the parameterized problem MaxLin2-AA[k], we are given a system with variables x1,..., xn consisting of equations of the form Pi(i epsilon I) x(i) = b, where x(i), b epsilon {-1, 1} and I subset of [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 (if k = 0, the possibility is assured). We show that MaxLin2-AA[k] has a kernel with at most O(k(2) log k) variables and can be solved in time 2(O(k log k)) (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 a theorem on Max-r-Lin2-AA[k, r] which implies that Max-r-Lin2-AA[k, r] has a kernel with at most (2k -1) r variables, improving a number of results including one by Kim and Williams (2010). The theorem also implies a lower bound on the maximum of a function f : {-1, 1}(n) -> R whose Fourier expansion (which is a multilinear polynomial) is of degree r. We show applicability of the lower bound by giving a new proof of the Edwards-Erdos bound (each connected graph on n vertices and m edges has a bipartite subgraph with at least m/2+(n-1)/4 edges) and obtaining a generalization. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.4230/LIPIcs.FSTTCS.2011.229 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
MaxLin,fixed-parameter tractability,kernelization,pseudo-boolean functions | Kernelization,Discrete mathematics,Linear equation,Combinatorics,Parameterized complexity,Open problem,Vertex (geometry),Computer science,Upper and lower bounds,Bipartite graph,Connectivity | Conference |
Volume | ISSN | Citations |
13 | 1868-8969 | 3 |
PageRank | References | Authors |
0.45 | 0 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert Crowston | 1 | 91 | 9.15 |
| Michael R. Fellows | 2 | 4138 | 319.37 |
| Gregory Gutin | 3 | 1583 | 142.47 |
| Mark Jones | 4 | 80 | 7.78 |
| Frances A. Rosamond | 5 | 21 | 2.83 |
| Stéphan Thomassé | 6 | 651 | 66.03 |
| Anders Yeo | 7 | 43 | 3.73 |