On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
Kazuhiro Kurita, Kevin Mann · 2025
Read On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs by Kazuhiro Kurita, Kevin Mann (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-07528.txt.
Description
Kazuhiro Kurita and Kevin Mann show that two classic listing problems turn hard when graphs grow hyperedges, in a 2025 paper. Listing all paths between two points, and all minimal ways to cut them apart, is easy to do steadily in ordinary graphs. In directed hypergraphs, where an edge can join many points at once, the authors prove no method can list the answers with time tied to the output size, unless P equals NP.
One narrow family still yields to backtracking, which they note with care. The results redraw the border between the listable and the wild for network theorists and database designers alike.
Catalog record
| CREATOR | Kazuhiro Kurita, Kevin Mann |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-07528