BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1589
DTSTAMP:20250725T093050Z
SUMMARY:Counting Problems in Graphical Models
DESCRIPTION:Speaker: Vidya Sagar Sharma (TIFR)\n\nAbstract: \nA graphical m
 odel is a probabilistic model that uses a graph to represent conditional i
 ndependence relations among random variables. We study acyclic directed gr
 aphical models\, where a directed acyclic graph (DAG) is used to represent
  both conditional independence and causal relationships. Multiple DAGs can
  represent the same set of conditional independence relations\; such DAGs 
 are called Markov equivalent and belong to the same equivalence class\, ca
 lled a Markov equivalence class (MEC)\, which is graphically represented b
 y the union of the DAGs it contains. Many combinatorial problems related t
 o MECs have been studied in the literature. One such problem is: given the
  graphical representation of an MEC\, compute its size. In a generalizatio
 n of this problem\, we are also given background knowledge in the form of 
 a set of directed edges. A DAG in the MEC is consistent with the backgroun
 d knowledge if the background knowledge is a subset of its directed edges\
 , and the goal is to count such DAGs. Another important problem is: given 
 an undirected graph\, count the number of MECs whose skeleton is the same 
 as the undirected graph.\n \nWienöbst et al. show that counting backgrou
 nd knowledge-consistent DAGs in an MEC is #P-hard. In this talk\, we prese
 nt an FPT algorithm for this problem\, along with an FPT algorithm for cou
 nting MECs with a given skeleton. We further provide a faster FPT algorith
 m when the input graph is chordal\, and a polynomial-time algorithm when t
 he input graph is a tree.\n \n
URL:https://www.tcs.tifr.res.in/web/events/1589
DTSTART;TZID=Asia/Kolkata:20250730T140000
DTEND;TZID=Asia/Kolkata:20250730T163000
LOCATION:Hybrid Mode (A-201)
END:VEVENT
END:VCALENDAR