On the strong p-Helly property

DOI10.1016/J.DAM.2007.05.047MaRDI QIDQ2482102zbMATH OpenOpenAlexFDO

Authors Mitre C. Dourado, Fábio Protti, Jayme L. Szwarcfiter

Publication date 16 April 2008

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2007.05.047

computationally complexity hereditary clique-Helly graphs strong Helly-property

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65)

Review text

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.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: On the strong \(p\)-Helly property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482102)