Establishing Complexity of Problems Parameterized Above Average

Establishing Complexity of Problems Parameterized Above Average

Tue, 09/03/2010
14:30 		Gregory Z. Gutin (Royal Holloway) Combinatorial Theory Seminar Add to calendar L3
Establishing Complexity of Problems Parameterized Above Average
In the Max Acyclic Subdigraph problem we are given a digraph $ D $ and ask whether $ D $ contains an acyclic subdigraph with at least $ k $ arcs. The problem is NP-complete and it is easy to see that the problem is fixed-parameter tractable, i.e., there is an algorithm of running time $ f(k)n $ for solving the problem, where $ f $ is a computable function of $ k $ only and $ n=|V(D)| $. The last result follows from the fact that the average number of arcs in an acyclic subdigraph of $ D $ is $ m/2 $, where $ m $ is the number of arcs in $ D $. Thus, it is natural to ask another question: does $ D $ have an acyclic subdigraph with at least $ m/2 +k $ arcs? Mahajan, Raman and Sikdar (2006, 2009), and by Benny Chor (prior to 2006) asked whether this and other problems parameterized above the average are fixed-parameter tractable (the problems include Max $ r $-SAT, Betweenness, and Max Lin). Most of there problems have been recently shown to be fixed-parameter tractable. Methods involved in proving these results include probabilistic inequalities, harmonic analysis of real-valued functions with boolean domain, linear algebra, and algorithmic-combinatorial arguments. Some new results obtained in this research are of potential interest for several areas of discrete mathematics and computer science. The examples include a new variant of the hypercontractive inequality and an association of Fourier expansions of real-valued functions with boolean domain with weighted systems of linear equations over $ F^n_2 $. I’ll mention results obtained together with N. Alon, R. Crowston, M. Jones, E.J. Kim, M. Mnich, I.Z. Ruzsa, S. Szeider, and A. Yeo.