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

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

Fortaleza

Simposio; Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS); 2015

We prove several characterizations of hereditary (p, q)-Helly hypergraphs, includ- ing 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 characteriza- tions 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.