English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Causal DAGs (also known as Bayesian networks) are a popular tool for encodingconditional dependencies between random variables. In a causal DAG, the randomvariables are modeled as vertices in the DAG, and it is stipulated that everyrandom variable is independent of its ancestors conditioned on its parents. Itis possible, however, for two different causal DAGs on the same set of randomvariables to encode exactly the same set of conditional dependencies. Suchcausal DAGs are said to be Markov equivalent, and equivalence classes of Markovequivalent DAGs are known as Markov Equivalent Classes (MECs). Beautifulcombinatorial characterizations of MECs have been developed in the past fewdecades, and it is known, in particular that all DAGs in the same MEC must havethe same ''skeleton'' (underlying undirected graph) and v-structures (inducedsubgraph of the form $a\rightarrow b \leftarrow c$).  These combinatorial characterizations also suggest several naturalalgorithmic questions. One of these is: given an undirected graph $G$ as input,how many distinct Markov equivalence classes have the skeleton $G$? Much workhas been devoted in the last few years to this and other closely relatedproblems. However, to the best of our knowledge, a polynomial time algorithmfor the problem remains unknown.  In this paper, we make progress towards this goal by giving a fixed parametertractable algorithm for the above problem, with the parameters being thetreewidth and the maximum degree of the input graph $G$. The main technicalingredient in our work is a construction we refer to as shadow, which lets uscreate a "local description'' of long-range constraints imposed by thecombinatorial characterizations of MECs.

A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton