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

CREATORKazuhiro Kurita, Kevin Mann
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-07528

Browse the full library · About the Tower of Babel