BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1127
DTSTAMP:20230914T125951Z
SUMMARY:Singly Connected Vertex Deletion Problem
DESCRIPTION:Speaker: Avinandan Das (Institut de Recherche en Informatique F
ondamentale\, Paris)\n\nAbstract: \nIn this talk\, I am going to present t
he Singly Connected Vertex Deletion Problem (SCVD).\nA digraph D is singly
connected if for all ordered pairs of vertices u\, v ∈ V (D)\, there is
at most one path in D from u to v. In this paper\, we study the Singly Co
nnected Vertex Deletion (SCVD) problem: Given an n-vertex digraph D and a
positive integer k\, does there exist a set S ⊆ V (D) such that |S| ≤
k and D − S is singly connected? This problem may be seen as a directed
counterpart of the (Undirected) Feedback Vertex Set problem\, as an undire
cted graph is singly connected if and only if it is acyclic. SCVD is known
to be NP-hard on general digraphs. We study the complexity of SCVD on var
ious classes of digraphs such as tournaments\, and various generalisations
of tournaments such as digraphs of bounded independence number\, in- and
out-tournaments and local tournaments. We show that unlike the Feedback Ve
rtex Set on Tournaments (FVST) problem\, SCVD is polynomial-time solvable
on tournaments. In addition\, we show that SCVD is polynomial-time solvabl
e on digraphs of bounded independence number\, and on the class of acyclic
local tournaments. We also study the parameterized complexity of SCVD\, w
ith k as the parameter\, on the class of in-tournaments. And we show that
on in-tournaments\, SCVD admits a fixed-parameter tractable algorithm and
a quadratic kernel.\n\nWe also show that on the class of local tournaments
\, which is a sub-class of in-tournaments\, SCVD admits a linear kernel.\n
\nZoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt
0Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1127
DTSTART;TZID=Asia/Kolkata:20210423T171500
DTEND;TZID=Asia/Kolkata:20210423T181500
END:VEVENT
END:VCALENDAR