NP-completeness conjecture for M-identifiability

Let $G=(V \cup \mathcal{H},D)$ be a factor analysis graph. M-identifiability and extended M-identifiability are the two identifiability properties defined by the matching criterion and the extended matching criterion, respectively. NP-completeness conjecture. Deciding M-identifiability and extended M-identifiability both is NP-complete. If the cardinalities of the sets considered in the matching and local BB-criteria are unbounded, the proposed algorithms may take exponential time in the number of nodes, and the conjecture asserts that no significantly better algorithm exists unless the corresponding complexity-theoretic barrier fails.