Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2312.17626 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913181145759744 |
|---|---|
| author | Sharma, Vidya Sagar |
| author_facet | Sharma, Vidya Sagar |
| contents | The structure of Markov equivalence classes (MECs) of causal DAGs has been studied extensively. A natural question in this regard is to algorithmically find the number of MECs with a given skeleton. Until recently, the known results for this problem were in the setting of very special graphs (such as paths, cycles, and star graphs). More recently, a fixed-parameter tractable (FPT) algorithm was given for this problem which, given an input graph $G$, counts the number of MECs with the skeleton $G$ in $O(n(2^{O(d^4k^4)} + n^2))$ time, where $n$, $d$, and $k$, respectively, are the numbers of nodes, the degree, and the treewidth of $G$.
We give a faster FPT algorithm that solves the problem in $O(n(2^{O(d^2k^2)} + n^2))$ time when the input graph is chordal. Additionally, we show that the runtime can be further improved to polynomial time when the input graph $G$ is a tree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_17626 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Faster Fixed Parameter Tractable Algorithms for Counting Markov Equivalence Classes with Special Skeletons Sharma, Vidya Sagar Data Structures and Algorithms The structure of Markov equivalence classes (MECs) of causal DAGs has been studied extensively. A natural question in this regard is to algorithmically find the number of MECs with a given skeleton. Until recently, the known results for this problem were in the setting of very special graphs (such as paths, cycles, and star graphs). More recently, a fixed-parameter tractable (FPT) algorithm was given for this problem which, given an input graph $G$, counts the number of MECs with the skeleton $G$ in $O(n(2^{O(d^4k^4)} + n^2))$ time, where $n$, $d$, and $k$, respectively, are the numbers of nodes, the degree, and the treewidth of $G$. We give a faster FPT algorithm that solves the problem in $O(n(2^{O(d^2k^2)} + n^2))$ time when the input graph is chordal. Additionally, we show that the runtime can be further improved to polynomial time when the input graph $G$ is a tree. |
| title | Faster Fixed Parameter Tractable Algorithms for Counting Markov Equivalence Classes with Special Skeletons |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2312.17626 |