{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreifvdhgns3czlgnurc53gbtvshoj6hulxuafdla4t5mbiegxct4b7u",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mj4ql5x4cbb2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.08278v1",
  "publishedAt": "2026-04-10T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Marco Bressan",
    "Stefano Clemente",
    "Giacomo Fumagalli"
  ],
  "textContent": "**Authors:** Marco Bressan, Stefano Clemente, Giacomo Fumagalli\n\nWe study the problem of counting $k$-\\emph{hyper}graphlets, an interesting but surprisingly ignored primitive, with the aim of understanding if efficient algorithms exist. To this end we consider \\emph{color coding}, a well-known technique for approximately counting $k$-graphlets in graphs. Our first result is that, on hypergraphs, color coding encounters a \\emph{quadratic barrier}: under the Orthogonal Vector Conjecture, no implementation of it can run in time sub-quadratic in the size of the input. We then introduce a simple property, $(α,β)$-niceness, that hypergraphs from real-world datasets appear to satisfy for small values of $α$ and $β$. Intuitively, an $(α,β)$-nice hypergraph can be split into two sub-hypergraphs having respectively rank at most $α$ and degree at most $β$. By applying different techniques to each sub-hypergraph and carefully combining the outputs, we show how to run color coding in time $2^{O(k)} \\cdot \\big(2^β|V| + α^k |E| + α^2 β\\size{H}\\big)$, where $H=(V,E)$ is the input hypergraph. Afterwards, we can sample colorful $k$-hypergraphlets uniformly in expected $k^{O(k)} \\cdot (β^2+\\ln |V|)$ time per sample. Experiments on real-world hypergraphs show that our algorithm neatly outperforms the naive quadratic algorithm, sometimes by more than an order of magnitude.",
  "title": "Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It"
}