Finding minimal d-separators in linear time and applications


The study of graphical causal models is fundamentally the study of separations and conditional independences. We provide linear-time algorithms for two graphical primitives: to test, if a given set is a minimal d-separator, and to find a minimal d-separator in directed acyclic graphs (DAGs), completed partially directed acyclic graphs (CPDAGs) and restricted chain graphs (RCGs) as well as minimal m-separators in ancestral graphs (AGs). These algorithms improve the runtime of the best previously known algorithms for minimal separators that are based on moralization and thus require quadratic time to construct and handle the moral graph. (Minimal) separating sets have important applications like finding (minimal) covariate adjustment sets or conditional instrumental variables.

Original languageEnglish
Number of pages11
Publication statusPublished - 2019
Event35th Conference on Uncertainty in Artificial Intelligence - Tel Aviv, Israel
Duration: 22.07.201925.07.2019
Conference number: 151391


Conference35th Conference on Uncertainty in Artificial Intelligence
Abbreviated titleUAI 2019
CityTel Aviv

DFG Research Classification Scheme

  • 409-01 Theoretical Computer Science


Dive into the research topics of 'Finding minimal d-separators in linear time and applications'. Together they form a unique fingerprint.

Cite this