4 papers · 1 filter
Fixed-Parameter Tractability of -Uniform Hypergraphicality
Riley Brown, Istvan Miklos
We study the -uniform hypergraphicality problem under a compressed representation of the degree sequence. Instead of listing all vertex degrees explicitly, the input consists of…
On the Complexity of Bipartite Degree Realizability
István Miklós
We study the \emph{Bipartite Degree Realization} (BDR) problem: given a graphic degree sequence , decide whether it admits a realization as a bipartite graph. While bipartite re…
A complete dichotomy theorem on the sparse -Uniform Hypergraphicality Problem
István Miklós, Miklós Ruszinkó, Bogdán Zavalnij
We prove a complete dichotomy theorem for the parameterized sparse -uniform hypergraphic degree sequence problem, $\mathrm{sparse}\text{-}t\text{-}\mathrm{uni}\text{-}\mathrm{HD…
A dichotomy theorem on the complexity of 3-uniform hypergraphic degree sequence graphicality
Sara Logsdon, Arya Maheshwari, István Miklós +1
We present a dichotomy theorem on the parameterized complexity of the 3-uniform hypergraphicality problem. Given , the parameterized 3-uniform Hypergraphic Degree…