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

MITRE COSTA DOURADO; LUCIANO N. GRIPPO; MARTÍN D. SAFE

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

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

0166-218X

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