University of Cambridge > > Combinatorics Seminar > Establishing Complexity of Problems Parameterized Above Average

Establishing Complexity of Problems Parameterized Above Average

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

  • UserGregory Gutin (Royal Holloway, University of London)
  • ClockThursday 04 February 2010, 14:30-15:30
  • HouseMR12.

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)nO(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 Fn2.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2019, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity