Hypergraph traversal revisited: Cost measures and dynamic algorithms (Q4218092)

A directed hypergraph is defined in this paper by a set of nodes and a set of directed hyperedges, where each hyperedge connects a set of source nodes to a target node. Also the notion of hyperpath is defined---it is a generalization of the notion of path for directed graphs. There are several different notions that all generalize the notion of ``length'' of a path in a directed graph. For several of these ``length''-notions for directed hypergraphs, the problem of finding an optimal hyperpath is NP-complete. In this paper, a general view is taken to these notions and a study is made to the intrinsic complexity of finding optimal hyperpaths under several measures of optimality. It is shown that all notions that are cycle unbounded or 1-cycle-convergent have polynomial time algorithms. The notions of cycle unbounded or 1-cycle-convergent basically say that there is an optimal hyperpath without a generalized cycle or with at most one generalized cycle. For the entire collection see [Zbl 0895.00049].