Establishing Complexity of Problems Parameterized Above Average

Add to your list(s) Download to your calendar using vCal

• Gregory Gutin (Royal Holloway, University of London)
• Thursday 04 February 2010, 14:30-15:30
• MR12.

If you have a question about this talk, please contact Andrew Thomason.

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.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.