Complexity aspects of the Helly property: graphs and hypergraphs (Q1960293)

A family of sets has the \(k\)-Helly property iff each finite subfamily, of which every \(k\) members have nonempty intersection, has a common element. This originates in Helly's theorem of 1923 asserting that the family of convex sets in \(\mathbb{R}^n\) has the \((n+1)\)-Helly property. This survey, based upon 106 references, summarizes results on the \(k\)-Helly property and on variants of it concerning graphs and hypergraphs. It focusses especially on recognition algorithms and their complexity for families of graphs and of hypergraphs having some special Helly property. A table of 33 entries lists the complexity results of these algorithms, some being NP-hard and some NP-complete.