{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidluswbihjhnewuwr5rxpdsfux2lt7jceolctqyijvckft2hfxwhm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mglxm4mn5wm2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.06402v1",
  "publishedAt": "2026-03-09T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Martin Schirneck"
  ],
  "textContent": "**Authors:** Martin Schirneck\n\nThe transversal rank of a hypergraph is the maximum size of its minimal hitting sets. Deciding, for an $n$-vertex, $m$-edge hypergraph and an integer $k$, whether the transversal rank is at least $k$ takes time $O(m^{k+1} n)$ with an algorithm that is known since the 70s. It essentially matches an $(m+n)^{Ω(k)}$ ETH-lower bound by Araújo, Bougeret, Campos, and Sau [Algorithmica 2023] and Dublois, Lampis, and Paschos [TCS 2022]. Many hypergraphs seen in practice have much more edges than vertices, $m \\gg n$. This raises the question whether an improvement of the run time dependency on $m$ can be traded for an increase in the dependency on $n$. Our first result is an algorithm to recognize hypergraphs with transversal rank at least $k$ in time $O(Δ^{k-2} mn^{k-1})$, where $Δ\\le m$ is the maximum degree. Our main technical contribution is a ``look-ahead'' method that allows us to find higher-order extensions, minimal hitting sets that augment a given set with at least two more vertices. We show that this method can also be used to enumerate all minimal hitting sets of a hypergraph with transversal rank $k^*$ with delay $O(Δ^{k^*-1} mn^2)$. We then explore the possibility of further reducing the running time for computing the transversal rank to $\\textsf{poly}(m) \\cdot n^{k+O(1)}$. This turns out to be equivalent to several breakthroughs in combinatorial algorithms and enumeration. Among other things, such an improvement is possible if and only if $k$-conformal hypergraphs can also be recognized in time $\\textsf{poly}(m) \\cdot n^{k+O(1)}$, and iff the maximal hypercliques/independent sets of a uniform hypergraph can be enumerated with incremental delay.",
  "title": "Transversal Rank, Conformality and Enumeration"
}