 # Applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra in Fixed-Parameter Tractability and Kernelization

• Gutin, B (Royal Holloway)
• Tuesday 21 June 2011, 14:00-15:00
• Seminar Room 2, Newton Institute Gatehouse.

Discrete Analysis

et \$P\$ be a decision problem (answers are yes or no). A parameterized problem \$Pi\$ is a set of pairs \$(x,k)\$ where \$x\$ is an instance of \$P\$ and \$k\$ (usually an integer) is the parameter. One example is the \$k\$-Vertex Cover problem, where for a given graph \$G\$ we are to decide whether there is a set of \$k\$ vertices covering all edges of \$G.\$

A kernelization of \$Pi\$ is a polynomial time algorithm that maps an instance \$(x,k)in Pi\$ to an instance \$(x’,k’)in Pi\$ (kernel) such that (i) \$(x,k)\$ is a yes-instance iff \$(x’,k’)\$ is a yes-instance, (ii) \$k’leq h(k)\$ and \$|x’|leq g(k)\$ for some functions \$h\$ and \$g\$, where \$|x’|\$ is the size of \$x’\$. For example, there is a kernelization of \$k\$-Vertex Cover reducing each pair (\$G,k\$) into (\$H,k\$), where \$H\$ has at most \$2k\$ vertices and \$k2\$ edges.

A parameterized problem is fixed-parameter tractable if it can be solved in time \$O(f(k)|x|{O(1)})\$ for some function \$f\$ in \$k\$. It is well-known that a parameterized problem is fixed-parameter tractable iff it is decidable and admits a kernelization.

We’ll discuss applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra to some parameterized problems. We’ll mainly discuss MaxLin2-AA: given a system of linear equations over GF(2) in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least \$W/2+k,\$ where \$W\$ is the total weight of all equations of the system. Solving an open question of Mahajan, Raman and Sikdar (2006,2009), we’ll show that MaxLin2-AA is fixed-parameter tractable and admits a kernel with at most \$O(k^2log k)\$ variables. Here we use Linear Algebra.

This is a very recent result, see http://arxiv.org/abs/1104.1135 It is still unknown whether MaxLin2-AA admits a kernel with a polynomial number of equations (rather than variables), but we can prove that such a kernel exists for a number of special cases of MaxLin2-AA. Here we apply Probabilistic Method and Discrete Harmonic Analysis. In particular, we use the well-known (4,2)-Hypercontractive Inequality as well as its new version.

This talk is part of the Isaac Newton Institute Seminar Series series.