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

MITRE C. DOURADO; GRIPPO, LUCIANO N.; MARTÍN DARÍO SAFE

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2023 vol. 330 p. 56 - 77

0166-218X

A family of sets is (p,q)-intersecting if every nonempty subfamily of p or fewer sets has at least 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 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 is part of the input. In addition, we generalize the characterization of (p,q)-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 and 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 -biclique-Helly graphs and hereditary -biclique-Helly graphs which are analogous to those for (p,q)-clique-Helly and hereditary (p,q)-clique-Helly graphs.