Complement Reducible Uniform Hypergraphs

We investigate a generalization of complement reducible graphs, called co-graphs, for r-uniform hypergraphs. The operations of r-co-hypergraphs are the disjoint union of two given r-co-hypergraphs and the join operation, which inserts all hyperedges of cardinality r between the non-empty vertex subsets of two given r-co-hypergraphs. We show that the primal graphs of r-co-hypergraphs are special co-graphs and that r-co-hypergraphs are closed under complementation of r-uniform hypergraphs. This leads to a method that can determine whether an input hypergraph H is an r-co-hypergraph. If the answer is positive, we find a decomposition tree for H in polynomial time. We give specific formulas for how to compute several hypergraph parameters for r-uniform hypergraphs defined by the disjoint union of two r-uniform hypergraphs and the join of two r-uniform hypergraphs. The considered parameters are the size of a largest stable set, the size of a largest co-stable set, the size of a largest independent set, the size of a largest co-independent set, the size of a smallest vertex cover, the size of a smallest 2-transversal, the size of a smallest dominating set, the strong chromatic number, and the upper chromatic number. This leads to O(n) time algorithms to compute these values on r-co-hypergraphs on n vertices given by a decomposition tree. Further, we conclude relations for the considered parameters restricted to r-co-hypergraphs. Our methods generalize and re-prove several results known for co-graphs.