Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Set graphs. II. Complexity of set graph recognition and similar problems   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 distinct. Equivalently, a set graph is the underlying
graph of the digraph representation of a hereditarily finite set. In this
paper, we continue the study of set graphs and related topics, focusing on
computational complexity aspects. We prove that set graph recognition is
NP-complete, even when the input is restricted to bipartite graphs with exactly
two leaves. The problem remains NP-complete if, in addition, we require that
the extensional acyclic orientation be also `slim', that is, that the digraph
obtained by removing any arc from it is not extensional. We 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.

16
The categories of this paper are: stat
10
The categories of this paper are: q-bio
31
The categories of this paper are: ao-sci
3
The categories of this paper are: physics
37
The categories of this paper are: supr-con
26
The categories of this paper are: bayes-an
24
The categories of this paper are: dg-ga
29
The categories of this paper are: funct-an
12
The categories of this paper are: nucl-th
2
The categories of this paper are: math
36
The categories of this paper are: cmp-lg
15
The categories of this paper are: nucl-ex
27
The categories of this paper are: comp-gas
35
The categories of this paper are: mtrl-th
25
The categories of this paper are: patt-sol
28
The categories of this paper are: alg-geom