Abstract :
[en] 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.
Funding text :
This project has been made possible in part by a grant from the Cisco University Research Program Fund , an advised fund of Silicon Valley Foundation grant number 1318167 .The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Miller reports financial support was provided by Cisco University Research Program Fund, grant number 1318167.This project has been made possible in part by a grant from the Cisco University Research Program Fund, an advised fund of Silicon Valley Foundation grant number 1318167. We wish to express our sincere gratitude to the anonymous reviewers for their feedback and valuable suggestions, which have had a profound impact in enhancing the quality of this manuscript.
Scopus citations®
without self-citations
0
