BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1346
DTSTAMP:20231020T044050Z
SUMMARY:Counting Markov equivalence classes with the same skeleton
DESCRIPTION:Speaker: Vidya Sagar Sharma (TIFR)\n\nAbstract: \nWe study a di
rected acyclic graphical model\, also known as a Bayesian network. In this
model\, a directed acyclic graph (DAG) is used to represent conditional d
ependence between random variables. Two DAGs are said to be Markov equival
ent if both represent the same set of conditional independence between the
random variables. Verma and Pearl (1990) show that two DAGs are Markov eq
uivalent if\, and only if\, both have the same skeleton (underlying undire
cted graph) and the same v-structures (induced subgraph of the form $a\\ri
ghtarrow b \\leftarrow c$). Markov equivalent DAGs belong to the same Mark
ov equivalent class (MEC). A graphical representation of an MEC is the uni
on of the DAGs it contains.An interesting problem related to the study of
MECs is: for an input undirected graph $G$\, count the MECs with skeleton
$G$. This problem has both graphical and statistical significance. In this
talk\, we will discuss a polynomial algorithm that solves the problem whe
n the skeleton is a tree graph. We will also explore a fixed parameter tra
ctable algorithm to solve the problem.\n
URL:https://www.tcs.tifr.res.in/web/events/1346
DTSTART;TZID=Asia/Kolkata:20231020T180000
DTEND;TZID=Asia/Kolkata:20231020T190000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR