| Abstrakt: | This thesis gives an overview of the edge covering problems in hypergraphs. We explore the complexity properties of the vertices and edges covering a hypergraph by subhypergraphs of different types. We consider the covering by clique hypergraphs, split hypergraph, and threshold hypergraphs. In total we prove NP-completness of 6 problems. We especially focus on the problem of covering by threshold hypergraphs, which has applications in learning theory. We give a reduction from the clique covering problem, so proving NP-hardness of this problem will imply NP-hardness of the problem of covering by threshold hypergraphs. Moreover, we propose a generalization of the concept of Dilworth number of a graph to hypergraphs. We give a polynomial algorithm for computation of this number. We prove that the Dilworth number gives an upper bound for some important parameters like diameter and domination number of a hypergraph.
|
|---|