Characterization and recognition of generalized clique-Helly graphs (Q2462382): Difference between revisions

For given \(p\geq 1\), \(q\geq 0\) a family of sets \(\mathcal F\) is \((p,q)\)-intersecting if every subfamily \(\mathcal F'\subseteq \mathcal F\) consisting of \(p\) or less members has total intersection cardinality at least \(q\). A family of sets \(\mathcal F\) is \((p,q)\)-Helly if every \((p,q)\)-intersecting subfamily \(\mathcal F'\subseteq \mathcal F\) has total intersection cardinality at least \(q\). A graph \(G\) is \((p,q)\)-clique-Helly if its family of (maximal) cliques is \((p,q)\)-Helly. This generalizes the notion of the Helly property and the clique-Helly graphs which correspond to the case when \(p=2\), \(q=1\). A characterization of \((p,q)\)-clique-Helly graphs is given. It is shown that for fixed \(p,q\) a polynomial-time recognition algorithm exists while for a variable \(p\) or \(q\) the recognition of \((p,q)\)-clique-Helly graphs is NP-hard.