On the generalized Helly property of hypergraphs, cliques, and bicliques

Abstract

A family of sets is (p,q)-intersecting if every nonempty subfamily of p or fewer sets has at least q elements in its total intersection. A family of sets has the (p,q)-Helly property if every nonempty (p,q)-intersecting subfamily has total intersection of cardinality at least q. The (2,1)-Helly property is the usual Helly property. A hypergraph is (p,q)-Helly if its edge family has the (p,q)-Helly property and hereditary (p,q)-Helly if each of its subhypergraphs has the (p,q)-Helly property. A graph is (p,q)-clique-Helly if the family of its maximal cliques has the (p,q)-Helly property and hereditary (p,q)-clique-Helly if each of its induced subgraphs is (p,q)-clique-Helly. The classes of (p,q)-biclique-Helly and hereditary (p,q)-biclique-Helly graphs are defined analogously. In this work, we prove several characterizations of hereditary (p,q)-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. On the algorithmic side, we give an improved time bound for the recognition of (p,q)-Helly hypergraphs for each fixed q and show that the recognition of hereditary (p,q)-Helly hypergraphs can be solved in polynomial time if p and q are fixed and co-NP-complete if p is part of the input. In addition, we generalize the characterization of p-clique-Helly graphs in terms of expansions to (p,q)-clique-Helly graphs and give different characterizations of hereditary (p,q)-clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of (p,q)-clique-Helly graphs and prove that the recognition problem of hereditary (p,q)-clique-Helly graphs is polynomial-time solvable for p and q fixed and NP-hard if p or q is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (p,q)-biclique-Helly graphs and hereditary (p,q)-biclique-Helly graphs which are analogous to those for (p,q)-clique-Helly and hereditary (p,q)-clique-Helly graphs.