ELC Seminar (Gregory Gutin)
| Time & Date | Mar. 29(Tue) 2016, 10:30 ~ 12:00 | |
|---|---|---|
| Place | CELC Seminar room (Rm. 404) | |
| Speaker | Gregory Gutin (Royal Holloway, University of London) | |
| Title | Constraint Satisfaction Problems Parameterized above Average | |
| Abstract | ||
|---|---|---|
| By computing the expected value of an appropriate random variable, it is not hard to see that every directed graph $D$ on $m$ arcs has an acyclic subgraph with at least $m/2$ arcs. The bound is tight: consider any digraph which contains arc $xy$ iff it contains arc $yx$. Similarly, it is not hard to see that we can satisfy at least $(1-2^{-r})m$ clauses in any CNF formula $F$ with $m$ clauses each with $r$ distinct variables. Again the bound is tight. Mahajan, Raman and Sikdar (IWPEC 2006 and JCSS 2009) asked whether there are fixed-parameter tractable algorithms for deciding whether $D$ has an acyclic subgraph with at least $m/2+k$ arcs and whether we can satisfy at least $(1-2^{-r})m+k$ clauses in $F$. To answer these and other questions of this nature, a new parameterized complexity method was introduced by Gutin, Kim, Szeider and Yeo (JCSS 2011) and developed in Alon, Gutin, Kim, Szeider and Yeo (Algorithmica 2011) and other papers including Makarychev, Makarychev and Zhou (FOCS 2015). We will describe the method which uses probabilistic tools as well as tools from Fourier analysis. We will also mention that to prove that MaxLin above Average is fixed-parameter tractable, required a different approach using algorithmic and linear algebraic tools. |
||