BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1307
DTSTAMP:20230914T125958Z
SUMMARY:Counting Markov equivalence directed cyclic graphs consistent with 
 background knowledge
DESCRIPTION:Speaker: Vidya Sagar Sharma\n\nAbstract: \nWe study the problem
  of counting the number of directed acyclic graphs in a Markov equivalence
  class (MEC) that are consistent with background knowledge specified in t
 he form of the directions of some additional edges in the MEC.  A polynom
 ial-time algorithm for the special case of the problem\, when no backgroun
 d knowledge constraints are specified\, was given by Wienöbst\, Bannach\,
  and Liśkiewicz (AAAI 2021)\, who also showed that the general case is NP
 -hard (in fact\, \\#P-hard).  In this talk\, we show that the problem is 
 nevertheless tractable in an interesting class of instances\, by establish
 ing that it is ``fixed-parameter tractable'' (FPT): we give an algorithm t
 hat runs in time $O(k! k^2 n^4)$\, where $n$ is the number of nodes in the
  MEC and $k$ is the maximum number of nodes in any maximal clique of the M
 EC that participate in the specified background knowledge constraints.  I
 n particular\, our algorithm runs in polynomial time in the well-studied s
 pecial case of MECs of bounded tree-width or bounded maximum clique size.
 \nPaper link: https://arxiv.org/abs/2206.06744\n
URL:https://www.tcs.tifr.res.in/web/events/1307
DTSTART;TZID=Asia/Kolkata:20230626T170000
DTEND;TZID=Asia/Kolkata:20230626T180000
LOCATION:A-201 and Zoom
END:VEVENT
END:VCALENDAR