论文标题
查找$（s，d）$ - F-Hypergraphs中的HyperNetworks是NP-HARD
Finding $(s,d)$-Hypernetworks in F-Hypergraphs is NP-Hard
论文作者
论文摘要
我们考虑计算$（s，d）$ - 超级f-hypergraph中的超级net工作的问题。这是在定向超图中引起的基本计算问题，并且是解决可及性和冗余问题的基本步骤。以前在通用的定向超图（包含循环）的背景下探索了这个问题，在该上下文中，它是np-hard和无环b-hypergraphs，可以在其中实现线性时间算法。令人惊讶的是，我们发现对于无环F-Hypergraphs，问题是NP-HARD，这也意味着在BF Hypergraphs中很难。考虑到F Hypergraphs和B-Hypergraphs起初似乎相互对称，这是一个惊人的复杂性边界。我们提供了复杂性的证明，并解释了为什么两类的定向超图之间存在基本不对称性。
We consider the problem of computing an $(s,d)$-hypernetwork in an acyclic F-hypergraph. This is a fundamental computational problem arising in directed hypergraphs, and is a foundational step in tackling problems of reachability and redundancy. This problem was previously explored in the context of general directed hypergraphs (containing cycles), where it is NP-hard, and acyclic B-hypergraphs, where a linear time algorithm can be achieved. In a surprising contrast, we find that for acyclic F-hypergraphs the problem is NP-hard, which also implies the problem is hard in BF-hypergraphs. This is a striking complexity boundary given that F-hypergraphs and B-hypergraphs would at first seem to be symmetrical to one another. We provide the proof of complexity and explain why there is a fundamental asymmetry between the two classes of directed hypergraphs.
