Some NP-complete problems for hypergraph degree sequences (Q1076694)

Let G be a k-hypergraph. For \(u\in V(G)\) a (k-1)-hypergraph \(G_ u\) is defined as follows: \(V(G_ u)=V(G)-u\), \(E(G_ u)=\{E-u\); \(E\in E(G)\}\). The set \(\{G_ u\); \(u\in V(G)\}\) of hypergraphs is said to be subsumed by G. Using the polynomial transformation from 3-dimensional matching it is shown that for n given (k-1)-hypergraphs (k\(\geq 3)\) \(g_ 1,...,g_ n\) it is NP-complete to decide whether there exists a k-hypergraph G subsuming them even in the case when all \(g_ i\) are simple (i.e. without multiple edges). The second part of the paper is devoted to degree sequences of (hyper)graphs. Let Deg Seq(g)\(=\{\deg (u)\); \(u\in V(g)\}\) be a degree sequence of a graph g. The following problem ''Given Deg Seq(g\({}_ i)\) of graphs \(g_ i\), is there a hypergraph G such that the subsumed graphs \(G_ i\) satisfy Deg Seq(g\({}_ i)=Deg Seq(G_ i)\), \(i=1,...,n?''\) is shown to be NP-complete even if \(g_ i\) are supposed to be simple. Finally the NP-completeness of the following problem ''Given degree sequence \(d=(d_ 1,...,d_ n)\), is d a degree sequence of a simple 3- hypergraph G?'' is left open. Recall that for a hypergraph G, \(u\in V(G)\), deg(u) is the number of edges of the subsumed \(G_ u\).