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

Martin Milanič, Romeo Rizzi, Alexandru I. Tomescu

A graph $G$ is said to be a `set graph' if it admits an acyclic orientation that is also `extensional', in the sense that the out-neighborhoods of its vertices are pairwise distinc…