BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1758
DTSTAMP:20260804T083732Z
SUMMARY:Approximating Vertex Deletion Problems in FPT Time: Unbounded Obstr
 uctions and Two Budgets
DESCRIPTION:Speaker: Soumen Mandal (IIT Delhi)\n\nAbstract: \n A vertex de
 letion problem asks for at most k vertices whose removal makes a graph sat
 isfy a property Pi. Such problems are typically NP-hard\, and their polyno
 mial-time approximation factors are in many cases tight under standard a
 ssumptions. Parameterized approximation relaxes the running time instead: 
 given f(k) times a polynomial in n\, can we do better than the polynomial-
 time factor allows? Two combinations recur: reduce the parameter and finis
 h with an exact FPT algorithm\, or solve most of the instance exactly and 
 finish with a polynomial-time approximation.\nWhen every minimal obstructi
 on to Pi has size at most d\, partial branching combined with the polynomi
 al-time d-approximation already gives a parameterized approximation scheme
 . This is unavailable when obstructions are unbounded\, as for Feedback Ve
 rtex Set\, where they are cycles of arbitrary length. I will show how a sa
 mpling step can take the place of branching in this case\, and how the run
 ning time improves further when the problem also admits a good polynomial-
 time approximation or a fast exact FPT algorithm.\nThe question changes ch
 aracter once vertices carry weights. For Weighted Vertex Cover no factor b
 elow 2 is known even in FPT time\, and the total weight can be arbitrarily
  large and unrelated to k\, so it cannot serve as a good parameter itself.
  Keeping k as the parameter and carrying the weight as a second budget W g
 ives a problem in which no single factor is the right guarantee: the natur
 al relaxation is bi-criteria\, returning a set of size at most ak and weig
 ht at most bW. I will present a family of such algorithms for Vertex Cover
  trading the pair (a\,b) against running time\, how far this extends to d-
 Hitting Set\, what is known when obstructions are unbounded\, and the ques
 tions left open.\n
URL:https://www.tcs.tifr.res.in/web/events/1758
DTSTART;TZID=Asia/Kolkata:20260806T090000
DTEND;TZID=Asia/Kolkata:20260806T100000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR