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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs

  • Kazuhiro Kurita,
  • Kevin Mann

摘要

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.