On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
摘要
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 \(\textsf {P}= \textsf {NP}\) , and the s-t hyperpath enumeration is at least as hard as the minimal transversal enumeration, even if a directed hypergraph is BF-hypergraph. As a positive result, s-t hyperpath enumeration for a B-hypergraph can be solved in polynomial delay by backtracking.