Backdoor Criterion Check

Problem

Given a small DAG with n nodes 0..n-1, directed edges as [u, v] pairs, a treatment node, an outcome node, and a list of adjustment nodes, return True when the adjustment set satisfies the backdoor criterion. It holds when no adjusted node is a descendant of the treatment and the adjustment d-separates treatment from outcome after deleting edges out of the treatment.

Hint

Delete arrows out of treatment, then check every remaining path for blocking.

Test cases

case 1

in: [3,[[2,0],[2,1],[0,1]],0,1,[]]

expected: false

case 2

in: [3,[[2,0],[2,1],[0,1]],0,1,[2]]

expected: true

case 3

in: [3,[[0,2],[2,1]],0,1,[2]]

expected: false

case 4

in: [4,[[1,0],[1,3],[0,2],[2,3]],0,3,[]]

expected: false

case 5

in: [4,[[1,0],[1,3],[0,2],[2,3]],0,3,[1]]

expected: true

Starter codePython

def backdoor_criterion(n, edges, treatment, outcome, adjustment):
    # Your code here
    pass

5 test cases · run your code against them in the editor