Some NP-complete problems for hypergraph degree sequences
type: Item
instance of: scholarly article
title: Some NP-complete problems for hypergraph degree sequences
zbMATH Open document ID: 0594.05051
DOI: 10.1016/0166-218X(86)90028-4
author: Charles J. Colbourn
author: William Kocay
author: D. R. Stinson
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: 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\).
reviewed by: Mirko Křivánek
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3954970
zbMATH Keywords: consistent numbering
zbMATH Keywords: k-hypergraph
zbMATH Keywords: degree sequences
MaRDI profile type: Publication
cites work: Degree multisets of hypergraphs
cites work: Embedding partial Steiner triple systems is NP-complete
cites work: Q3287781
cites work: Q4198056
cites work: On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
cites work: Q5592263
cites work: Combinatorial Properties of Matrices of Zeros and Ones
full work available at URL: 0166-218x(86)90028-4
OpenAlex ID: W1969063419
Recommended article: The polytope of degree sequences of hypergraphs
Recommended article: Q3340895
Recommended article: Hypergraphic Degree Sequences are Hard
Recommended article: On the Degree Sequences of Uniform Hypergraphs
Recommended article: Q5167708
Recommended article: An extremal problem on degree sequences of graphs
Recommended article: Q3826607
Recommended article: Solution to a problem on degree sequences of graphs
Recommended article: Foundations of Software Science and Computation Structures
Recommended article: Asymptotic Enumeration of Hypergraphs by Degree Sequence
description: scientific article; zbMATH DE number 3954970