Complexity aspects of the Helly property: graphs and hypergraphs

MaRDI QIDQ1960293zbMATH OpenFDO

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

Publication date 13 October 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/222810, http://www.emis.de/journals/EJC/Surveys/index.html

zbMATH Keywords

computational complexityHelly propertyNP-completeNP-hardrecognition algorithm

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph algorithms (graph-theoretic aspects) (05C85) Helly-type theorems and geometric transversal theory (52A35) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• The colorful Helly theorem and general hypergraphs
• Complexity aspects of generalized Helly hypergraphs
• The colorful Helly property for hypergraphs
• scientific article; zbMATH DE number 1409177
• On the generalized Helly property of hypergraphs, cliques, and bicliques

Cited in

(23)

• On the Helly property working as a compactness criterion on graphs
• On the clique behavior and Hellyness of the complements of regular graphs
• On the computational complexity of the Helly number in the \(P_3\) and related convexities
• Characterization of classical graph classes by weighted clique graphs
• On the generalized Helly property of hypergraphs, cliques, and bicliques
• The colorful Helly property for hypergraphs
• The problem of determining the Helly dimension of a graph
• A unified approach to recognize squares of split graphs
• The complexity of Helly-B₁ EPG graph recognition
• Helly's property for n-cliques and the degree of a graph
• On neighborhood-Helly graphs
• scientific article; zbMATH DE number 4101253 (Why is no real title available?)
• Split clique graph complexity
• The colorful Helly theorem and general hypergraphs
• scientific article; zbMATH DE number 1491621 (Why is no real title available?)
• scientific article; zbMATH DE number 5064049 (Why is no real title available?)
• Domination in digraphs and their direct and Cartesian products
• A story of diameter, radius, and (almost) Helly property
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Helly and strong Helly numbers of B_k-EPG and B_k-VPG graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• The Helly property on subfamilies of limited size
• The Helly property and satisfiability of Boolean formulas defined on set families

This page was built for publication: Complexity aspects of the Helly property: graphs and hypergraphs

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