On the strong \(p\)-Helly property (Q2482102): Difference between revisions
From MaRDI portal
Latest revision as of 20:33, 27 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the strong \(p\)-Helly property |
scientific article |
Statements
On the strong \(p\)-Helly property (English)
0 references
16 April 2008
0 references
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.
0 references
strong Helly-property
0 references
hereditary clique-Helly graphs
0 references
computationally complexity
0 references