PC algorithm

The PC algorithm starts with a candidate undirected graph, removes edges using conditional independence tests over increasing conditioning-set sizes, records separating sets, then orients unshielded colliders and propagates orientations. Under oracle tests and faithfulness of a directed acyclic graph, it estimates the graph's Markov equivalence class.

With an exact conditional independence oracle and faithfulness of a directed acyclic graph, the skeleton phase of the PC algorithm deletes precisely the nonedges. A true edge cannot be D-separated by a set excluding its endpoints. For nonadjacent vertices, choose the later vertex $v$ in a topological ordering; its parents separate it from the earlier nonparent. True parent edges survive throughout, so this separator remains available among the algorithm's candidate neighbour sets. For an unshielded triple $u-v-w$, any recorded separator of $u,w$ excludes $v$ exactly when the triple is an unshielded collider. The skeleton and collider characterization of Markov equivalence therefore identifies the correct equivalence class. Directions compelled throughout that class give its completed partially directed acyclic graph.

Initialize the PC skeleton search with an estimated conditional independence graph to reduce candidate pairs and conditioning sets. An exact graph contains the true Directed acyclic graph skeleton because it equals its moral graph under faithfulness. For initially absent pairs record the full complement as a separating set; an empty default can create false collider orientations. Estimation errors can affect this screening step.