Complexity Aspects of the Helly Property: Graphs and Hypergraphs^{∗}

Mitre C. Dourado^{1}, Fábio Protti^{2} & Jayme L. Szwarcfiter^{3}

1ICE - Universidade Federal Rural do Rio de Janeiro and NCE - UFRJ

2Instituto de Matemática - Universidade Federal do Rio de Janeiro

3Instituto de Matemática, NCE and COPPE - Universidade Federal do Rio de Janeiro

Caixa Postal 2324, Rio de Janeiro, RJ, Brasil

{mitre — jayme}@nce.ufrj.br, fabiop@dcc.ufrj.br

Submitted: Nov 13, 2006; Accepted: Jun 5, 2009; Published: Jun 12, 2009

Abstract

In 1923, Eduard Helly published his celebrated theorem, which originated the well known Helly property. A family of subsets has the Helly property when every subfamily thereof, formed by pairwise intersecting subsets, contains a common element. Many generalizations of this property exist which are relevant to some fields of mathematics, and have several applications in computer science. In this work, we survey complexity aspects of the Helly property. The main focus is on characterizations of several classes of graphs and hypergraphs related to the Helly property. We describe algorithms for solving different problems arising from the basic Helly property. We also discuss the complexity of these problems, some of them leading to NP-hardness results.

Keywords: Computational Complexity, Helly property, NP-complete problems

∗Partially supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq, and Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro - FAPERJ, Brazil.

the electronic journal of combinatorics (2009), #DS17 1

1 Introduction

In 1923, Eduard Helly [27, 65] published the famous theorem which originated the so called Helly property. The theorem asserts that in a d-dimensional euclidian space, if in a finite collection of n > d convex sets any d + 1 sets have a point in common, then there is a point in common to all the sets. This theorem has been extensively studied in distinct parts of mathematics and other areas, such as computer science. In fact, it plays a central role in studies of geometric transversal theory, combinatorial geometry and convexity theory.

A few surveys have been written on the Helly property, as in [31, 48, 57]. The Helly property has been a field of interest within extremal hypergraph theory, as in [101], and other topics of graph theory. For instance, see [44, 102, 103]. There are many extensions of the Helly property. One of its generalizations, the fractional Helly property, is directly related to Alon and Kleitman’s result [4], and is a tool to solve a famous conjecture by Hadwiger and Debrunner [62]

Besides the purely theoretical interest, the Helly property has applications in different areas. For example, in the context of optimization, it has been applied to location problems [41], and generalizes linear programming [5]. In computer science, the Helly property has been used in theory of semantics [11], coding [10], computational biology [93], data bases [50, 51], image processing [25] and, especially, graph and hypergraph theory.

The Helly property has motivated the introduction of several classes of graphs and hypergraphs, e.g., clique-Helly graphs, disk-Helly graphs, Helly circular-arc graphs, Helly hypergraphs, among others. Some of these classes are described in this survey. In general, the Helly property in graphs and hypergraphs corresponds to some restriction imposed on certain subsets of vertices or edges. Besides of the definition of the classes directly employing the Helly property, it has been a useful, natural tool in other topics of graph theory, for example intersection graph and clique graph theory.

In this work, we survey some of the results on the Helly property, from the complexity point of view. Our purpose is to describe algorithms and complexity results for many structural algorithmic problems related to the Helly property and some of its generalizations. In addition, we include new proposals of algorithms for some specific problems, and formulate the main structural characterizations which are the basis of the algorithms.

Following are some definitions and notation used throughout this paper.

A hypergraph H is an ordered pair (V (H), E(H)) where V (H) = {v_{1}, …, v_{n}} is a finite set of vertices and E(H) = {E_{1}, …, E_{m}} is a set of nonempty hyperedges E_{i} ⊆ V (H). Where there is no ambiguity, we will denote the number of vertices and hyperedges of a hypergraph H by n and m, respectively. Since the Helly property and most variations considered in this work deal with hyperedges, isolated vertices are not relevant and can be dropped. Hence, unless otherwise stated, we assume V (H) = ⋃_{E_{i}∈E(H)}E_{i}.

We say that H is a k-hypergraph if |E(H)| = k, a k^{−}-hypergraph if |E(H)| ≤ k, and a k^{+}-hypergraph if |E(H)| ≥ k. We use the same notation for any term standing for a set; for example, given a set S, write that S is k-set whenever |S| = k.

The rank r(H) of a hypergraph H is the maximum cardinality among the hyperedges of H. A hypergraph H′ is a partial hypergraph of H if E(H′) ⊆ E(H), and a subhypergraph of H induced by V′ ⊆ V (H) if H′ contains exactly the hyperedges E_{i} ∩V′ ≠ ∅ for 1 ≤ i ≤ m.

The core of H is defined as core(H) = E_{1} ∩ E_{2} ∩ … ∩ E_{m}. We say that H is (p, q)- intersecting if every partial p^{−}-hypergraph of H has a q^{+}-core. We employ the terms intersecting and p-intersecting meaning (2, 1)-intersecting and (p, 1)-intersecting, respectively.

Two hypergraphs H, H′ are isomorphic if there exists a bijection f : V (H) → V (H′) such that:

{v_{1}, …, v_{p}} ∈ E(H) ⟺ {f(v_{1}), …, f(v_{p})} ∈ E(H′).

Given a hypergraph H, we construct the dual hypergraph H^{∗} of H creating one vertex e_{j} in V (H^{∗}) for each hyperedge E_{j} ∈ E(H), and one hyperedge A_{i} in E(H^{∗}) for each vertex a_{i} ∈ V (H), defined as A_{i} = {e_{j} : a_{i} ∈ E_{j}}.

A hypergraph H is r-uniform when every hyperedge of H contains exactly r vertices. Let r, n be integers, 1 ≤ r ≤ n. We define the r-complete hypergraph K_{n}^{r} to be a hypergraph consisting of all the r-subsets of an n-set.

A graph is a 2-uniform hypergraph. Usually, a graph is denoted by G. A hyperedge and a partial hypergraph of a graph G are respectively called edge and subgraph of G. A spanning subgraph of G is a subgraph with vertex set V (G), and the subgraph of G induced by V′, denoted by G[V′], is the maximal subgraph of G with vertex set V′. Two vertices u and v forming an edge of G are adjacent vertices or neighbors in G, and we denote such an edge by uv. The open neighborhood of a vertex v, denoted by N(v), is the set formed by the neighbors of v. The closed neighborhood of v is N[v] = N(v) ∪ {v}. The disk of radius k and center v is the set of vertices whose distance to v is not larger than k. A vertex v is universal in G if N[v] = V (G).

A path is a sequence of distinct vertices v_{1}, …, v_{q}, q ≥ 1, such that v_{i}v_{i+1} ∈ E(G), for 1 ≤ i ≤ q − 1. If, furthermore, q ≥ 3 and v_{q}v_{1} ∈ E(G), this sequence is a cycle. A chord of a cycle C is any edge joining two non-consecutive vertices in C. The distance between two vertices is the number of edges of a minimum path joining them.

A complete set (independent set) is a subset of pairwise adjacent (nonadjacent) vertices. A bipartite set is a subset B ⊆ V (G) which can be partitioned into B = V_{1} ∪ V_{2}, where V_{1}, V_{2} are nonempty independent sets. If every v_{i} ∈ V_{1} and v_{j} ∈ V_{2} are adjacent, then B is a complete bipartite set. A clique of G is a maximal complete set, and a biclique is a maximal complete bipartite set. A (complete) bipartite graph is a graph induced by a (complete) bipartite set. A graph is K_{r}-free if it does not contain r-complete sets as subgraphs.

A graph is a tree if there exists exactly one path between every pair of vertices thereof. A graph G is chordal if every cycle of G with at least 4 vertices has a chord. The complement of a graph G, denoted by \overline{G}, has V (G) as vertex set, and uv ∈ E(\overline{G}) if and only if uv ∉ E(G). A graph is perfect if it does not contain an odd cycle or a complement of an odd cycle, with at least 5 vertices, as an induced subgraph.

The clique hypergraph of G, denoted by C(G), is the hypergraph formed by the cliques of G. Given a hypergraph H, the intersection graph or line graph of H is the graph containing one vertex for each hyperedge of H, and two vertices are adjacent if the corresponding hyperedges intersect. The clique graph K(G) of G is the intersection graph of the clique hypergraph of G. The i-th iterated clique graph of G, denoted by K^{i}(G), is defined as follows: K^{0}(G) = G and K^{i}(G) = K(K^{i−1}(G)) for i ≥ 1.

The contents of this survey is as follows. Section 2 presents the basic Helly property on hypergraphs, with the description of some classical families of hypergraphs. A test for the Helly property on hypergraphs is also included. Section 3 discusses the basic Helly property on graphs. The commonest Helly classes of graphs are described, together with their characterizations and recognition algorithms. Section 4 considers the p-Helly hypergraphs and a generalization of them, the list p-Helly hypergraphs. Section 5 considers the Helly property on subfamilies of limited size, that is, when the cardinality of the subfamilies to be checked for a common vertex is bounded by a positive integer k. Section 6 contains a generalization of the p-Helly property which considers the cardinality of the intersections, the (p, q, s)-Helly property. Characterizations generalizing classical results on p-Helly hypergraphs and conformal hypergraphs are given; the last one is a new result. This concept is also used to generalize the Helly number of a hypergraph. In Section 7 we apply the (p, q, s)-Helly property to graphs. Characterization and recognition of (p, q)- clique-Helly graphs are presented. Also, the complexity of determining the Helly defect of a graph is discussed. In Section 8 we consider the hereditary Helly property applied to special families of vertices of a graph, such as cliques, disks, bicliques, open and closed neighborhoods. Furthermore, we characterize the hereditary p-Helly property on graphs and hypergraphs. Section 10 contains a summary of the computational aspects of the problems surveyed in this work. In the last section we list some proposed problems.

2 Basic Helly Property on Hypergraphs

In this section, we discuss the basic Helly property on hypergraphs. First, we describe some classical examples of special families of objects satisfying the Helly property. Next, we consider general Helly hypergraphs, and give an algorithm for recognizing this class. Finally, we describe some well known classes of hypergraphs where the Helly property holds.

Relevant references for this section are [12, 13, 15, 24, 43, 83].

2.1 General hypergraphs

A hypergraph H is Helly when every intersecting partial hypergraph of H has a nonempty core. For example, the hypergraph H having V (H) = {1, 2, 3, 4} and E(H) = {{1, 2}, {1, 3}, {1, 4}} is Helly, while if E(H) = {{1, 2}, {1, 3}, {2, 3}} then H is not Helly.

We now give some classical examples of objects satisfying the Helly property. Intervals of a straight line form a Helly family, as it can be easily observed. Another classical example, coming from the Chinese Theorem, expresses a property of arithmetic progressions: let H be the hypergraph having the integers as vertices, and the arithmetic progressions formed by integers as hyperedges (in this case, hyperedges are not finite); then H is Helly. Another commonly employed case of a Helly family is that of subtrees of a tree. The fact that subtrees of a tree are Helly is the basis for many properties of chordal graphs.

From the computational point of view, a central question is to describe a method for recognizing Helly hypergraphs. Let us observe that simply applying the definition would not lead to an efficient method, since the number of intersecting partial hypergraphs could be exponential on the number of vertices.

Problem 2.1 Helly hypergraph INSTANCE: A hypergraph H. QUESTION: Does H satisfy the Helly property?

The following algorithm [12] decides whether a given hypergraph H is Helly.

Algorithm 2.1 [12] (Recognizing Helly hypergraphs): For every triple T of vertices of V (H), construct the partial hypergraph H_{T} of H formed by the hyperedges of H containing at least two of the vertices of T. Then H is Helly precisely when H_{T} has a nonempty core for every triple T.

The above algorithm corresponds to the case p = 2 of the method for deciding if H is p-Helly. Therefore its correctness follows from Theorem 4.2 (see Section 4).

As for the complexity, there are O(n^{3}) partial hypergraphs to be considered. Each one can be constructed and checked in linear time, yielding an overall complexity of

O(n^{3} ∑_{E_{i}∈E(H)}|E_{i}|) = O(n^{4}m).

2.2 Special hypergraphs

We now define some classes of Helly hypergraphs.

Say that H is an interval hypergraph when its vertices can be embedded on a line in such a way that its hyperedges correspond to intervals of the line. An example is given in Figure 1(a).

Figure 1: An interval hypergraph and a hypertree

A hypertree is a hypergraph H such that there exists a tree T with vertex set V (H) where the hyperedges of E(H) induce subtrees in T. See Figure 1(b). Hypertrees are also called arboreal hypergraphs. The dual of a hypertree is a concept employed in the theory of relational databases [50, 51].

The following theorem characterizes hypertrees in terms of the Helly property.

Theorem 2.1 [42, 52, 95] A hypergraph H is a hypertree if and only if H is Helly and its line graph is chordal.

Next, we define more families of hypergraphs based on the following notion. A special cycle of a hypergraph H is a sequence v_{1}E_{1}v_{2}E_{2} … v_{k}E_{k}v_{k+1}, k ≥ 3 and v_{k+1} = v_{1}, where v_{1}, …, v_{k} and E_{1}, …, E_{k} are distinct vertices and hyperedges of H satisfying E_{i} ∩ {v_{1}, …, v_{k}} = {v_{i}, v_{i+1}}. The value k is the length of the cycle.

A hypergraph is balanced if it contains no special cycle of odd length [12] and it is totally balanced if it has no special cycles of any length [79]. Finally, a hypergraph is normal if it is Helly and its line graph is perfect [79].

Theorem 2.2 Normal hypergraphs, hypertrees, balanced, totally balanced, and interval hypergraphs are Helly.

The proof of the above theorem follows from the fact that normal hypergraphs are Helly by definition, balanced hypergraphs are normal [78, 80], and totally balanced hypergraphs are balanced. On the other hand, hypertrees are Helly because the subtrees of a tree satisfy the Helly property, while interval hypergraphs are special hypertrees.

3 Basic Helly Property on Graphs

In the context of graphs, the Helly property has been mainly applied to certain subsets of vertices, such as cliques, disks, open neighborhoods, closed neighborhoods, and bicliques. In general, any of these special families of subsets may or not satisfy the Helly property. In this section, we consider the classes of graphs for which the above families of subsets of vertices do satisfy the Helly property. The clique-Helly graphs are exactly the graphs whose families of cliques satisfy the Helly property. Similarly, we define disk-Helly, open neighborhood-Helly, closed neighborhood-Helly, and biclique-Helly graphs, respectively. Disk-Helly graphs are also called simply Helly graphs. In the definition of these classes, we consider all possible subsets of the corresponding types. For instance, for the clique-Helly graphs, all cliques are taken into account. For the disk-Helly graphs, all disks are considered, for all possible centers and radii. The same principle is valid for the other classes.

We describe characterizations and recognition algorithms for these classes, as well as the containment relations among them. Finally, we consider another class of graphs closely related to the Helly property, the Helly circular-arc graphs.

3.1 Clique-Helly graphs

Clique-Helly graphs have been well studied, mainly in connection with clique graphs. The first reference to them is the following sufficient condition for a graph to be a clique graph.

Theorem 3.1 [63] Every clique-Helly graph is a clique graph.

This theorem has been generalized to an actual characterization of clique graphs, as follows:

Theorem 3.2 [94] A graph G is a clique graph if and only if it contains a family of complete subsets of vertices which covers all its edges and satisfies the Helly property.

The above characterization has not lead so far to a polynomial time algorithm for recognizing clique graphs. In fact, it has been recently proved that recognizing clique graphs is NP-complete [2].

Another result closely related to Theorem 3.1 can be formulated as follows.

Theorem 3.3 [49] The clique graph of a clique-Helly graph is clique-Helly, and every clique-Helly graph is the clique graph of a clique-Helly graph.

Clique-Helly graphs play a key role in the study of iterated clique graphs. Let G and H be graphs. Say that G is convergent to H when K^{i}(G) = K^{i+1}(G) = H, for some i ≥ 0. When H is the one-vertex graph, G is simply convergent. On the other hand, when lim_{i→∞}|V (K^{i}(G))| = ∞, G is a divergent graph. Finally, when K(G) = G, say that G is a self-clique graph.

If G is clique-Helly then K^{i}(G) is again clique-Helly, and, in addition, K^{2}(G) is an induced subgraph of G [49]. The latter implies that divergent graphs cannot be clique-Helly. The study of divergent graphs has both algebraic and geometric connections and has recently attracted much interest. For instance, see [68, 69, 70, 71, 88], among other papers. A general theory for this class is in [72, 85]. Finally, as for self-clique graphs, we can mention that self-clique clique-Helly graphs have been fully characterized [16, 73]. However, little is known about self-clique graphs which are not clique-Helly. A survey on clique graphs appears in [98].

Various other classes of graphs have been defined motivated by clique-Helly graphs, or are closely related to them. See, for instance, [20, 22, 23, 99].

Figure 2: The Hajós Graph

The family of minimal non clique-Helly graphs has been described in [81]. Here, the minimality refers both to induced subgraphs and to intersecting families of cliques.

The smallest graph which is not clique-Helly is the Hajós graph, depicted in Figure 2. In general, in order to recognize clique-Helly graphs, the first idea is to apply the algorithm of Section 2.1, with the aim of checking whether the clique hypergraph of the given graph is Helly. However, since the number of cliques of a graph might be exponential [84], this would not necessarily lead to a polynomial time algorithm.

Problem 3.1 Clique-Helly graph INSTANCE: A graph G. QUESTION: Is G a clique-Helly graph?

However, clique-Helly graphs can be recognized in polynomial time, applying the following concept. Let G be a graph and T a triangle of if. The extended triangle of G relative to T is the subgraph induced in G by the set of all vertices adjacent to at least two vertices of T. The following theorem characterizes clique-Helly graphs.

Theorem 3.4 [40, 97] A graph is clique-Helly if and only if every of its extended triangles contains a universal vertex.

The above theorem leads directly to a polynomial time algorithm for recognizing whether a given graph G is clique-Helly.

Algorithm 3.1 (Recognizing clique-Helly graphs): For every triangle T of G, construct its extended triangle and verify if it contains a universal vertex. Then G is clique-Helly precisely when the answer is positive for every triangle T.

We need O(nm) time to generate all the triangles of G. The computation of the required operations, for each of the triangles, requires O(m). Therefore the overall complexity is O(nm^{2}). This complexity can be reduced by applying matrix multiplication for generating the triangles.

3.2 Disk-Helly graphs

Disk-Helly graphs can also be recognized in polynomial time. Such recognition algorithms have been described in [7, 40]. Disk-Helly graphs have been studied in connection with retracts of a graph, e.g. [6, 8, 64]. This class has also been characterized in terms of convergence, as follows.

Theorem 3.5 [9] A graph is disk-Helly if and only if it is clique-Helly and convergent.

The above theorem completely characterizes convergent graphs which are clique-Helly, implying that such a class can be recognized in polynomial time. In contrast, it is an open problem whether it is even decidable to recognize general convergent graphs.

3.3 Open and closed neighborhood-Helly graphs

Open and closed neighborhood-Helly graphs can also be recognized in polynomial time, by applying Algorithm 2.1, since the size of the neighborhoods is polynomially bounded. The same remark applies for disk-Helly graphs.

The following concept generalizes extended triangles. It has been employed both for characterizing open neighborhood-Helly graphs and biclique-Helly graphs. For a graph G, let S ⊆ V (G), |S| = 3. Denote by B_{S} the family of bicliques of G, each of them containing at least two vertices of S. Let G_{B_{S}} be the subgraph of G formed exactly by the vertices and edges of B_{S}. Write S^{∗} = V (G_{B_{S}}). The induced subgraph of G formed by the vertices of S^{∗} is called an extension of S. Finally, denote by S_{2}^{∗} ⊆ S^{∗} the subset of vertices which are adjacent to at least two vertices of S.

Theorem 3.6 [60] A graph G is open neighborhood-Helly if and only if G contains no triangles, and for every independent set S with three vertices, S^{∗} contains a vertex adjacent to all the vertices of S_{2}^{∗}.

3.4 Biclique-Helly graphs

For biclique-Helly graphs, we need an additional definition. For a graph G, say that a vertex v dominates an edge e when one of the extremes of e either coincides or is adjacent to v. When v dominates every edge of G then v is an edge dominator of G. Biclique-Helly graphs can be characterized as follows.

Theorem 3.7 [60] A graph G is biclique-Helly if and only if G is triangle-free and each of its extensions has an edge dominator.

Problem 3.2 Biclique-Helly graph INSTANCE: A graph G. QUESTION: Is G a biclique-Helly graph?

As for the question of recognizing biclique-Helly graphs, first we remark that unlike neighborhoods and disks, the number of bicliques of a graph is not polynomially bounded, meaning that a direct application of Algorithm 2.1 would not lead to an efficient method. In fact, the number of bicliques of a graph might be exponential on its number of vertices [92]. However, the above theorem can be used to formulate the following polynomial time algorithm. Let G be the given graph.

Algorithm 3.2 [60] (Recognizing biclique-Helly graphs): First, verify whether G has a triangle. If it does then stop, as G is not biclique-Helly. Otherwise, for each 3subset of vertices of G, construct its extension and verify if it contains an edge dominator. Then G is biclique-Helly precisely when the answer is affirmative in all cases.

There are O(n^{3}) extensions to be considered. In order to construct and check each of them, we require O(m). The total complexity is O(n^{3}m). The next result says that a closed neighborhood-Helly graph with no triangles is also open neighborhood-Helly and biclique-Helly.

Theorem 3.8 [58] Let G be a triangle-free graph. If G is closed neighborhood-Helly, then G is open neighborhood-Helly and biclique-Helly.

3.5 Relation among classes

Finally, we relate the Helly classes so far considered in this section. Clearly, clique-Helly graphs contain open neighborhood-Helly and biclique-Helly graphs, because the two last classes are triangle-free (Theorems 3.6 and 3.7) and every triangle-free graph is clique-Helly. Furthermore, if T is a triangle of some graph G and the extended triangle of T does not contain a universal vertex then the closed neighborhoods of the vertices of T contain an

Figure 3: Relations among Helly classes

intersecting subfamily with no common vertex. Consequently, every closed neighborhood-Helly graph is also clique-Helly. On the other hand, it is clear that closed neighborhood-Helly graphs contain disk-Helly graphs. However, open and closed neighborhood-Helly graphs do not contain each other. Clearly, a triangle is closed neighborhood-Helly and not open neighborhood-Helly, whereas the graph C_{4} is open neighborhood-Helly and not closed neighborhood-Helly. See Figure 3, where some minimal graphs are also shown.

3.6 Helly circular-arc graphs

A generalization of intervals of a straight line is to consider arcs of a circle. However, arcs of a circle do not form necessarily a Helly family. For example, a family of three arcs which together cover the circle, and such that none of them contains another one, is not Helly. See Figure 4. In fact, we are interested in the intersection graph G of arcs of a circle, called circular-arc graph. That is, G has a vertex for each arc, and two vertices are adjacent when the corresponding arcs intersect. The family of arcs together with the corresponding circle form a circular-arc model of G. For a circular-arc graph G, if there exists a Helly family of arcs which represents G, then G is a Helly circular-arc graph.

The above definition leads to the following problem.

Figure 4: Non Helly families of arcs

Problem 3.3 Helly circular-arc graph INSTANCE: A graph G. QUESTION: Is G a Helly circular-arc graph?

In order to characterize circular-arc graphs, the following concept is useful. For a (0, 1)-matrix M, say that M has the circular 1’s property on the columns when the 1’s in each column appear consecutively, following the ordering of the lines, considered circularly. The following theorem characterizes Helly circular-arc graphs.

Theorem 3.9 [53] A graph is a Helly circular-arc graph if and only if it admits a clique matrix possessing the circular 1’s property on the columns.

This theorem leads to the following algorithm able to recognize Helly circular-arc graphs. Let G be a graph.

Algorithm 3.3 [53] (Recognizing Helly circular-arc graphs): Find all cliques of G. If G has more than n cliques then stop, as G is not Helly circular-arc. Otherwise, verify if its cliques can be placed in a circular ordering, so that the corresponding clique matrix has the circular 1’s property on its columns. Then G is a Helly circular-arc graph in the affirmative case, otherwise it is not.

Helly circular-arc graphs can contain no more than n cliques, which can be computed in overall O(n^{3}) time, using the algorithm in [87]. Determining whether the graph admits a clique matrix with the circular 1’s property on the columns can also be done within the same bound [53]. Therefore the complexity of the algorithm is O(n^{3}). See [96] for a discussion about this recognition problem.

Recently, a forbidden subgraph characterization for Helly circular-arc graphs has been described, which leads to a linear time recognition algorithm for the class. Furthermore,

Figure 5: A Helly circle graph and two circle models of it.

if a circular-arc model is given as input [67], then the algorithm terminates in O(n) time. Helly circular-arc graphs have been also studied in relation to clique graphs [17, 47] and clique-perfectness [18].

Some special classes of Helly circular-arc graphs have also been studied. Say that a circular-arc model is proper when no arc of it contains another one, and it is a unit model when all arcs have the same size (always assuming that no two arcs share an endpoint). Similarly, a proper (unit) circular-arc graph is one admitting a proper (unit) circular-arc model. A proper (unit) Helly circular-arc model is a model simultaneously proper (unit) and Helly. Finally, a proper (unit) Helly circular-arc graph is a graph admitting a proper (unit) Helly circular-arc model. Clearly, if G is a proper (unit) Helly circular-arc graph then it is both a proper (unit) circular-arc graph and Helly circular-arc graph. However, the converse is not true. Proper Helly and unit Helly circular-arc graphs have been characterized by forbidden induced subgraphs, and linear time recognition algorithms have been described for this class [74, 75].

3.7 Helly circle graphs

A circle graph G is the intersection graph of a family of chords in a circle. The circle together with the corresponding family of chords form a model for G. A model is Helly when the family of chords satisfies the Helly property, and a circle graph is Helly when it admits a Helly model. Figure 5(a) and 5(b) illustrate two distinct models of a same circle graph, shown in Figure 5(c). The first of such models is not Helly, while the second one is Helly, meaning that the graph of Figure 5(c) is a Helly circle graph.

Clearly, in a Helly model of a circle graph, any set of pairwise intersecting chords contains a common point. Of course, this cannot occur if the graph contains an induced diamond, that is, a K_{4} minus an edge. (Figure 6). Consequently, a necessary condition for a circle graph to be Helly is that it cannot contain diamonds. In fact, in [45] it was stated the conjecture that a circle graph is Helly if and only if it does not contain diamonds.

Figure 6: A diamond and a paw.

This conjecture has been recently proved in [30]. A characterization of Helly circle graphs through a system of equalities and inequalities has been described in [46]. Further, in [19] there is a characterization of this class in terms of the existence of a real solution for a certain system of polynomial equations and inequalities.

A circle graph is unit Helly if it admits a Helly circle model, where all chords have the same size. Unit Helly circle graphs form a restricted class of graphs, as shown below. Denote by C_{n}^{∗} the graph obtained from the induced cycle with n vertices by adding an isolated vertex to it.

Theorem 3.10 [19] Let G be a graph. The following assertions are equivalent:

1. G is a unit Helly circle graph;

2. G contains no induced diamond, paw nor C_{n}^{∗}, for n ≥ 3;

3. G is a chordless cycle, a complete graph or a disjoint union of chordless paths.

3.8 Matrices of a graph

Another example of the use of the Helly property is in the characterization of clique matrices of a graph, due to Gilmore. It states that a (0, 1)-matrix with no zero lines is the clique matrix of some graph if and only if the 1’s of any row do not cover the 1’s of another row, while the 1’s of the columns satisfy the Helly property. Biclique matrices of a graph have recently been characterized [59], also in terms of the Helly property.

4 The p-Helly Property

Consider the following generalization of the Helly property. A hypergraph H is p-Helly if every partial p-intersecting hypergraph of H has a nonempty core. In this section we present two characterizations of this concept, one of them leading to a polynomial-time algorithm for recognizing p-Helly hypergraphs when p is fixed.

4.1 k-Conformal hypergraphs

Define the k-section of a hypergraph H to be a hypergraph [H]_{k} whose hyperedges are sets F ⊆ V (H) such that |F | = k and F ⊆ E_{i} ∈ E(H), or |F | < k and F ∈ E(H).

For k ≥ 2, a hypergraph H is k-conformal if every maximal set of V (H), which induces a K_{j}^{k} hypergraph of [H]_{k} for k ≤ j, is a hyperedge of H.

For example, the hypergraph H, where V (H) = {1, 2, 3, 4} and E(H) = {{1, 2}, {1, 3}, {1, 4}} is 2-conformal. However, if E(H) = {{1, 2, 4}, {1, 3, 4}, {2, 3, 4}} then H is not 2-conformal. There is a close relationship between k-conformal and k-Helly hypergraphs.

Theorem 4.1 [13] A hypergraph is k-conformal if and only if its dual is k-Helly.

A generalization of the above theorem, Theorem 6.8, is proved in Section 6.

4.2 Recognition

The following theorem characterizes p-Helly hypergraphs:

Theorem 4.2 [14] A hypergraph H is p-Helly if and only if for every (p + 1)-subset V′ of V (H), the partial hypergraph formed by the hyperedges that contain at least p elements of V′ has a nonempty core.

This theorem leads directly to an algorithm for recognizing whether a given hypergraph H is p-Helly, for p ≥ 2.

Problem 4.1 p-Helly hypergraph, fixed p INSTANCE: A hypergraph H. QUESTION: Is H a p-Helly hypergraph?

Algorithm 4.1 [14] (Recognizing p-Helly hypergraphs): For each (p + 1)-subset V′ of V (H), construct the partial hypergraph H′ formed by the hyperedges of H containing at least p vertices of V′, and verify whether H′ has a nonempty core. Then H is p-Helly precisely when the answer is positive in all cases.

There are O(n^{p+1}) partial hypergraphs to be considered. Each one of these partial hypergraphs as well as its core can be constructed in O(m(n + p)) time. Then the overall complexity of the above algorithm is O(m(n + p)n^{p+1}), that is, polynomial for fixed p. As we shall see in Section 6, this problem is NP-hard for the case when p is variable, since it is a particular case of Problem 6.3.

Observe that if a hypergraph is p-Helly, then it is (p + 1)-Helly. From this fact, one can ask, for a given hypergraph H, what is the least number h for which H is h-Helly. This number is known as the Helly number of the hypergraph [66]. The Subsection 6.4 is dedicated to the Helly number and related topics.

What happens to the complexity of checking the p-Helly property if we relax the definition, in the sense that some specific partial p-intersecting hypergraphs with an empty core are allowed?

Let H be a hypergraph and ℒ be a list of partial p-hypergraphs of H. Say that H is list p-Helly relative to ℒ if every partial p-intersecting hypergraph H′ of H satisfies the following condition:

- if all the partial p-hypergraphs of H′ are listed in ℒ, then core(H′) ≠ ∅.

In particular, if ℒ is the list of all the partial p-hypergraphs of H, then H is list p-Helly if and only if H is p-Helly.

Problem 4.2 List p-Helly hypergraph, fixed p ≥ 2 INSTANCE: A hypergraph H and a list ℒ of partial p-hypergraphs of H. QUESTION: Is H list p-Helly relative to ℒ?

Theorem 4.3 [36] List p-Helly hypergraph, fixed p ≥ 2 is co-NP-complete.

5 The Bounded Helly Property

Recall that a hypergraph H is p-Helly if every p-intersecting partial hypergraph of H has a nonempty core. As an example, consider V = {a_{1}, …, a_{p+1}} and the hypergraph H formed by the hyperedges V \{a_{i}}, i = 1, …, p + 1. Clearly, H is not p-Helly. This definition can be restricted to subfamilies of limited size.

We say that a hypergraph H is k-bounded p-Helly (k ≤ |E(H)|) if every p-intersecting partial k^{−}-hypergraph of H has a nonempty core. This definition implies that, in a kbounded p-Helly hypergraph, p-intersecting subfamilies of size strictly greater than k do not necessarily contain a common element. For instance, the hypergraph defined in the previous paragraph is not (p + 1)-bounded p-Helly, but it is p-bounded (p − 1)-Helly. This concept, for the case p = 2, was first considered in [94].

Observe that any hypergraph is k-bounded p-Helly for any p ≥ k; consequently, we only need to study the case p < k.

Problem 5.1 k-Bounded p-Helly hypergraph, fixed k and p INSTANCE: A hypergraph H. QUESTION: Is H a k-bounded p-Helly hypergraph?

The following algorithm is straightforward from the definition.

Algorithm 5.1 (Recognizing k-bounded p-Helly hypergraphs): For each partial k^{−}-hypergraph H′ of H, verify whether it is p-intersecting. If some H′ is p-intersecting and has an empty core then stop, as H is not k-bounded p-Helly. Otherwise H is k-bounded p-Helly.

There are O(|E(H)|^{k}) partial k^{−}-hypergraphs in H. In order to test if one of them is p-intersecting and to compute its core we require O(pnk^{p}) and O(nk) time, respectively. Then the definition leads to an algorithm with time complexity O(pnm^{k}k^{p}).

Problem 5.2 k-Bounded p-Helly hypergraph, fixed p INSTANCE: A hypergraph H and an integer k. QUESTION: Is H a k-bounded p-Helly hypergraph?

When p is variable, Theorem 5.2 implies that the above problem is NP-hard. When p is fixed and k is variable, Theorem 5.2 asserts the co-NP-completeness of Problem 5.2. Its proof uses Theorem 5.1.

Theorem 5.1 [29] (Satisfiability): Deciding whether a boolean expression in the conjunctive normal form is satisfiable is NP-complete.

Theorem 5.2 [35] k-Bounded p-Helly hypergraph, fixed p is co-NP-complete.

Proof. It can be checked in polynomial time whether a partial k^{−}-hypergraph is not p-Helly, for fixed p, using Algorithm 4.1. Thus, the decision problem belongs to co-NP. For the hardness proof, we employ a transformation from Satisfiability. Let E be a boolean expression. Denote by X = {x_{1}, …, x_{n}} the set of variables of E and by 𝒞 = {C_{1}, …, C_{m}} the set of clauses. Build a hypergraph H in the following way: for each variable of X and each clause of 𝒞 create one vertex in H. Denote V (H) = V_{X} ∪ V_{𝒞} , where V_{X} = {v_{1}, …, v_{n}} and V_{𝒞} = {c_{1}, …, c_{m}}, that is, the vertex v_{i} ∈ V_{X} is associated with the variable x_{i} ∈ X, and the vertex c_{j} ∈ V_{𝒞} with the clause C_{j} ∈ 𝒞. For each variable x_{i} ∈ X create the hyperedges E_{x_{i}} and E_{\overline{x}_{i}} in H, adding to them the vertices of V_{X}\\{v_{i}\}. Furthermore, for each vertex c_{j} ∈ V_{𝒞} , include c_{j} in the hyperedge E_{x_{i}} (E_{\overline{x}_{i}}) if and only if the literal x_{i} (\overline{x}_{i}) does not appear in the clause C_{j}. Finally, define k = n.

Let H′ be a partial hypergraph of H. If H′ does not contain at least one of the hyperedges E_{x_{i}} or E_{\overline{x}_{i}}, corresponding to x_{i} ∈ X, then v_{i} belongs to the core of H′. Hence, in order to verify whether H is k-bounded p-Helly we need to consider only the partial hypergraphs H′ with exactly k hyperedges such that, for every variable x_{i} ∈ X, either E_{x_{i}} or E_{\overline{x}_{i}} is a hyperedge of H′. Then let H′ be a partial k-hypergraph of H satisfying such a property. Clearly, every v_{i} ∈ V_{X} does not belong to the core of H′ and H′ is (k − 1)-intersecting. Hence, H′ is p-intersecting, because p < k.

Since H′ contains E_{x_{i}} or E_{\overline{x}_{i}} for every x_{i} ∈ X, H′ defines a truth assignment for 𝒞. In this truth assignment a literal has the value true if and only if the corresponding hyperedge belongs to H′. Therefore, let us say that H′ satisfies E if and only if this truth assignment satisfies E.

Suppose that H′ satisfies E. Then any clause of 𝒞 contains at least one literal associated to some hyperedge of H′. This means that for each vertex c_{i} ∈ V_{𝒞} there exists a hyperedge in H′ which does not contain it. Therefore, the core of H′ is empty, meaning that H is not k-bounded p-Helly.

Conversely, suppose that H′ does not satisfy E, and let C_{j} ∈ 𝒞 be a clause in which no literal has the value true. Consider an arbitrary variable x_{i} ∈ X. If E_{x_{i}} is the edge of H′ representing x_{i} then x_{i} ∉ C_{j}, otherwise C_{j} would be satisfied. This implies c_{j} ∈ E_{x_{i}}. Similarly, whenever E_{\overline{x}_{i}} is the representing edge of x_{i}, we have c_{j} ∈ E_{\overline{x}_{i}}. In either case, c_{j} belongs to the edge representing x_{i}, for every i. Thus c_{j} belongs to the core of H′, that is, H is k-bounded p-Helly.

Applying this concept to the cliques of a graph, we have the k-bounded p-clique-Helly graphs. Consider now the recognition problem for graphs. The next theorem states that this problem is co-NP-complete, even for fixed k and p.

Problem 5.3 k-Bounded p-clique-Helly graph, fixed k and p INSTANCE: A graph G. QUESTION: Is G a k-bounded p-clique-Helly graph?

Theorem 5.3 [35] k-Bounded p-clique-Helly graph, fixed k and p is co-NP-complete.

By the definition, it is clear that Clique-Helly ⊂ k-bounded clique-Helly ⊂ k′-bounded clique-Helly, for k′ < k.

However, for K_{k+1}-free graphs, the classes of clique-Helly and k-bounded clique-Helly coincide.

Lemma 5.1 [94] A K_{k+1}-free graph is clique-Helly if and only if it is k-bounded clique-Helly.

Let G be a planar graph. Since any planar graph is K_{5}-free, the number of cliques of G is O(n^{4}). Using Algorithm 5.1, we conclude that the next problem can be solved in polynomial time.

Figure 7: Extended triangles of type 2 and 3

Problem 5.4 Planar 3-bounded clique-Helly graph INSTANCE: A graph G. QUESTION: Is G a 3-bounded clique-Helly graph?

A characterization which leads to a good algorithm for recognizing planar 3-bounded clique-Helly graphs is presented in [3]. Next, we describe it.

For a given triangle T = {x, y, z} of G, we define:

• V_{xy} = {v ∈ V (G) : v ∈ N[x], v ∈ N[y], v ∉ N[z]};

• V_{xz} = {v ∈ V (G) : v ∈ N[x], v ∈ N[z], v ∉ N[y]};

• V_{yz} = {v ∈ V (G) : v ∈ N[y], v ∈ N[z], v ∉ N[x]};

• V_{xyz} = {v ∈ V (G) : v ∈ N[x], v ∈ N[y], v ∈ N[z]}.

Let G be a graph and T′ the extended triangle of G relative to the triangle T = {x, y, z}. Say that:

• T′ is of type 1 if at least one of the sets V_{xy}, V_{xz} or V_{yz} is empty;

• T′ is of type 2 if V_{xy} = {z_{1}}, V_{xz} = {y_{1}}, V_{yz} = {x_{1}}, V_{xyz} = {w}, and w is adjacent to x_{1}, y_{1} and z_{1};

• T′ is of type 3 if V_{xy} = {z_{1}}, V_{xz} = {y_{1}}, V_{yz} = {x_{1}}, V_{xyz} = {w, w′}, and w is adjacent to x_{1}, y_{1} and z_{1}.

Notice that if T′ is an extended triangle of type 2 (resp. type 3) of a planar graph then T′ is isomorphic to the leftmost (resp. rightmost) graph in Figure 7.

Theorem 5.4 [3] Let G be a planar graph.

1. G is a clique-Helly graph if and only if every extended triangle of G is of type 1 or 2.

2. G is a 3-bounded clique-Helly graph if and only if every extended triangle of G is of type 1, 2 or 3.

By this characterization, the complexities to recognize clique-Helly planar graphs and 3-bounded clique-Helly planar graphs are asymptotically the same. Therefore we discuss only the algorithm for 3-bounded 2-clique-Helly planar graphs.

Algorithm 5.2 (Recognizing 3-bounded clique-Helly graphs): Construct the extended triangle for every triangle of G. If some extended triangle is not of type 1, 2 or 3 then stop as the graph is not 3-bounded clique-Helly graph, otherwise it is.

Since the triangles of a planar graph can be listed in O(n) time [86], the above algorithm has complexity O(n^{2}).

Finally, Figure 8 illustrates containment relations among the Helly classes discussed in this section.

Figure 8: Relations among k-bounded p-Helly hypergraph classes

Next, we describe examples for the intersection of hypergraph classes, for Figure 8. The examples are for k = 5 and p = 3.

Define the following hyperedges: E_{1} = {a, b, c}, E_{2} = {a, b, d}, E_{3} = {a, c, d}, E_{4} = {b, c, d}, E_{5} = {a, b, c, d}, E_{6} = {a, b, c, e}, E_{7} = {a, b, d, e}, E_{8} = {a, c, d, e}, E_{9} = {b, c, d, e}, E_{10} = {a, b}.

Examples of hypergraphs in the intersections of Figure 8 can be defined by the hyperedges below:

E(H_{1}) = {E_{1}, E_{2}, E_{3}, E_{4}};

E(H_{2}) = {E_{5}, E_{6}, E_{7}, E_{8}, E_{9}, E_{10}};

E(H_{3}) = {E_{8}, E_{9}, E_{10}};

E(H_{4}) = {E_{5}, E_{6}, E_{7}, E_{8}, E_{9}};

E(H_{6}) = {E_{1}}.

The hypergraph H_{5} does not exist by the following theorem.

Theorem 5.5 Let H be a hypergraph and p and k positive integers such that k > p. If H is not k-bounded (p − 1)-Helly, then H is not (k − 1)-bounded (p − 1)-Helly and not k-bounded p-Helly.

Proof. Suppose that H is a hypergraph which is not k-bounded (p − 1)-Helly but is (k − 1)-bounded (p − 1)-Helly and k-bounded p-Helly. Let H′ be a (p − 1)-intersecting partial k^{−}-hypergraph of H with empty core. Since H is (k − 1)-bounded (p − 1)-Helly, |E(H′)| = k and H′ is (k − 1)-intersecting. Then H′ is also p-intersecting. This implies that H′ has a nonempty core, because H is k-bounded p-Helly, a contradiction.

For the case k = p, a general example of a hypergraph which is not k-bounded (p−1)- Helly but is (k −1)-bounded (p−1)-Helly and k-bounded p-Helly is a k-hypergraph which is not k-bounded (k − 1)-Helly.

6 Cardinality of the Intersections in Hypergraphs

In this section we extend the idea of the Helly property by considering the cardinality of the intersections. Such concept was introduced in [105].

6.1 (p, q)-Intersecting

We begin with a generalization of the concept of p-intersecting hypergraph. Let p ≥ 1 and q ≥ 0. A hypergraph H is (p, q)-intersecting when every partial p^{−}-hypergraph of H has a q^{+}-core.

Clearly, the following implications hold for any hypergraph H.

• If 1 ≤ q ≤ |core(H)|, then H is (p, q)-intersecting.

• For p ≥ 2, if H is (p, q)-intersecting, then H is (p − 1, q)-intersecting.

• If H is (p, q)-intersecting, then H is (p, q − 1)-intersecting.

• H is (1, q)-intersecting if and only if every hyperedge of H contains at least q vertices.

• If H is (p, q)-intersecting, then every partial hypergraph of H is (p, q)-intersecting.

If p is fixed then it is possible to test whether H is (p, q)-intersecting in polynomial time by simply computing the core of every partial p-hypergraph of H. For the case that p is not fixed, deciding whether H is (p, q)-intersecting is co-NP-complete.

Problem 6.1 (p, q)-Intersecting hypergraph, fixed q INSTANCE: A hypergraph H and an integer p ≥ 1. QUESTION: Is H a (p, q)-intersecting hypergraph?

Theorem 6.1 [36] (p, q)-Intersecting hypergraph, fixed q is co-NP-complete.

6.2 (p, q, s)-Helly hypergraphs

The following definition is a generalization of the p-Helly property, and has been introduced in [105].

Let p ≥ 1, q ≥ 0 and s ≥ 0. A hypergraph H is (p, q, s)-Helly when every partial (p, q)-intersecting hypergraph of H has an s^{+}-core.

The following implications are true for any hypergraph H.

• If H is (p, q, s)-Helly, then H is (p + 1, q, s)-Helly.

• If H is (p, q, s)-Helly, then H is (p, q + 1, s)-Helly.

• If H is (p, q, s)-Helly, then H is (p, q, s − 1)-Helly.

• H is (1, q, s)-Helly if and only if the partial hypergraph formed by the q^{+}-hyperedges of H has an s^{+}-core.

Theorem 6.2 Let H be a hypergraph and q > 1 an integer. If H is (p, q, q)-Helly or (p, q, q − 1)-Helly, then H is (p + 1, q − 1, q − 1)-Helly.

Proof. Let H be a hypergraph which is not (p + 1, q − 1, q − 1)-Helly. Let H′ = {E_{1}, …, E_{k}} be a minimal (p + 1, q − 1)-intersecting partial hypergraph of H with no (q − 1)-core. It is clear that k ≥ p + 2. Define C_{i} = core(H′ \ {E_{i}}), 1 ≤ i ≤ k. If |C_{i} ∩ C_{j}| ≥ q − 1, for some i ≠ j, then H′ would have a (q − 1)-core. This implies that |C_{i} ∪ C_{j}| ≥ q, for every i ≠ j. Since the core of every partial p-hypergraph of H′ contains at least two distinct C_{i}’s, H′ is (p, q)-intersecting with no (q − 1)-core. This implies that H is not (p, q, q)-Helly nor (p, q, q − 1)-Helly.

Lemma 6.1 Let H be a hypergraph with m edges, m ≥ 2. Any hypergraph with 0 < m′ < m edges, each containing at least m − 1 edges of H, has a core containing at least m − m′ edges of H.

We can now describe the characterization of (p, q, s)-Helly hypergraphs. First we deal the natural case q ≥ s. The idea is to check whether the (p, q)-intersecting hypergraphs still keep s ≤ q elements in their cores.

Theorem 6.3 [38] Let p, s ≥ 1, q ≥ s be integers. A hypergraph H is (p, q, s)-Helly if and only if:

(i) for every family S formed by p + q − s + 1 distinct s-subsets of V (H), the partial hypergraph H′ of H formed by all the edges of H containing each at least p + q − s members of S satisfies the following statement:

H′ is (p, q)-intersecting ⇒ |core(H′)| ≥ s

(ii) every (p, q)-intersecting partial hypergraph of H with p + q − s or fewer edges has an s-core.

Proof. The theorem says that, in order to check the (p, q, s)-Helly property in a hypergraph H, it is not necessary to check whether every (p, q)-intersecting partial hypergraph of H has an s-core, but it is sufficient to check only a few particular partial hypergraphs of H. Hence we only need to prove the sufficiency.

Assume that H is not (p, q, s)-Helly. Then there exists a (p, q)-intersecting partial hypergraph H′ of H such that |core(H′)| < s. If |H′| ≤ p + q − s then H′ is a (p, q)- intersecting partial (p + q − s)^{−}-hypergraph of H that violates Condition (ii).

Otherwise, write H′ = {E_{1}, …, E_{m′}}. Thus, m′ ≥ p + q − s + 1. Assume that H′ is minimal, that is, H′ \ {E} has an s^{+}-core, for any E ∈ H′. (If H′ is not minimal, one can successively remove edges from H′ until obtaining either a minimal (p + q − s + 1)^{+}- hypergraph or a (p+q −s)^{−}-hypergraph violating Condition (ii)). For each i, 1 ≤ i ≤ m′, let S_{i} ⊆ core(H′ \ {E_{i}}) be a s-subset of vertices such that S_{i} ⊈ E_{i} and S_{i} ⊆ E_{j} for every j ≠ i. This means that there exists v_{i} ∈ S_{i} such that v_{i} ∉ E_{i} but v_{i} ∈ E_{j} for every j ≠ i.

Let S = {S_{1}, …, S_{p+q−s+1}}. Note that S is a family formed by p + q − s + 1 distinct s-subsets of V (H). Define H′′ as the hypergraph formed by those edges of H containing p + q − s edges of S each. Since H′ is a partial hypergraph of H′′, H′′ does not have an s-core. Let us show that H′′ is (p, q)-intersecting.

Consider any partial p-hypergraph H′′′ of H′′. By Lemma 6.1, core(H′′′) contains at least q − s + 1 edges of S, say S_{1}, …, S_{q−s+1}. Note that S_{1} ∪ {v_{i} : 2 ≤ i ≤ q − s + 1} contains exactly s + q − s = q vertices. This means that |core(H′′′)| ≥ q. Therefore, H′′ is (p, q)-intersecting and does not have an s^{+}-core. This violates Condition (i).

Nevertheless, for completeness, we deal with the case s ≥ q.

Theorem 6.4 Let p, q ≥ 1, s ≥ q be integers. A hypergraph H is (p, q, s)-Helly if and only if:

(i) for every family S formed by p+1 distinct q-subsets of V (H), the partial hypergraph H′ of H formed by all the hyperedges of H containing at least p members of S has an s-core;

(ii) every (p, q)-intersecting partial hypergraph of H with p or fewer edges has an s-core.

Proof. For the necessity we only need to prove that every partial hypergraph H′ of the Condition (i) is (p, q)-intersecting. But this is inferred directly from Lemma 6.1.

For the sufficiency, the proof is essentially the same of Theorem 6.3.

Problem 6.2 (p, q, s)-Helly hypergraph, fixed p and q INSTANCE: A hypergraph H and an integer s ≥ 1. QUESTION: Is H a (p, q, s)-Helly hypergraph?

The above theorems leads to the following algorithm for Problem 6.2. For the case q ≥ s consider a = q − s and b = s, while for the case s ≤ q consider a = 0 and b = q.

Algorithm 6.1 (Recognizing (p, q, s)-Helly hypergraphs):

Part (i): for each (p + a + 1)-family S of b-subsets of V (H), construct the partial hypergraph H′ choosing the hyperedges of H containing at least p + a members of S. Then verify whether H′ is (p, q)-intersecting. If so, verify whether H′ has an s^{+}-core.

Part (ii): for each partial (p+a)^{−}-hypergraph of H, check whether it is (p, q)-intersecting. If so, verify whether it has an s^{+}-core.

The complexity of Part (i) of the above algorithm is O(pm^{p}n^{b(p+a+1)+1}), because there are O(n^{b(p+a+1)}) (p + a + 1)-families of b-subsets of V (H), and for each one we spend O(m(n + (p + a)b)) steps to construct each H′, O(pnm^{p}) to check whether H′ is (p, q)-intersecting and O(nm) to compute its core. For Part (ii), the complexity is O(pnm^{p+a}(p + a)^{p+1}). The overall time complexity is the sum of both. It is polynomial for fixed p, q and variable s.

Problem 6.3 (p, q, s)-Helly hypergraph, fixed q and s INSTANCE: A hypergraph H and an integer p ≥ 2. QUESTION: Is H a (p, q, s)-Helly hypergraph?

Theorem 6.5 [36] (p, q, s)-Helly hypergraph, fixed q and s is NP-hard.

We deal now with the case in which q is not fixed.

Problem 6.4 (p, q, s)-Helly hypergraph, fixed p and s INSTANCE: A hypergraph H and an integer q ≥ 1. QUESTION: Is H a (p, q, s)-Helly hypergraph?

Theorem 6.6 [36] (p, q, s)-Helly hypergraph, q variable is co-NP-complete.

Containment relations among the (p, q, s)-Helly hypergraph classes, considering variations of p, q and s, are shown in Figure 9.

Figure 9: Relations among (p, q, s)-Helly hypergraph classes

Next, we describe examples belonging to the intersections of classes in Figure 9. The examples are for p = 2, q = 2 and s = 2.

Define the following hyperedges: E_{1} = {a, b, c, e}, E_{2} = {a, b, d, e}, E_{3} = {a, c, d, e}, E_{4} = {b, c, d, e}, E_{5} = {a, b, c}, E_{6} = {a, b, c, d, e, f}, E_{7} = {a, b, c, g, h, i}, E_{8} = {d, e, f, g, h, i}, E_{9} = {a, d, e, f, g, h, i}, E_{10} = {a, b, d}, E_{11} = {a, c, d}.

Examples of hypergraphs belonging to the intersections of classes in Figure 9 can be defined by the hyperedges below:

E(H_{1}) = {E_{1}, E_{2}, E_{3}, E_{4}, E_{5}};

E(H_{2}) = {E_{6}, E_{7}, E_{8}};

E(H_{3}) is the subhypergraph of H_{6} (see its definition below) induced by V (H_{6}) \ {e};

H_{4} does not exist by Theorem 6.2;

E(H_{5}) = {E_{6}, E_{7}, E_{9}};

E(H_{6}) = {E_{1}, E_{2}, E_{3}, E_{4}};

H_{7} does not exist by Theorem 6.2;

E(H_{8}) = {E_{5}, E_{10}, E_{11}};

E(H_{9}) = {E_{5}}.

6.3 The Case q = s

The case q = s is natural and interesting. For simplicity, we write (p, q)-Helly hypergraphs instead of (p, q, q)-Helly hypergraphs. Theorem 6.3 can be rewritten for the case q = s as follows:

Corollary 6.1 [38] A hypergraph H is (p, q)-Helly if and only if for every family S formed by p + 1 distinct q-subsets of V (H), the partial hypergraph H′ formed by all the hyperedges of H containing at least p members of S has a q^{+}-core.

Proof. Condition (ii) of Theorem 6.3 is trivially true for q = s.

The case p = 2, q = s has received attention. In special, bounds for (2, q)-Helly hypergraphs were described in [104]. In the same work, the problem of finding a structural characterization for r-uniform (2, q)-Helly hypergraphs for r > q + 1 was proposed.

The complexity of recognizing (2, q)-Helly hypergraphs, when q is part of the input, remains as an open question. However, if we consider a fixed q, we have a polynomial time recognition algorithm as a consequence of Theorem 6.3.

Problem 6.5 (2, q)-Helly hypergraph, fixed q INSTANCE: A hypergraph H. QUESTION: Is H a (2, q)-Helly hypergraph?

The complexity of recognizing (p, q)-Helly hypergraphs, by using Corollary 6.1 and Algorithm 6.1, is O(n^{q(p+1)}m(n + pq)). Hence, for p = 2, we have an O(mn^{3q+1}) time complexity. If q = 1, we obtain the same complexity of Algorithm 4.1.

Another interesting case occurs for p = 2 and small values of r − q:

Problem 6.6 (2, q)-Helly hypergraph, fixed r − q INSTANCE: A hypergraph H with rank r and an integer q, such that r − q is small. QUESTION: Is H a (2, q)-Helly hypergraph?

A polynomial-time algorithm for the above problem is a consequence of the following proposition:

Proposition 6.1 [104] If H is a minimal non-(2, q)-Helly hypergraph of rank r with 1 ≤ q < r, then |E(H)| ≤ r − q + 2.

Algorithm 6.2 ((2, q)-Helly hypergraphs): For every partial (r−q+2)^{−}-hypergraph of a hypergraph H, compute its core and verify if it contains at least q elements. Then H is (2, q)-Helly precisely when the answer is affirmative in all cases.

There are ∑_{i=3}^{r−q+2} \binom{m}{i} partial hypergraphs to be considered; this amount is O(m^{r−q+2}) by [82, Theorem 2.6.1]. In order to compute the core of each one we need O(nm) time. The overall complexity is O(nm^{r−q+3}), which is polynomial for small values of r − q.

We now present another way to verify if a hypergraph is (2, q)-Helly. The q-line graph of a hypergraph H, denoted by L_{q}(H), has a vertex for every hyperedge of H, and two vertices are adjacent if the corresponding hyperedges share at least q vertices.

Theorem 6.7 The number of cliques of L_{q}(H) for a (2, q)-Helly hypergraph H of rank r is not greater than m\binom{r}{q}.

Proof. Let H be a (2, q)-Helly hypergraph. First note that if C′, C′′ are cliques of L_{q}(H) and H′, H′′ are the partial hypergraphs of H formed by the hyperedges associated to the vertices of C′ and C′′, respectively, then the cores of H′ and H′′ are incomparable and each one has at least q elements.

Let v be a vertex of L_{q}(H) and E_{v} the hyperedge of H corresponding to v. Since E_{v} contains all the cores of the partial hypergraphs associated with the cliques to which v belongs, vertex v appears in at most (_{q}^{r}) cliques of L_{q}(H). Since the number of vertices of L_{q}(H) is m, the number of cliques of L_{q}(H) is not greater than m\binom{r}{q}.

The above theorem leads to the following algorithm. Let H be a hypergraph and q ≥ 0 an integer.

Algorithm 6.3 ((2, q)-Helly hypergraphs):

Construct the graph L_{q}(H) and generate its cliques, C_{1}, C_{2}, …, C_{i}, … For each C_{i}, proceed as follows.

• If i > \frac{mr!}{q!(r − q)!} then stop: H is not (2, q)-Helly.

• Otherwise, construct the partial hypergraph H_{i} of H, formed by the hyperedges of H corresponding to the vertices of C_{i}. If core(H_{i}) < q, then stop: H is not (2, q)-Helly.

• Otherwise, if all the cliques of L_{q}(H) have been generated, then H is (2, q)-Helly.

To construct L_{q}(H) we spend O(m^{2}n) steps. We generate at most m\binom{r}{q} cliques, each in O(nm) time using the algorithm in [100]. In order to compute the core of each partial hypergraph, O(nm) steps are required. The total complexity of the above algorithm is thus O(m^{2}n + n^{2}m^{3}\binom{r}{q}) = O(n^{2}m^{3}\binom{r}{q}).

The time complexity of this algorithm for Problem 2, when q is fixed, is O(n^{2}m^{3}r^{q}) = O(n^{q+2}m^{3}), while for Question 3, when r − q is small, O(n^{2}m^{3}r^{r−q}) = O(n^{r−q+2}m^{3}) steps are required.

6.4 Helly numbers

A hypergraph H has Helly number h if h is the least number for which H is h-Helly [66]. For the general (p, q, s)-Helly property it is possible to define variations of the Helly number in the following ways:

– Let q, s ≥ 0 be fixed integers. The (p^{∗}, q, s)-Helly number of H is the least integer p, if it exists, such that H is (p, q, s)-Helly.

– Let p ≥ 1 and s ≥ 0 be fixed integers. The (p, q^{∗}, s)-Helly number of H is the least integer q such that H is (p, q, s)-Helly. This number is well defined since H is (p, n + 1, s)-Helly for any p, s.

– Let p ≥ 1 and 0 ≤ q ≤ r(H) be fixed integers. The (p, q, s^{∗})-Helly number of H is the largest s for which H is (p, q, s)-Helly.

By Theorem 6.5, we conclude that determining the (p^{∗}, q, s)-Helly number is NP-hard. Similarly, Theorem 6.6 implies that finding the (p, q^{∗}, s)-Helly number is also NP-hard. However, using Theorem 6.1, we can determine the (p, q, s^{∗})-Helly number in polynomial time.

6.5 (p, q)-Conformal hypergraphs

We now generalize Theorem 4.1. In order to do so, we use the following generalizations of the concepts of k-section and k-conformal hypergraphs.

Define the (p, q)-section of H to be a hypergraph [H]_{p,q} whose hyperedges are sets F ⊆ V (H) such that either |F | = p and F is contained in at least q hyperedges of H, or |F | < p and F is a maximal set contained in at least q hyperedges of H.

A hypergraph H is (p, q)-conformal if every maximal set of V (H), which induces a K_{j}^{p} hypergraph of [H]_{p,q}, for p ≤ j, is contained in at least q hyperedges of H.

Theorem 6.8 A hypergraph H is (p, q)-Helly if and only if its dual is (p, q)-conformal.

Proof. Let H be a hypergraph and H^{∗} its dual hypergraph. Suppose first that H^{∗} is not (p, q)-conformal. Hence, in [H^{∗}]_{p,q}, there is a maximal set that induces a p-complete hypergraph I, such that V (I) is not contained in q hyperedges of H^{∗}. However, the hyperedges of H, associated with the vertices of I, form a (p, q)-intersecting partial hypergraph with no q^{+}-core.

Conversely, suppose that H is not (p, q)-Helly. Consider a maximal (p, q)-intersecting partial hypergraph H′ of H with no q^{+}-core. The hyperedges of H′ correspond to a subset of vertices C of H^{∗} with the property that every p of them belong to at least q hyperedges of H^{∗} simultaneously. This means that C is a maximal set inducing a p-complete partial hypergraph I of [H^{∗}]_{p,q}. Furthermore, if V (I) = C is contained in at least q hyperedges of H^{∗}, this implies that H′ contains a q^{+}-core, which contradicts the hypothesis.

7 Cardinality of the Intersections on Cliques of Graphs

In this section we apply the (p, q, s)-Helly property to the clique hypergraph of a graph. Thus, a graph is (p, q, s)-clique-Helly if its clique hypergraph is (p, q, s)-Helly. According to this definition, (2, 1)-clique-Helly graphs are the clique-Helly graphs. First we focus on the recognition problem of the case q = s, corresponding to the so-called (p, q)-clique-Helly graphs, and afterwards we shall deal with the problem of deciding whether the clique graph of a graph is clique-Helly.

7.1 (p, q)-Clique-Helly graphs

We begin with an example. Define, for two integers p and q, the graph G_{p,q} as follows: V (G_{p,q}) is formed by a (q − 1)-complete set Q, a p-complete set Z = {z_{1}, …, z_{p}}, and a p-independent set W = {w_{1}, …, w_{p}}. Further, there exist the edges z_{i}w_{j}, for i ≠ j, and qx, for q ∈ Q and x ∈ Z ∪ W.

Figure 10: Graph G_{p,q}

The general graph G_{p,q} appears in Figure 10, where a thick line joining two sets means that every vertex of a set is adjacent to all vertices of the other. Furthermore, for every vertex of Z, there is a dotted line joining it to the only vertex of W which is not adjacent to it.

The graph G_{p,q} contains exactly p + 1 cliques of size p + q − 1, namely: Q ∪ Z and Q ∪ (Z\{z_{i}}) ∪ {w_{i}}, for 1 ≤ i ≤ p.

Observe that G_{p,q} is (p, q)-clique-Helly, but it is not (p − 1, q)-clique-Helly. Therefore, G_{p,q} is (t, q)-clique-Helly for t ≥ p, and is not (t, q)-clique-Helly for t < p.

Furthermore, G_{p+1,q} is not (p, q)-clique-Helly, but it is (p, t)-clique-Helly for any t ≠ q. Consequently, for distinct q and t, the classes of graphs (p, q)-clique-Helly and (p, t)-clique-Helly are incomparable.

The following theorem describes a class of (p, q)-clique-Helly graphs.

Theorem 7.1 [37] Let p, r > 1, q > 0 such that p + q ≥ r. If G is a K_{r}-free graph, then G is (p, q)-clique-Helly.

Our aim is now to characterize (p, q)-clique-Helly graphs. We divide the characterization in two cases, the first dealing with p = 1.

Figure 11: Relations among (p, q)-clique-Helly graph classes. Where G_{1} = G_{p,q} ∪ G_{p,q−1} and G_{2} = G_{1} ∪ G_{p+1,q}.

Theorem 7.2 [37] Let G be a graph, and let W be the union of the q^{+}-cliques of G. Then G is a (1, q)-clique-Helly graph if and only if G[W] contains q universal vertices.

The second case corresponds to p ≥ 2 and we employ some additional definitions.

Let G be a graph and C a p-complete set of G. The p-expansion relative to C is the subgraph of G induced by the vertices w such that w is adjacent to at least p − 1 vertices of C.

We remark that the p-expansion for p = 3 has been used for characterizing clique-Helly graphs [40, 97]. It is clear that constructing a p-expansion relative to a given p-complete set can be done in polynomial time.

Let ℱ be a partial hypergraph of C(G). The clique subgraph induced by ℱ in G, denoted by G_{c}[ℱ], is the subgraph of G formed exactly by the vertices and edges belonging to the cliques of ℱ.

Lemma 7.1 Let G be a graph, C a p-complete set of G, H the p-expansion of G relative to C, and 𝒞 the partial hypergraph C(G) formed by the cliques that contain at least p − 1 vertices of C. Then G_{c}[𝒞] is a spanning subgraph of H.

Figure 12: A graph G and the 4-expansion relative to {a, b, c, d}.

Figure 13: A graph G and Φ_{3}(G)

Let G be a graph. The graph Φ_{q}(G) is defined as follows: the vertices of Φ_{q}(G) correspond to the q-complete sets of G, two vertices being adjacent in Φ_{q}(G) if the corresponding q-complete sets in G are contained in a common clique. As an example see Figure 13.

We remark that Φ_{q} is precisely the operator Φ_{q,2q} described in [91], p.136, and the graph Φ_{2}(G) is the edge clique graph of G, introduced in [1].

An interesting property of Φ_{q} is that it preserves the q^{+}-cliques of G, that is, every q^{+}-clique of G is a clique of Φ_{q}(G), and vice versa. Then, given a q^{+}-clique C of G, denote by φ_{q}(C) the clique of Φ_{q}(G) associated with C.

Let G be a graph and C(G) its clique hypergraph. Let ℱ be a partial hypergraph of C(G) containing some q^{+}-cliques of G. Define φ_{q}(ℱ) to be the set of cliques {φ_{q}(C) : C ∈ E(ℱ)}. If 𝒞 is a partial hypergraph of C(Φ_{q}(G)), define φ_{q}^{−1}(𝒞) as the set of cliques {φ_{q}^{−1}(C) : C ∈ E(𝒞)}. As a consequence we have:

Corollary 7.1 Let G be a graph, ℱ a partial hypergraph of C(G) containing some q^{+}- cliques of G, and 𝒞 such that E(𝒞) = φ_{q}(ℱ). Then |core(ℱ)| ≥ q if and only if |core(𝒞)| ≥ 1 .

Lemma 7.2 Let C be a (p + 1)-complete set of a graph G, and let 𝒞 be a partial p^{−}- hypergraph of C(G) such that every clique of 𝒞 contains at least p vertices of C. Then core(𝒞) ≠ ∅.

The next result is a characterization of (2, 2)-clique-Helly graphs.

Theorem 7.3 [28] A graph G is (2, 2)-clique-Helly if and only if every extended triangle of Φ_{2}(G) contains a universal vertex.

Problem 7.1 (2, 2)-Clique-Helly graph INSTANCE: A graph G. QUESTION: Is G a (2, 2)-clique-Helly graph?

Algorithm 7.1 (Recognizing (2, 2)-clique-Helly graphs): In order to construct Φ_{2}(G), create one vertex for each edge of G. Then join two vertices by an edge if the corresponding edges are contained in a same clique of G.

Next, for every triangle T of Φ_{2}(G), we construct the extended triangle of T and verify if it contains a universal vertex. If we find one extended triangle which does not have a universal vertex, then we stop as G is not (2, 2)-clique-Helly; otherwise it is (2, 2)-clique-Helly.

In order to calculate the complexity of this algorithm, first note that the number of vertices of Φ_{2}(G) is m. The time complexity to construct Φ_{2}(G) is O(m^{2}), and the time complexity to verify if there exists an extended triangle without a universal vertex is O(m^{5}). Therefore one can verify if a graph is (2, 2)-clique-Helly in time O(m^{5}).

Now we present a generalization of this result.

Theorem 7.4 [37] Let p > 1 be an integer. Then a graph G is (p, q)-clique-Helly if and only if every (p + 1)-expansion of Φ_{q}(G) contains a universal vertex.

Proof. Suppose that G is a (p, q)-clique-Helly graph and there exists a (p + 1)-expansion T, relative to a (p+1)-complete set C of Φ_{q}(G), such that T contains no universal vertex.

Denote H = Φ_{q}(G). Let 𝒞 be the partial hypergraph C(H) that contains at least p vertices of C. Consider a partial p^{−}-hypergraph 𝒞′ of 𝒞. By Lemma 7.2, core(𝒞′) ≠ ∅. This implies that 𝒞 is (p, 1)-intersecting. By Corollary 7.1, ℱ = φ_{q}^{−1}(𝒞) is (p, q)- intersecting. Since G is (p, q)-clique-Helly, we conclude that ℱ has a q^{+}-core. By using Corollary 7.1 again, 𝒞 has an 1^{+}-core, which means that H_{c}[𝒞] contains a universal vertex. Moreover, by Lemma 7.1, H_{c}[𝒞] is a spanning subgraph of T. However, T contains no universal vertex. This is a contradiction. Therefore, every (p+1)-expansion of H contains a universal vertex.

Conversely, assume by contradiction that G is not (p, q)-clique-Helly. Let ℱ be a minimal (p, q)-intersecting partial hypergraph of C(G) which does not have a q^{+}-core. Denote E(ℱ) = {C_{1}, …, C_{k}}, C_{i} ∈ C(G). Clearly, k > p.

The minimality of ℱ implies that there exists a q-subset Q_{i} ⊆ core(ℱ − C_{i}), for i = 1, …, k. It is clear that Q_{i} ⊈ C_{i}. Moreover, every two distinct Q_{i}, Q_{j} are contained in a common clique, since k ≥ 3. Hence the sets Q_{1}, Q_{2}, …, Q_{p+1} correspond to a (p + 1)- complete set C in Φ_{q}(G).

Let 𝒞′ be the partial hypergraph of C(H) formed by the cliques that contain at least p vertices of C. Let 𝒞 = φ_{q}(ℱ). Since every C_{i} ∈ E(ℱ) contains at least p sets from Q_{1}, Q_{2}, …, Q_{p+1}, it is clear that the clique φ_{q}(C_{i}) ∈ E(𝒞) contains at least p vertices of C. Therefore, φ_{q}(C_{i}) ∈ E(𝒞′), for i = 1, …, k.

Let T be the (p + 1)-expansion of H relative to C. By Lemma 7.1, H_{c}[𝒞′] is a spanning subgraph of T. Therefore, Q ⊆ V (T), for every Q ∈ E(𝒞′). In particular, V (φ_{q}(C_{i})) ⊆ V (T), for i = 1, …, k. By hypothesis, T contains a universal vertex x. Then x is adjacent to all the vertices of φ_{q}(C_{i})\{x}, for i = 1, …, k. This implies that φ_{q}(C_{i}) contains x, otherwise φ_{q}(C_{i}) would not be maximal. Thus, core(𝒞) ≠ ∅. By Corollary 7.1, ℱ has a q^{+}-core, a contradiction. Hence, G is a (p, q)-clique-Helly graph.

From the above theorem one can recognize (p, q)-clique-Helly graphs in polynomial time if p and q are fixed.

Problem 7.2 (p, q)-Clique-Helly graph, fixed p and q INSTANCE: A graph G. QUESTION: Is G a (p, q)-clique-Helly graph?

We present now the algorithm, for the case p ≥ 2. Let G be a graph.

Algorithm 7.2 (Recognizing (p, q)-clique-Helly graphs): Construct the graph Φ_{q}(G) having as vertices the p-complete sets of G, and join two vertices by an edge when the corresponding p-complete sets are both contained in a same clique.

Next, for every (p+1)-complete set C of Φ_{q}(G), we construct the (p+1)-expansion relative to C and verify if it contains a universal vertex. If we find a (p+1)-expansion which does not have a universal vertex, then we stop as G is not (p, q)-clique-Helly; otherwise it is (p, q)-clique-Helly.

In order to calculate the complexity of this algorithm, first note that the number of vertices of Φ_{q}(G) is t = O(n^{q}). The time complexity to construct Φ_{q}(G) is O(n^{2q}q^{2}), whereas to verify if there exists a (p+1)-expansion with no universal vertex is O(t^{p+1}m′) = O(n^{q(p+1)}m′), where m′ = O(t^{2}) is the number of edges of Φ_{q}(G). Therefore one can verify if a graph is (p, q)-clique-Helly in O(n^{q(p+3)}) time.

If p or q is variable, this procedure does not lead to a polynomial time algorithm. Indeed, the problem is NP-hard in both cases.

Problem 7.3 (p, q)-clique-Helly graph, fixed p INSTANCE: A graph G and a positive integer q. QUESTION: Is G a (p, q)-clique-Helly graph?

Theorem 7.5 [37] (p, q)-Clique-Helly graph, fixed p is NP-hard.

Problem 7.4 (p, q)-Clique-Helly graph, fixed q INSTANCE: A graph G and a positive integer p. QUESTION: Is G a (p, q)-clique-Helly graph?

Theorem 7.6 [37] (p, q)-Clique-Helly graph, fixed q is NP-hard.

7.2 Helly defect

For any clique-Helly graph, its clique graph is also clique-Helly [49]. However, if a graph is not clique-Helly it is still possible for its clique graph to be clique-Helly. This leads to the definition of Helly defect [9], a parameter that informs how many times the clique operator must be applied for a graph to become clique-Helly. The Helly defect of a graph G is the smallest i such that K^{i}(G) is clique-Helly. There are graphs with any desired finite Helly defect [21]. However if K^{i}(G) is not clique-Helly, for any finite i, we say that its Helly defect is infinite. Trivially, the Helly defect of a clique-Helly graph is 0, while that of a divergent graph is infinity.

Problem 7.5 Helly defect one INSTANCE: A graph G. QUESTION: Is the Helly defect of G at most one?

The Helly defect of a graph G is less than or equal to 1 when G or K(G) is clique-Helly. In fact, this problem corresponds to asking whether G or K(G) is (2, q)-clique-Helly, for q = 1.

Problem 7.6 Clique graph is (2, q)-clique-Helly INSTANCE: A graph G. QUESTION: Is K(G) a (2, q)-clique-Helly graph?

Theorem 7.7 [34] Clique graph is (2, q)-clique-Helly is NP-hard.

Corollary 7.2 [34] Helly defect one is NP-hard.

8 Hereditary Helly Property

A hypergraph is strong Helly if, for every partial hypergraph H′ of H, there exist two hyperedges in H′ whose core is equal to the core of H′. A hypergraph H is hereditary Helly if all subhypergraphs of H are Helly. In this section we present algorithms and characterizations on these variants of the Helly property.

In fact, we show that these two concepts are equivalent. First we characterize hereditary p-Helly hypergraphs and then we consider the hereditary Helly property applied to special families of vertices of a graph, such as cliques, disks, bicliques, open and closed neighborhoods.

8.1 Hypergraphs

Since the number of partial hypergraphs and subhypergraphs of a given hypergraph H can be exponential in the size of H, the definitions do not lead directly to algorithms capable of verifying, in polynomial time, if a hypergraph is strong Helly or hereditary Helly.

Problem 8.1 Hereditary Helly hypergraph INSTANCE: A hypergraph H. QUESTION: Is H a hereditary Helly hypergraph?

In [106] it has been shown that a hypergraph H is strong Helly if and only if for every three hyperedges of H there exist two of them whose core equals the core of the three hyperedges. This characterization leads to an algorithm for recognizing strong Helly hypergraphs with time complexity O(rm^{3}), where r and m are, respectively, the rank and the number of hyperedges of the hypergraph.

In [26] it was presented an algorithm for recognizing hereditary Helly hypergraphs that needs O(mΔr^{4}) time and O(mr^{2}) space, where Δ is the maximum degree of the hypergraph.

Generalizing these concepts, it follows that a hypergraph H is strong p-Helly if for every partial (p + 1)^{+}-hypergraph H′ of H there exist p hyperedges in H′ whose core equals the core of H′. Also, a hypergraph H is hereditary p-Helly if all subhypergraphs of H are p-Helly.

The following theorem describes classes of strong k-Helly hypergraphs.

Theorem 8.1 [54]

(i) A hypergraph in which every hyperedge is a set of edges of some path of a tree is strong 3-Helly.

(ii) A hypergraph in which every hyperedge is a set of edges of some subtree of a tree with k leaves is strong k-Helly.

The following theorem characterizes strong p-Helly and hereditary p-Helly hypergraphs. It implies that these concepts are equivalent.

Theorem 8.2 [39] The following statements are equivalent for a hypergraph H:

(i) H is strong p-Helly;

(ii) H is hereditary p-Helly;

(iii) H is (p, q)-Helly, for every q;

(iv) every partial (p + 1)-hypergraph of H is (p, q)-Helly for every q;

(v) there is no subhypergraph of H having a partial hypergraph isomorphic to K_{p+1}^{p}.

Proof. (i) ⇒ (ii) Suppose that H contains a subhypergraph H′ that is not p-Helly. Let H′′ be a partial hypergraph of H′ which is p-intersecting with an empty core. Define a partial hypergraph H_{1} of H choosing for every hyperedge E′′ ∈ E(H′′) the hyperedge of H that originated it. Since any p hyperedges of H′′ contain a vertex that is not in the core of H′′, the same is true for any p hyperedges and the core of H_{1}. Therefore H is not strong p-Helly.

(ii) ⇒ (iii) Suppose that H is not (p, q)-Helly, for some q. Let H′ be a (p, q)- intersecting partial hypergraph of H without a q^{+}-core. Denote the core of H′ by C′. Every hyperedge of H′ properly contains C′ because it belongs to a (p, q)-intersecting partial hypergraph, and C′ is a (q − 1)^{−}-set. Hence, in the subhypergraph H′_{1} of H induced by V (H) \ C′, there is one hyperedge for every hyperedge of H′. Consider the partial hypergraph H′′_{1} of H′_{1} formed by these hyperedges. Note that H′′_{1} is p-intersecting and has an empty core. Therefore H′_{1} is not p-Helly.

(iii) ⇒ (iv) Trivial.

(iv) ⇒ (v) Let H′ be a partial hypergraph of a subhypergraph of H isomorphic to K_{p+1}^{p}. Clearly, H′ is not (p, 1)-Helly. Moreover, there exists a partial (p + 1)-hypergraph H′′ of H in which every hyperedge contains a different hyperedge of H′. Hence, if the core of H′′ has size c, we can say that H′′ is (p, c + 1)-intersecting, that is, H′′ is not (p, c + 1)-Helly.

(v) ⇒ (i) Suppose that H is not strong p-Helly. Then there is a partial hypergraph H′ of H such that the core of every p hyperedges of H′ properly contains C′ = core(H′).

Perform the following process: if H′ contains a hyperedge E′ such that the core of H′ −E′ is C′, redefine E(H′) = E(H′) \ {E′}, and repeat; otherwise, stop.

After completing the above process, observe that for any E_{k} ∈ E(H′) there exists a vertex v_{k} ∉ E_{k} in the core of H′ − E_{k}. This means that the subhypergraph of H induced by {v_{1}, v_{2}, …, v_{p+1}} has a partial hypergraph isomorphic to the hypergraph formed by all p-subsets of a (p + 1)-set.

We can apply the equivalence (i)-(iv) in order to formulate a recognition algorithm for strong p-Helly graphs. First, observe that assertion (iv) is equivalent to state that for every (p + 1)-hypergraph H′ of H there exist p hyperedges with the same core as H′.

Problem 8.2 Hereditary p-Helly hypergraph, fixed p ≥ 2 INSTANCE: A hypergraph H. QUESTION: Is H strong p-Helly?

Algorithm 8.1 (Recognizing hereditary p-Helly hypergraphs): For every partial (p + 1)-hypergraph of H, compute its core and the core of every partial p-hypergraph thereof. If every partial (p + 1)-hypergraph H′ of H has a partial p-hypergraph whose core equals the core of H′ then H is strong p-Helly, otherwise it is not.

Computing the cores of a (p + 1)-hypergraph and all its partial p-hypergraphs can be done in O(p^{2}r) steps. Since there are O(m^{p+1}) partial (p + 1)-hypergraphs in a hypergraph, this algorithm has time complexity O(p^{2}rm^{p+1}). For fixed p, the above algorithm terminates within polynomial time. The following theorem refers to p variable.

Problem 8.3 Hereditary p-Helly hypergraph, p variable INSTANCE: A hypergraph H and an integer p ≥ 2. QUESTION: Is H strong p-Helly?

Theorem 8.3 [39] Hereditary p-Helly hypergraph, p variable is co-NP-complete.

Now we present a figure relating the classes of p-Helly and hereditary p-Helly hypergraphs. We present examples showing these relations. Consider an integer p ≥ 3. Let V_{1} = {v_{1}, …, v_{p}}, H_{1} = {E_{i} : 1 ≤ i ≤ p}; and V_{2} = {u_{1}, …, u_{p+2}} and H_{2} = {E_{i} : 1 ≤ i ≤ p + 1}. The hypergraph H_{1} is hereditary p-Helly, but is not (p − 1)-Helly; while H_{2} is (p − 1)-Helly, but is not hereditary p-Helly. Last, the hypergraph H_{3} = H_{1} ∪ H_{2} is p-Helly, but is not (p − 1)-Helly nor hereditary p-Helly.

Next, we describe examples for the intersection of hypergraph classes, for Figure 14. The examples are for general values of p:

H_{1} = K_{p+1}^{p};

H_{2} = K′∪K_{p}^{p−1}, where K′ is the hypergraph K_{p+1}^{p} with an additional universal vertex;

H_{3} = K_{p}^{p−1}.

Figure 14: Relations among p-Helly and hereditary p-Helly hypergraph classes

8.2 Cliques of graphs

We say that a graph is strong p-clique-Helly if its clique hypergraph is strong p-Helly, and that it is hereditary p-clique-Helly if all its induced subgraphs are p-clique-Helly. As usual, we write clique-Helly to mean 2-clique-Helly.

Since every p-clique-Helly graph is also (p + 1)-clique-Helly, every hereditary p-clique-Helly graph is also hereditary (p+1)-clique-Helly. The following result says that the clique hypergraph of a intersection graph of a family of edge paths of a tree is strong 4-Helly.

Theorem 8.4 [54] If G is an intersection graph of edge paths of a tree, then G is strong 4-clique-Helly.

Next, we consider the question of characterizing hereditary p-clique-Helly graphs.

Theorem 8.2 is valid for general hypergraphs, and in particular for the clique hypergraph of a graph. However, since the number of cliques of a graph may be exponential in the size of the graph [84], it does not lead to a polynomial-time recognition algorithm for strong p-clique-Helly graphs. Similarly, the recognition algorithm for p-clique-Helly

Figure 15: Forbidden subgraphs for hereditary clique-Helly graphs

graphs is not suitable for the recognition of hereditary p-clique-Helly graphs because the number of induced subgraphs may also be exponential in the size of the graph.

The characterization of hereditary clique-Helly graphs given below uses the following definition: an edge e of a triangle T is good, relative to T, if any vertex adjacent to the vertices of e is also adjacent to the other vertex of T.

Theorem 8.5 [106, 90] The following statements are equivalent for any graph G:

(i) G is hereditary clique-Helly;

(ii) G is strong clique-Helly;

(iii) G does not contain an ocular graph as an induced subgraph;

(iv) every triangle of G has a good edge.

Figure 15 shows the ocular graphs.

Problem 8.4 Hereditary clique-Helly graph INSTANCE: A graph G. QUESTION: Is G hereditary clique-Helly?

Algorithm 8.2 (Recognizing hereditary clique-Helly graphs): For every triangle T of G, verify if T contains a good edge.

All the triangles of a graph can be computed in time O(nm). We need O(n) time to verify, for each one, if it contains a good edge. Therefore the complexity of the recognition algorithm for hereditary clique-Helly graphs is O(n^{2}m).

For every integer p ≥ 3, a graph G is p-ocular if V (G) is the union of the disjoint sets W = {w_{1}, w_{2}, ..., w_{p}} and U = {u_{1}, u_{2}, ..., u_{p}}, where W is a complete set, U induces an arbitrary subgraph, and w_{i}, u_{j} are adjacent precisely when i ≠ j. The 3-ocular graph corresponds to the ocular graph defined in [106]. A graph is p-ocular-free if it has not a p-ocular graph as an induced subgraph.

Lemma 8.1 [39] Any (p + 1)-ocular graph is not p-clique-Helly, p ≥ 2.

The following characterization of hereditary p-clique-Helly graphs is a generalization of the one presented above for hereditary clique-Helly graphs. We need one more concept, which is a generalization of a good edge. A p-complete subset C′ of a (p + 1)-complete set C is good, relative to C, if any vertex adjacent to all vertices of C′ is also adjacent to the vertex in C\C′.

Theorem 8.6 [39] The following statements are equivalent for any graph G:

(i) G is strong p-clique-Helly;

(ii) G is hereditary p-clique-Helly;

(iii) G is (p + 1)-ocular-free;

(iv) every (p + 1)-complete set of G contains a good p-complete subset.

Problem 8.5 Hereditary p-clique-Helly graph, fixed p ≥ 2 INSTANCE: A graph G. QUESTION: Is G hereditary p-clique-Helly?

Algorithm 8.3 (Recognizing hereditary p-clique-Helly graphs): For every (p + 1)-complete set C of G, verify if C contains a good p-complete set.

The number of (p + 1)-complete sets in a graph with n vertices is O(n^{p+1}). We need O(np) time to verify, for each one, if it contains a good p-complete set. Therefore the complexity of the above algorithm is O(pn^{p+2}). For fixed p, the algorithm terminates within polynomial time. For p variable, we have the following result:

Problem 8.6 Hereditary p-clique-Helly graph INSTANCE: A graph G and an integer p ≥ 2. QUESTION: Is G hereditary p-clique-Helly?

Theorem 8.7 [39] Hereditary p-clique-Helly graph is NP-hard.

8.3 Other Hereditary Helly Classes of Graphs

A hereditary disk-Helly graph is a graph whose induced subgraphs are disk-Helly. Similarly, we define hereditary biclique-Helly, hereditary open and closed-neighborhood-Helly graphs. The following theorems describe characterizations for these classes, in terms of forbidden induced subgraphs.

Figure 16: Forbidden subgraphs for hereditary disk-Helly graphs

Problem 8.7 Hereditary disk-Helly graph INSTANCE: A graph G. QUESTION: Is G hereditary disk-Helly?

Theorem 8.8 [40] A graph is hereditary disk-Helly if and only if it does not contain the graphs of Figure 16 as induced subgraphs.

Problem 8.8 Hereditary biclique-Helly graph INSTANCE: A graph G. QUESTION: Is G hereditary biclique-Helly?

Theorem 8.9 [61] A graph is hereditary biclique-Helly if and only if it does not contain the graphs of Figure 17 as induced subgraphs.

Problem 8.9 Hereditary open neighborhood-Helly graph INSTANCE: A graph G. QUESTION: Is G hereditary open neighborhood-Helly?

Theorem 8.10 [61] A graph is hereditary open neighborhood-Helly if and only if it does not contain the graphs of Figure 18 as induced subgraphs.

Problem 8.10 Hereditary closed neighborhood-Helly graph INSTANCE: A graph G. QUESTION: Is G hereditary closed neighborhood-Helly?

Theorem 8.11 [61] A graph is hereditary closed neighborhood-Helly if and only if it does not contain the graphs of Figure 19 as induced subgraphs.

Figure 17: Forbidden subgraphs for hereditary biclique-Helly graphs Figure 18: Forbidden subgraphs for hereditary open neighborhood-Helly graphs Figure 19: Forbidden subgraphs for hereditary closed neighborhood-Helly graphs

the electronic journal of combinatorics (2009), #DS17 43

It follows directly from the characterizations of the above considered classes that they can be recognized in polynomial time.

By comparing the above forbidden families, we can also conclude:

Corollary 8.1 Let G be a graph with girth at least 7. Then G is hereditary clique-Helly, hereditary biclique-Helly, hereditary open neighborhood-Helly and hereditary closed neighborhood-Helly.

Figure 20 depicts relations among the above considered hereditary Helly classes of graphs. All graphs shown in the figure are minimal examples. The symbol Ø indicates that no graph exists in the corresponding intersection of graph classes.

Figure 20: Relations among hereditary Helly graph classes

9 Sandwich Problems

In this section we define a class of problems which is a natural generalization of the class of recognition problems.

A graph sandwich problem consists of: given two graphs G_{1} and G_{2}, find a graph G with some desired property, the sandwich graph, such that E(G_{1}) ⊆ E(G) ⊆ E(G_{2}). Graph sandwich problems were defined in the context of Computational Biology [55].

Clearly, the complexity of recognizing the existence of a sandwich graph in a certain class cannot be lower than the recognition of the class itself. Hence, the interest in looking at the complexity of sandwich graph recognition is restricted to those classes of graphs admitting a polynomial-time recognition algorithm. For instance, the recognition of interval sandwich graphs is NP-complete [56]. Below, we report on clique-Helly sandwich graphs.

Problem 9.1 Clique-Helly sandwich graph INSTANCE: Two graphs G_{1}, G_{2} such that E(G_{1}) ⊆ E(G_{2}). QUESTION: Is there a sandwich graph for G_{1} and G_{2} that is clique-Helly?

Theorem 9.1 [33] Clique-Helly sandwich graph is NP-complete.

We can define the sandwich problem for hereditary clique-Helly graphs as we did for clique-Helly graphs.

Problem 9.2 Hereditary clique-Helly sandwich graph INSTANCE: Two graphs G_{1}, G_{2} such that G_{1} ⊆ G_{2}. QUESTION: Is there a sandwich graph for G_{1} and G_{2} which is hereditary clique-Helly?

Theorem 9.2 [33] Hereditary clique-Helly sandwich graph is NP-complete.

The sandwich problems corresponding to the other Helly classes considered in this survey have not been considered so far.

10 Summary of Results

Table 1 summarizes the complexity results of the various algorithmic problems considered in this work. The complexities are expressed in terms of O-notation and correspond to straightforward algorithms realizing the associated characterizations.

Problem  Complexity  Reference
2.1 Helly hypergraph  O(n^{4}m)  [14]
O(Mn^{2} + rn^{3})  [32]
3.1 Clique-Helly graph O(nm^{2}) [40, 97]
O(m^{2})  [77]
9.1 Clique-Helly sandwich  NP-complete  [33]
3.2 Biclique-Helly graph  O(n^{3}m)  [60]
3.3 Helly circular-arc graph  O(n^{3})  [53]
O(n + m)  [67]
4.1 p-Helly hypergraph, fixed p O(n^{p+2}m) = O(Mn^{p+1}) [14]
O(Mn^{p} + prn^{p+1})  [32]
4.2 List p-Helly hypergraph, fixed p ≥ 2 Co-NP-complete [36]
5.1 k-Bounded p-Helly hypergraph, fixed k and p O(nm^{k}k^{p})  Alg. 5.1
5.2 k-Bounded p-Helly hypergraph, fixed p Co-NP-complete [35]
5.3 k-Bounded p-clique-Helly graph, fixed k and p Co-NP-complete  [35]
5.4 Planar 3-bounded clique-Helly graph  O(n^{2})  [3]
6.1 (p, q)-Intersecting hypergraph, fixed q  Co-NP-complete  [36]
6.2 (p, q, s)-Helly hypergraph, fixed p and q  O(n^{b(p+a+1)+1}m^{p} + nm^{p+a}) [38]
6.3 (p, q, s)-Helly hypergraph, fixed q and s  NP-hard  [36]
6.4 (p, q, s)-Helly hypergraph, fixed p and s  Co-NP-complete  [36]
6.5 (2, q)-Helly hypergraph, fixed q  O(n^{3q+1}m)  [36]
O(r^{q}nm^{5})  Alg. 6.3
6.6 (2, q)-Helly hypergraph, fixed r − q O(n(r − q + 2)^{2}m^{r−q+2}) [104]
O(r^{r−q}nm^{5})  Alg. 6.3
7.1 (2, 2)-Clique-Helly graph  O(m^{5})  [28]
7.2 (p, q)-Clique-Helly graph, fixed p and q  O(n^{q(p+3)})  [37]
7.3 (p, q)-Clique-Helly graph, fixed p  NP-hard  [37]
7.4 (p, q)-Clique-Helly graph, fixed q  NP-hard  [37]
7.5 Helly defect  NP-hard  [34]
8.1 Hereditary Helly hypergraph  O(rm^{3})  [106]
O(r^{4}m^{2})  [26]
O(rn^{3})  [32]
8.2 Hereditary p-Helly hypergraph, fixed p ≥ 2 O(rm^{p+1}) [39]
O(prn^{p+1})  [32]
8.3 Hereditary p-Helly hypergraph, p variable  Co-NP-complete  [39]
8.4 Hereditary clique-Helly graph  O(n^{2}m)  [90, 106]
O(m^{2})  [77]
9.2 Hereditary clique-Helly sandwich graph  NP-complete  [33]
8.5 Hereditary p-clique-Helly graph, fixed p ≥ 2  O(n^{p+2})  [39]
8.6 Hereditary p-clique-Helly graph  NP-hard  [39]
8.7 Hereditary disk-Helly graph  O(n^{2}m)  [40]
8.8 Hereditary biclique-Helly graph  O(n^{2}m^{3})  [61]
8.9 Hereditary open neighborhood-Helly graph  O(n^{2}m^{2})  [61]
8.10 Hereditary closed neighborhood-Helly graph O(n^{2}m^{2})  [61]

Table 1: Summary of complexity results. Recall that n is the number of vertices, m is the number of hyperedges or edges, M is the sum of the cardinalities of the hyperedges, r is the rank, a = max{q − s, 0}, and b = min{q, s}.

11 Proposed Problems

To conclude, we propose the following problems:

1. Describe a structural characterization for (2, q)-Helly hypergraphs.

This problem has been posed in [104]. In the article, some different extremal problems have been studied in relation to (2, q)-Helly hypergraphs. A characterization for the case r − q fixed is described in [104]. Algorithm 6.3 of the present survey also considers this special case.

2. Determine the complexity of recognizing (p, q)-Helly hypergraphs, for fixed p. In special, consider p = 2.

Papers [36] and [38] consider some different variations of the problem of recognizing (p, q, s)-Helly hypergraphs. However, the case p fixed and q = s variable has been left open, in particular for p = 2. Clearly, this problem is related to the previous one.

3. Characterize (p, q, s)-clique-Helly graphs.

A characterization of (p, q, s)-Helly hypergraphs is described in [38], while that of (p, q)-clique-Helly appears in [37]. It remains open the case of (p, q, s)-clique-Helly graphs.

4. Determine the complexity of recognizing (p, q, s)-clique-Helly graphs, for fixed p, q.

Clearly, this problem is related to the previous one, and to references [38] and [37].

5. Is there an algorithm to decide if the Helly defect of a graph G is finite?

Helly defect equal to zero corresponds to the case of a clique-Helly graph, and can therefore be recognized in polynomial time. The recognition of graphs having Helly defect 1 is NP-hard [34]. In general, for finite Helly defect, it is unknown even if the problem is decidable. However, for every finite k ≥ 0 there is a graph whose Helly defect is k [21]. There are similar problems within the scope of iterated clique graphs. For instance, it is an open question to know whether the recognition of convergent/divergent graphs is a decidable problem. General divergent graphs have been studied in [72]. Divergence of cographs has been considered in [68], and of circular-arc graphs in [17] and [76]. Convergence of clique-Helly graphs has been examined in [9] and [89].

References

[1] M. O. Albertson and K. L. Collins. Duality and perfection for edges in cliques. Journal of Combinatorial Theory, Series B, 36:298–309, 1984.

[2] L. Alcón, L. Faria, C. M. H. Figueiredo, and M. Gutierrez. Clique graph recognition is NP-complete. In F. V. Fomin, editor, Proceedings of the 32nd Workshop on Graph-Theoretic Concepts on Computer Science (WG’ 2006), volume 4271 of LNCS, pages 269–277. Springer, 2006.

[3] L. Alcón and M. Gutierrez. Cliques and extended triangles. A necessary condition for planar clique graphs. Discrete Applied Mathematics, 141:3–17, 2004.

[4] N. Alon and D. Kleitman. Piercing convex sets and the Hadwiger-Debrunner (p,q)- problem. Advances in Mathematics, 96:103–112, 1992.

[5] N. Amenta. Helly theorems and generalized linear programming. In Symposium on Computational Geometry, pages 63–72, 1993.

[6] H.-J. Bandelt, M. Farber, and P. Hell. Absolute reflexive retracts and absolute bipartite retracts. Discrete Applied Mathematics, 44(1-3):9–20, 1993.

[7] H.-J. Bandelt and E. Pesch. Dismantling absolute retracts of reflexive graphs. European Journal of Combinatorics, 10:210–220, 1989.

[8] H.-J. Bandelt and E. Pesch. Efficient characterizations of n-chromatic absolute retracts. Journal on Combinatorial Theory Series B, 53:5–31, 1991.

[9] H.-J. Bandelt and E. Prisner. Clique graphs and Helly graphs. Journal of Combinatorial Theory, Series B, 51:34–45, 1991.

[10] A. Barg, G. Cohen, S. Encheva, G. Kabatiansky, and G. Zémor. A hypergraph approach to the identifying parent property: The case of multiple parents. SIAM Journal on Discrete Mathematics, 14(3):423–431, 2001.

[11] M. Benke. Efficient type reconstruction in the presence of inheritance. In A. M. Borzyszkowski and S. Sokolowski, editors, Proceedings of Mathematical Foundations of Computer Science (MFCS ’93), volume 711 of LNCS, pages 272–280. Springer, 1993.

[12] C. Berge. Graphes et Hypergraphes. Dunod, Paris, 1970. (Graphs and Hypergraphs, North-Holland, Amsterdam, 1973, revised translation).

[13] C. Berge. Hypergraphs. Gauthier-Villars, Paris, 1987.

[14] C. Berge and P. Duchet. A generalization of Gilmore’s theorem. In M. Fiedler, editor, Recent Advances in Graph Theory, pages 49–55. Acad. Praha, Prague, 1975.

[15] B. Bollobás. Combinatorics. Cambridge University Press, Cambridge, 1986.

[16] A. Bondy, G. Durán, M. C. Lin, and J. L. Szwarcfiter. Self-clique graphs and matrix permutations. J. Graph Theory, 44(3):178–192, 2003.

[17] F. Bonomo. Self-clique Helly circular-arc graphs. Discrete Mathematics, 306:595– 597, 2006.

[18] F. Bonomo, M. Chudnovski, and G. Durán. Partial characterizations of cliqueperfect graphs I: Subclasses of claw-free graphs. Discrete Applied Mathematics, 156:1058–1082, 2008.

[19] F. Bonomo, G. Duran, L. N. Grippo, and M. D. Safe. Partial characterizations of circle graphs. In Proc. of the ALIO-EURO Conference on Combinatorial Optimization and Applications, Buenos Aires, Argentina, 2008.

[20] F. Bonomo, G. Durán, M. Groshaus, and J. L. Szwarcfiter. On clique-perfect and k-perfect graphs. Ars Combinatoria, to appear.

[21] C. F. Bornstein and J. L. Szwarcfiter. On clique convergent graphs. Graphs and Combinatorics, 11:213–220, 1995.

[22] A. Brandstädt, V. Chepoi, and F. Dragan. The algorithmic use of hypertree structure and maximum neighbourhood orderings. Discrete Applied Mathematics, 82(1-3):43–77, 1998.

[23] A. Brandstädt, V. Chepoi, F. Dragan, and V. Voloshin. Dually chordal graphs. SIAM Journal on Discrete Mathematics, 11(3):437–455, aug 1998.

[24] A. Brandstädt, V. B. Le, and J. P. Spinrad. Graph classes: A survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999.

[25] A. Bretto, J. Azema, H. Cherifi, and B. Laget. Combinatorics and image processing. Grafical Models and Image Processing, 59(5):265–277, 1997.

[26] A. Bretto, S. Ubéda, and J. Žerovnik. A polynomial algorithm for the strong Helly property. Information Processing Letters, 81:55–57, 2002.

[27] P. L. Butzer, R. J. Nessel, and E. L. Stark. Eduard Helly (1884-1943): In memoriam, volume 7. Resultate der Mathematik, 1984.

[28] M. R. Cerioli. Edge-clique Graphs (in portuguese). Ph.D. Thesis, COPPE - Sistemas, Universidade Federal do Rio de Janeiro, Rio de Janeiro, 1999.

[29] S. A. Cook. The complexity of theorem-proving procedures. Proc. 3rd Ann. ACM Symp. on Theory of Computing Machinery, New York, pages 151–158, 1971.

[30] J. Daligault, D. Gonçalves, and M. Rao. Diamond-free circle graphs are Helly circle. Submitted.

[31] L. Danzer, B. Grünbaum, and V. L. Klee. Helly’s theorem and its relatives. In Proc. Symp. on Pure Math AMS, volume 7, pages 101–180, 1963.

[32] M. C. Dourado, M. C. Lin, F. Protti, and J. L. Szwarcfiter. Improved algorithms for recognizing p-Helly and hereditary p-Helly hypergraphs. Information Processing Letters, (2008), doi:10.1016/j.ipl.2008.05.013.

[33] M. C. Dourado, P. Petito, and R. B. Teixeira. Helly property and sandwich graphs. In Proceedings of ICGT 2005, volume 22 of Eletronic Notes in Discrete Mathematics, pages 497–500. Elsevier B.V., 2005.

[34] M. C. Dourado, F. Protti, and J. L. Szwarcfiter. On the Helly defect of a graph. Journal of the Brazilian Computer Society, 7(3):48–52, 2001.

[35] M. C. Dourado, F. Protti, and J. L. Szwarcfiter. The Helly property on subfamilies of limited size. Information Processing Letters, 93:53–56, 2005.

[36] M. C. Dourado, F. Protti, and J. L. Szwarcfiter. Complexity aspects of generalized Helly hypergraphs. Information Processing Letters, 99:13–18, 2006.

[37] M. C. Dourado, F. Protti, and J. L. Szwarcfiter. Characterization and recognition of generalized clique-Helly graphs. Discrete Applied Mathematics, 155:2435–2443, 2007.

[38] M. C. Dourado, F. Protti, and J. L. Szwarcfiter. On Helly hypergraphs with variable intersection sizes. Submitted, 2007.

[39] M. C. Dourado, F. Protti, and J. L. Szwarcfiter. On the strong p-Helly property. Discrete Applied Mathematics, 156:1053–1057, 2008.

[40] F. F. Dragan. Centers of Graphs and the Helly Property (in russian). Ph. D. Thesis, Moldava State University, Chisinǎu, 1989.

[41] F. F. Dragan, C. F. Prisacaru, and V. D. Chepoi. Location problems in graphs and the Helly property. Diskretnája Matematica, 1992.

[42] P. Duchet. Proprieté de Helly et problèmes de représentations. In Colloquium International CNRS 260, Problèmes Combinatoires et Théorie de Graphs, pages 117–118, Orsay, France, 1976. CNRS.

[43] P. Duchet. Hypergraphs. In R. L. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, volume 1, pages 381–432, Amsterdam-New York-Oxford, 1995. Elsevier North-Holland.

[44] P. Duchet and H. Meyniel. Ensembles convexes dans les graphes. I: Théorèmes de Helly et de Radon pour graphes et surfaces. European Journal of Combinatorics, 4:127–132, 1983.

[45] G. Durán. Some new results on circle graphs. Matemática Contemporânea, 25:91– 106, 2003.

[46] G. Durán, A. Gravano, M. Groshaus, F. Protti, and J. L. Szwarcfiter. On a conjecture concerning Helly circle graphs. Pesquisa Operacional, pages 221–229, 2003.

[47] G. Durán and M. C. Lin. Clique graphs of Helly circular-arc graphs. Ars Combinatoria, 60:255–271, 2001.

[48] J. Eckhoff. Helly, Radon, and Carathéodory type theorems. In Handbook of Convex Geometry, pages 389–448. North-Holland, 1993.

[49] F. Escalante. Über iterierte clique-graphen. Abhandlungender Mathematischen Seminar der Universität Hamburg, 39:59–68, 1973.

[50] R. Fagin. Acyclic database schemes of various degrees: A painless introduction. In G. Ausiello and M. Protasi, editors, Proceedings of the 8th Colloquium on Trees in Algebra and Programming (CAAP’83), volume 159 of LNCS, pages 65–89, L’Aquila, Italy, mar 1983. Springer.

[51] R. Fagin. Degrees of acyclicity for hypergraphs and relational database systems. Journal of the Association for Computing Machinery, 30:514–550, 1983.

[52] C. Flament. Hypergraphes arborés. Discrete Mathematics, 21:223–226, 1978.

[53] F. Gavril. Algorithms on circular-arc graphs. Networks, 4:357–369, 1974.

[54] M. C. Golumbic and R. E. Jamison. The edge intersection graphs of paths in a tree. Journal of Combinatorial Theory, Series B, 38:8–22, 1985.

[55] M. C. Golumbic, H. Kaplan, and R. Shamir. Graph sandwich problems. Journal of Algorithms, 19:449–473, 1995.

[56] M. C. Golumbic and R. Shamir. Complexity and algorithms for reasoning about time: A graph-theoretic approach. J. ACM, 40:1108–1133, 1993.

[57] J. E. Goodman, R. Pollack, and R. Wenger. Geometric transversal theory. In J. Pach, editor, New Trends in Discrete and Computational Geometry, pages 163– 198. Springer-Verlag, Berlin, 1993.

[58] M. Groshaus, M. C. Lin, and J. L. Szwarcfiter. On neighborhood-Helly classes of graphs. In preparation, 2008.

[59] M. Groshaus and J. L. Szwarcfiter. Biclique graphs. Submitted, 2007.

[60] M. Groshaus and J. L. Szwarcfiter. Biclique-Helly graphs. Graphs and Combinatorics, 23(6):633–645, 2007.

[61] M. Groshaus and J. L. Szwarcfiter. On hereditary Helly classes of graphs. Discrete Mathematics and Theoretical Computer Science, 10(1):71–78, 2008.

[62] H. Hadwiger and H. Debrunner. Uber eine Variante zum Helly’schen Satz. Arch. Math., 8:309–313, 1957.

[63] R. C. Hamelink. A partial characterization of clique graphs. Journal of Combinatorial Theory, 5:192–197, 1968.

[64] P. Hell. Rétractions de graphes. Ph.D. Thesis, Université de Montreal, 1972.

[65] E. Helly. Ueber mengen konvexer koerper mit gemeinschaftlichen punkter, Jahresber. Math. Verein., 32:175–176, 1923.

[66] R. E. Jamison. Partition numbers for trees and ordered sets. Pacific Journal of Mathematics, 96:115–140, 1981.

[67] B. Joeris, M. C. Lin, R. M. McConnell, J. Spinrad, and J. L. Szwarcfiter. Lineartime recognition of Helly circular-arc graphs and models. Algorithmica, to appear.

[68] F. Larrión, C. P. Mello, A. Morgana, V. Neumann-Lara, and M. A. Pizaña. The clique operator on cographs and serial graphs. Discrete Mathematics, 282(1-3):183– 191, 2004.

[69] F. Larrión and V. Neumann-Lara. A family of clique divergent graphs with linear growth. Graphs and Combinatorics, 13:263–266, 1997.

[70] F. Larrión, V. Neumann-Lara, and M. A. Pizaña. Clique divergent clockwork graphs and partial orders. Discrete Applied Mathematics, 141(1-3):195–207, 2004.

[71] F. Larrión, V. Neumann-Lara, and M. A. Pizaña. Graph relations, clique divergence and surface triangulations. Journal of Graph Theory, 51:110–122, 2006.

[72] F. Larrión, V. Neumann-Lara, and M. A. Pizaña. On expansive graphs. European Journal of Combinatorics, to appear.

[73] F. Larrión, V. Neumann-Lara, M. A. Pizaña, and T. D. Porter. A hierarchy of self-clique graphs. Discrete Mathematics, 282(1-3):193–208, 2004.

[74] M. C. Lin, F. J. Soulignac, and J. L. Szwarcfiter. Helly circular-arc graph classes. Submitted.

[75] M. C. Lin, F. J. Soulignac, and J. L. Szwarcfiter. Proper Helly circular-arc graphs. In Andreas Brandstädt, Dieter Kratsch, and Haiko Müller, editors, Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers, volume 4769, pages 248–257. Springer, 2007.

[76] M. C. Lin, F. J. Soulignac, and J. L. Szwarcfiter. The clique operator on circular-arc graphs. Submitted, 2008.

[77] M. C. Lin and J. L. Szwarcfiter. Faster recognition of clique-Helly and hereditary clique-Helly graphs. Information Processing Letters, 103:40–43, 2007.

[78] L. Lovász. Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics, 2:253–267, 1972.

[79] L. Lovász. Combinatorial Problems and Exercises. North-Holland, Amsterdam, 1979.

[80] L. Lovász. Perfect graphs. In R. W. Beineke and R. J. Wilson, editors, Selected Topics in Graph Theory, pages 55–87. Academic Press, New York, N. Y., 1983.

[81] C. L. Lucchesi, C. P. Mello, and J. L. Szwarcfiter. On clique-complete graphs. Discrete Mathematics, 183:247–254, 1998.

[82] J. Matousek and J. Nesetril. Invitation to Discrete Mathematics. Oxford University Press, 1998.

[83] T. A. Mckee and F. R. McMorris. Topics in Intersection Graph Theory. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 1999.

[84] J. W. Moon and L. Moser. On cliques in graphs. Israel Journal of Mathematics, 3:23–28, 1965.

[85] V. Neumman-Lara. A theory of expansive graphs. Manuscript, 1995.

[86] T. Nishizeki and N. Chiba. Planar Graphs: Theory and Algorithms. Annals of Discrete Mathematics 32, North Holland, Amsterdam, New York, Oxford, Tokyo, 1988.

[87] M. C. Paul and S. H. Unger. Minimizing the number of states in incompletely specified sequential switching functions. IRE Transactions Eletronic Computers EC-8, pages 356–367, 1959.

[88] M. A. Pizaña. The icosahedron is clique divergent. Discrete Mathematics, 262(1-3):229–239, 2003.

[89] E. Prisner. Convergence of iterated clique graphs. Discrete Mathematics, 103:199– 207, 1992.

[90] E. Prisner. Hereditary clique-Helly graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 14:216–220, 1993.

[91] E. Prisner. Graph Dynamics. Pitman Research Notes in Mathematics, Longman, 1995.

[92] E. Prisner. Bicliques in graphs I: Bounds on their number. Combinatorica, 20(1):109–117, 2000.

[93] T. M. Przytycka, G. Davis, N. Song, and D. Durand. Graph theoretical insights into evolution of multidomain proteins. In Proceedigns of the 9th Research in Computational Molecular Biology (RECOMB’ 2005), volume 3500 of LNBI, pages 311–325, 2005.

[94] F. S. Roberts and J. H. Spencer. A characterization of clique graphs. Journal of Combinatorial Theory, Series B, 10:102–108, 1971.

[95] P. J. Slater. A characterization of SOFT hypergraphs. Canadian Mathematical Bulletin, 21:335–337, 1978.

[96] J. P. Spinrad. Efficient Graph Representation. American Mathematics Society, Providence, RI, 2003.

[97] J. L. Szwarcfiter. Recognizing clique-Helly graphs. Ars Combinatoria, 45:29–32, 1997.

[98] J. L. Szwarcfiter. A survey on clique graphs. In B. A. Reed and C. L. Sales, editors, Recent Advances in Algorithms and Combinatorics, pages 109–136. Springer-Verlag, New York, N. Y., 2003.

[99] J. L. Szwarcfiter and C. F. Bornstein. Clique graphs of chordal and path graphs. SIAM Journal on Discrete Mathematics, 7(2):331–336, may 1994.

[100] S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa. A new algorithm for generating all the maximal independent sets. SIAM Journal on Computing, 6(3):505–517, sep 1977.

[101] Zs. Tuza. Extremal Problems on Graphs and Hypergraphs (in hungarian). PhD Thesis, Acad. Sci., Budapeste, 1983.

[102] Zs. Tuza. Helly-type hypergraphs and Sperner families. Europ. J. Combinatorics, 5:185–187, 1984.

[103] Zs. Tuza. Helly property in finite set systems. Journal of Combinatorial Theory, Series A, 62:1–14, 1993.

[104] Zs. Tuza. Extremal bi-Helly families. Discrete Mathematics, 213:321–331, 2000.

[105] V. I. Voloshin. On the upper chromatic number of a hypergraph. Australasian Journal of Combinatorics, 11:25–45, 1995.

[106] W. D. Wallis and G.-H. Zhang. On maximal clique irreducible graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 8:187–193, 1990.