Fixed-Parameter Tractability of $t$-Uniform Hypergraphicality
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.08523
curl -X POST /api/v1/records/arxiv/2606.08523/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.08523/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'