{"id":"arxiv/2606.08523","url":"https://arxiv.org/abs/2606.08523","tags":["math.CO","cs.CC","cs.DM"],"score":0,"title":"Fixed-Parameter Tractability of $t$-Uniform Hypergraphicality","domain":"math.CO","source":"arxiv","authors":["Riley Brown","Istvan Miklos"],"reviews":0,"subject":"math.CO","summary":"We study the $t$-uniform hypergraphicality problem under a compressed representation of the degree sequence. Instead of listing all vertex degrees explicitly, the input consists of pairs $$ (δ_1,n_1),\\dots,(δ_k,n_k), $$ meaning that exactly $n_i$ vertices have degree $δ_i$. Thus the parameter $k$ denotes the number of distinct degrees. Although deciding $t$-hypergraphicality is NP-complete for every fixed $t>2$, we prove that the problem is fixed-parameter tractable parameterized by $(k,t)$. Our result shows that tractability extends substantially beyond previously known bounded-range…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-07","reactions":{}}