Set graphs. II. Complexity of set graph recognition and similar problems

Our approach in fact allows us to also show that the counting variants of the above problems are #P-complete, and prove similar complexity results for problems related to a generalization of extensional acyclic digraphs, the so-called hyper-extensional digraphs, which were proposed by Aczel to describe hypersets. Our proofs are based on reductions from variants of the Hamiltonian Path problem. We also consider a variant of the well-known notion of a separating code in a digraph, the so-called open-out-separating code, and show that it is NP-complete to determine whether an input extensional acyclic digraph contains an open-out-separating code of given size.