BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Establishing Complexity of Problems Parameterized
Above Average - Gregory Gutin (Royal Holloway\, Un
iversity of London)
DTSTART;TZID=Europe/London:20100204T143000
DTEND;TZID=Europe/London:20100204T153000
UID:TALK22235AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/22235
DESCRIPTION:In the Max Acyclic Subdigraph problem we are given
a digraph D and ask\nwhether D contains an acycli
c subdigraph with at least k arcs. The\nproblem is
NP-complete and it is easy to see that the probl
em is\nfixed-parameter tractable\, i.e.\, there is
an algorithm of running time\nf(k)n^O(1)^ for sol
ving the problem\, where f is a computable functio
n\nof k only and n=|V(D)|. The last result follows
from the fact that the\naverage number of arcs in
an acyclic subdigraph of D is m/2\, where m\nis t
he number of arcs in D. Thus\, it is natural to as
k another\nquestion: does D have an acyclic subdig
raph with at least m/2 +k arcs?\n\nMahajan\, Raman
and Sikdar (2006\, 2009)\, and by Benny Chor (pri
or to\n2006) asked whether this and other problems
parameterized above the\naverage are fixed-parame
ter tractable (the problems include Max r-SAT\,\nB
etweenness\, and Max Lin). Most of there problems
have been recently\nshown to be fixed-parameter tr
actable.\n\nMethods involved in proving these resu
lts include probabilistic\ninequalities\, harmonic
analysis of real-valued\nfunctions with boolean d
omain\, linear algebra\, and\nalgorithmic-combinat
orial arguments.\nSome new results obtained in thi
s research are of potential interest\nfor several
areas of discrete mathematics and computer science
. The\nexamples include a new variant of the hyper
contractive inequality and\nan association of Four
ier expansions of real-valued functions with\nbool
ean domain with weighted systems of linear equatio
ns over F^n^2.\n\nI'll mention results obtained to
gether with N. Alon\, R. Crowston\, M.\nJones\, E.
J. Kim\, M. Mnich\, I.Z. Ruzsa\, S. Szeider\, and
A. Yeo.\n
LOCATION:MR12
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR