Abstract

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^O(1) 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ⁿ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.