On the hereditary (p, q)-Helly property of hypergraphs, cliques, and bicliques

We prove several characterizations of hereditary (p, q)-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs, and show that the recognition of hereditary (p, q)-Helly hypergraphs can be solved in polynomial time for fixed p but is co-NP-complete if p is part of the input. We also give several characterizations of hereditary (p, q)-clique-Helly graphs, including one by forbidden induced subgraphs, and prove that the recognition of hereditary (p, q)-clique-Helly graphs can be solved in polynomial time for fixed p and q but is NP-hard if p or q is part of the input. We prove similar results for hereditary (p, q)-biclique-Helly graphs.