2025/07/10 by Kazuhiro Kurita, Kevin Mann, Kurita, Kazuhiro +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2507.07528
openalex publication_date 2025/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we address the enumeration of (induced) s-t paths and minimal s-t separators. These problems are some of the most famous classical enumeration problems that can be solved in polynomial delay by simple backtracking for a (un)directed graph. As a generalization of these problems, we consider the (induced) s-t hyperpath and minimal s-t separator enumeration in a directed hypergraph. We show that extending these classical enumeration problems to directed hypergraphs drastically changes their complexity. More precisely, there are no output-polynomial time algorithms for the enumeration of induced s-t hyperpaths and minimal s-t separators unless P = NP, and if there is an output-polynomial time algorithm for the s-t hyperpath enumeration, then the minimal transversal enumeration can be solved in output polynomial time even if a directed hypergraph is BF-hypergraph. Since the existence of an output-polynomial time algorithm for the minimal transversal enumeration has remained an open problem for over 45 years, it indicates that the s-t hyperpath enumeration for a BF-hypergraph is not an easy problem. As a positive result, the s-t hyperpath enumeration for a B-hypergraph can be solved in polynomial delay by backtracking.