Counting Background Knowledge Consistent Markov Equivalent Directed Acyclic Graphs

Vidya Sagar Sharma
Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, PMLR 216:1911-1920, 2023.

Abstract

We 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 the form of the directions of some additional edges in the MEC. A polynomial-time algorithm for the special case of the problem, when no background knowledge constraints are specified, was given by Wienöbst, Bannach, and Liskiewicz (AAAI 2021), who also showed that the general case is NP-hard (in fact, #P-hard). In this paper, we show that the problem is nevertheless tractable in an interesting class of instances, by establishing that it is “fixed-parameter tractable”: we give an algorithm that 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 MEC that participate in the specified background knowledge constraints. In particular, our algorithm runs in polynomial time in the well-studied special case of MECs of bounded tree-width or bounded maximum clique size.

Cite this Paper

BibTeX
@InProceedings{pmlr-v216-sharma23b, title = {Counting Background Knowledge Consistent {M}arkov Equivalent Directed Acyclic Graphs}, author = {Sharma, Vidya Sagar}, booktitle = {Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence}, pages = {1911--1920}, year = {2023}, editor = {Evans, Robin J. and Shpitser, Ilya}, volume = {216}, series = {Proceedings of Machine Learning Research}, month = {31 Jul--04 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v216/sharma23b/sharma23b.pdf}, url = {https://proceedings.mlr.press/v216/sharma23b.html}, abstract = {We 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 the form of the directions of some additional edges in the MEC. A polynomial-time algorithm for the special case of the problem, when no background knowledge constraints are specified, was given by Wienöbst, Bannach, and Liskiewicz (AAAI 2021), who also showed that the general case is NP-hard (in fact, #P-hard). In this paper, we show that the problem is nevertheless tractable in an interesting class of instances, by establishing that it is “fixed-parameter tractable”: we give an algorithm that 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 MEC that participate in the specified background knowledge constraints. In particular, our algorithm runs in polynomial time in the well-studied special case of MECs of bounded tree-width or bounded maximum clique size.} }
Endnote
%0 Conference Paper %T Counting Background Knowledge Consistent Markov Equivalent Directed Acyclic Graphs %A Vidya Sagar Sharma %B Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2023 %E Robin J. Evans %E Ilya Shpitser %F pmlr-v216-sharma23b %I PMLR %P 1911--1920 %U https://proceedings.mlr.press/v216/sharma23b.html %V 216 %X We 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 the form of the directions of some additional edges in the MEC. A polynomial-time algorithm for the special case of the problem, when no background knowledge constraints are specified, was given by Wienöbst, Bannach, and Liskiewicz (AAAI 2021), who also showed that the general case is NP-hard (in fact, #P-hard). In this paper, we show that the problem is nevertheless tractable in an interesting class of instances, by establishing that it is “fixed-parameter tractable”: we give an algorithm that 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 MEC that participate in the specified background knowledge constraints. In particular, our algorithm runs in polynomial time in the well-studied special case of MECs of bounded tree-width or bounded maximum clique size.
APA
Sharma, V.S.. (2023). Counting Background Knowledge Consistent Markov Equivalent Directed Acyclic Graphs. Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 216:1911-1920 Available from https://proceedings.mlr.press/v216/sharma23b.html.

Related Material