On the strong \(p\)-Helly property (Q2482102)

The hypergraph \(\mathcal H\) is called \textit{\((p,q)\)-intersecting} if any \(p\) edges have at least \(q\) common points. It is \textit{\((p,q,s)\)-Helly} if every \((p,q)\)-intersecting partial hypergraph of it has an \(s\)-core. (That is if a subset \(\mathcal E\) of the edges of \(\mathcal H\) is \((p,q)\)-intersecting, then there are \(s\) points in common in the edges of \(\mathcal E\). The particular case \((2,1,1)\)-Helly coincides with the usual notion of Helly hypergraphs.) Finally the hypergraph is \textit{strong \(p\)-Helly} if for every edge-subset \(\mathcal E\) contains at most \(p\) edges s.t. their intersection coincides with the complete intersection of all edges in \(\mathcal E\). One of the main results of this nice paper is a structural characterization of strong \(p\)-Helly hypergraphs, which in turn provides an algorithm to recognize such hypergraphs. The algorithm has polynomial time-complexity for fixed \(p\)'s. In contrast the recognition problem is in \textit{co-NP} for arbitrary \(p.\) The paper also studies some closely related problems.