Covering edges of a hypergraph: complexity and applications

Chapter 1 Introduction 1.1 Motivation The complexity properties of the covering problems in graphs have been ex- tensively studied by many authors (see [GJ79] for a survey). In recent years, Aizenstein et al. [AHHP98] has proved that efficient learnability in one of the on-line learning models is related to the representation problem, e.g. to decide if a given Boolean formula in DNF has a representation of some type, for example as a union of k linearly separable functions. NP-hardness of representation problem for some concept class implies negative results for its efficient learnability in this model. Such results are given for many con- cept classes, however for an important concept class - the class of unions of two linearly separable functions, the status of the representation problem is unknown. The covering problem by threshold hypergraphs can be easily transformed to the representation problem of unions of two linearly separa- ble functions. This thesis focuses on the complexity properties of covering problems in hypergraphs. These problems were not explored elsewhere, and their applications to the learning theory are a good motivation for a deeper examination of these problems. 1.2 Summary of thesis contributions We prove NP-completness of the following covering problems for r-uniform hypergraphs: 9