Instruction Set and Language for Hypergraphs

arXiv:2607.10194v2 Announce Type: replace-cross Abstract: We present IsalHG, a method for representing the structure of any finite, connected hypergraph of bounded hyperedge arity as a string over a compact instruction alphabet Sigma_{HG}. The encoding is executed by a small virtual machine comprising a sparse hypergraph, a circular doubly-linked list (CDLL) of node references, and k traversal pointers, where k bounds the hyperedge arity. Instructions either move a pointer through the CDLL or insert a hyperedge, optionally together with new nodes, into the hypergraph. Every string over Sigma_{HG} decodes to a valid hypergraph; the alphabet is closed. A greedy HypergraphToString (h2s) algorithm encodes any connected hypergraph into a string; a backtracking variant seeded at nodes of lexicographically maximal structural tuple produces a canonical string w^{*}, which we conjecture to be a complete isomorphism invariant. Canonical-string equality then decides hypergraph isomorphism natively, without the standard reduction to the Levi incidence graph followed by a graph-isomorphism engine. We verify the round-trip property s2h(h2s(H)) ong H on 150 connected random uniform hypergraphs and on named combinatorial designs, and we benchmark the canonical algorithm against the three practically available exact baselines -- nauty, Traces, and bliss operating on the 2-coloured Levi graph -- across a (n, c) grid with ten seeds per cell. All four methods agree on every one of 600 isomorphism verdicts, consistent with the completeness conjecture. On wall-clock time the Levi baselines dominate every tested cell by three to five orders of magnitude (geometric-mean ratio 311imes to 117{,}672imes), which we report as measured. We contribute the representation framework, a conjecture of canonical completeness, and the first native-versus-Levi benchmark for hypergraph isomorphism.

Source: arXiv cs.AI | 2026-08-11