Linear connectivity problems in directed hypergraphs

摘要

We introduce a notion of hyperconnection (formally called L-hyperpath) between vertices in a directed hypergraph and relate this notion to existing notions of hyperpaths in directed hypergraphs. We show that some interesting questions in problem domains such as distributed secret sharing and routing in packet filtered networks are basically questions about the existence of L-hyperpaths in directed hypergraphs. We study the computational complexity of problems related to L-hyperpaths and the L-cyclomatic number of directed hypergraphs (the minimum number of hyperedges that need to be deleted to make a directed hypergraph free of L-hypercycles). We prove that the L-hyperpath existence problem, the L-cyclomatic number problem, the minimum L-cyclomatic set problem, and the minimal L-cyclomatic set problem are each complete for the complexity class NP, (Σ{sub}2){sup}p, (∏{sub}2){sup}p, and DP, respectively.