Jean-Daniel Boissonnat

Dorian Mazauric

On the complexity of the representation of simplicial complexes by trees *

Keywords: simplicial complexes, hypergraphs, tree representations, NP-complete, approximation algorithms complexes simpliciaux, hypergraphes, representations par des arbres, NP-complet, algorithmes d'approximation

In this paper, we investigate the problem of the representation of simplicial complexes by trees. We introduce and analyze local and global tree representations. We prove that the global tree representation is more efficient in terms of time complexity for searching a given simplex and we show that the local tree representation is more efficient in terms of size of the structure. The simplicial complexes are modeled by hypergraphs. We then prove that the associated combinatorial optimization problems are very difficult to solve and to approximate even if the set of maximal simplices induces a planar graph of maximum degree at most three or a bounded degree hypergraph. However, we prove polynomial time algorithms that compute constant factor approximations and optimal solutions for some classes of instances.

Introduction

In this article, we consider the problem of representing simplicial complexes by compact structures as trees. In addition to decreasing the size of the representation, searching a simplex and updating such a structure must be done efficiently. In this section, we first explain the importance of representing simplicial complexes by trees. We then introduce the notion of tree representation, and explain why we need to introduce some new constraints. We also describe some related works and open questions about the representation of simplicial complexes. We finally summarize our contributions and give the organization of the paper.

Need for a compact structure. Simplicial complexes are used extensively in combinatorial and computational topology. There are many applications that involve simplicial complexes (e.g. topological data analysis and geometric inference). One of the main problems is that the size of the complexes is very large and increases significantly with the dimension of the structures. Consequenlty, the use of simplicial complexes is limited in pratice. An important problem is to store simplicial complexes by using compact structures. One of the most natural and efficient ways of compacting the size of a simplicial complex is to represent it as a rooted node-labeled tree. Intuitively, every maximal simplex is represented by a path between the root and a leaf.

Modeling maximal simplices by hypergraphs. In this paper, we consider the problem of representing all the maximal simplices of a given simplicial complex K by a rooted node-labeled tree. To do that, K is modeled by a hypergraph H = (V, E), where the set of vertices V is the set of vertices of K and the set of hyperedges E is the set of maximal simplices of K. Note that e ⊆ e for all e, e ∈ E, e = e . We deduce that all the results presented in this paper are also valid for representing a hypergraph in which there is no hyperedge that is contained into another hyperedge. We restrict our attention to those hypergraphs we simply call hypergraphs in the sequel.

Notations. Let us define some notations used in the paper. Let H = (V, E) be a hypergraph. Let v ∈ V be any node of H. The set N H (v) represents the set of neighbors of v in H, that is N H (v) = {v ∈ V | v = v, v ∈ e, v ∈ e, e ∈ E}. We define N H [v] = N H (v) ∪ {v} as the closed neighborhood of v. We denote by |e| the size of hyperedge e ∈ E, that is the number of distinct vertices that are contained in e. Let d H = max e∈E |e| be the dimension of H. Let E v = {e \ {v} | v ∈ e, e ∈ E} be the set of all hyperedges of H that contain node v, for which we have removed node v. Let Ēv = {e | v / ∈ e, e ∈ E} be the set of all hyperedges of H that do not contain node v. Let E[v] = {e | v ∈ e, e ∈ E} be the set of all hyperedges of H that contain node v. Let Ē[v] = Ēv . Let ∆ H = max v∈V |E[v]| be the maximum degree of H. Let n = |V|. Let Σ(V) be the set of all the orderings of V. Let σ = (σ 1 , . . . , σ n ) ∈ Σ(V) be any ordering of V. For every e ∈ E, we define σ e = (σ e 1 , . . . , σ e |e| ) as the ordering induced by the subset of nodes of e ∈ E from σ.

Let T = (V, E) be a tree rooted at r ∈ V and let u ∈ V be any node of T . The tree T [u] is the subtree of T rooted at u, that is the tree induced by the set of nodes {u ∈ V | u ∈ V (P u ,r )}, where P u ,r is the simple path in T between u and r. For every u ∈ V \ {r}, let p T (u) be the parent of u in T , that is {p T (u), u} ∈ E and p T (u) / ∈ V (T [u]).

Tree representation. As mentioned before, the problems studied in this paper concern the representation of maximal simplices (hyperedges) by rooted node-labeled trees. The idea is to factorize the representation of the vertices that appear in several maximal simplices (hyperedges), in order to minimize the space used to store a simplicial complex (hypergraph). Let K be any simplicial complex and let H = (V, E) be the hypergraph modeling K. The problem considered in our work is to construct a rooted node-labeled tree that represents H. This notion, called tree representation, is formalized in Definition 1. Definition 1 (tree representation) Let H = (V, E) be a hypergraph. A tree representation of H is defined as a node-labeled tree T = (V, E, L 1 ) rooted at r ∈ V , L 1 : V → V, such that:

1. for every hyperedge e ∈ E, there exists a simple path P e in T between the root r and a leaf such that for all v ∈ e, there exists a node u ∈ V (P e ) \ {r} such that L 1 (u) = v;

2. the number of leaves of T is |E|.

Note that L 1 (r) is arbitrarily chosen. Property [START_REF] Alimonti | Hardness of approximating problems on cubic graphs[END_REF] means that for every hyperedge, there exists a simple path between the root and a leaf that represents this hyperedge. Property [START_REF] Boissonnat | Building efficient and compact, data structures for simplicial complexes[END_REF] states that every simple path between the root and a leaf represents a hyperedge. Thus, there is a bijection between the set of hyperedges and the set of simple paths of the tree.

Example. Figure 1(a) represents a simplicial complex K, Figure 1(b) is the hypergraph H modeling K, and Figure 1(c) depicts a tree representation T of H. Observe that vertex v 4 (v 6 , v 8 , respectively) appears in four (two, respectively) hyperedges but there is a unique node labeled by v 4 (v 6 , v 8 , respectively) in T .

Need for additional constraints and problems. We prove that the notion of tree representation (Definition 1) is not sufficient for designing efficient algorithms for searching, removing, and adding a given maximal simplex in T , and so to update the structure efficiently. Thus, some other constraints are needed for tree representations. Informally, given a hypergraph, the associated combinatorial problems consist in computing a rooted node-labeled tree T such that: (a) T is a tree representation of the hypergraph; (b) T satisfies some additional constraints in order to admit efficient algorithms (e.g. for searching a simplex); (c) T has a minimum number of nodes with respect to the two first properties.

Related works. The Hasse diagram of a simplicial complex K is the graph that associate a node to each simplex τ 1 ∈ K and an edge between two nodes if the associated simplices τ 1 and τ 2 satisfy τ 1 ⊂ τ 2 and dim(τ 1 ) = dim(τ 2 ) -1. The Hasse diagram does not permit to efficiently (in terms of size) represent a simplicial complex. The notion of simplex tree has been introduced in [START_REF] Boissonnat | The simplex tree: An efficient data structure for general simplicial complexes[END_REF] for representing simplicial complexes in a compact way. Recently, in [START_REF] Boissonnat | Building efficient and compact, data structures for simplicial complexes[END_REF], the problem of compressing the simplex tree has been investigated. The constraint is that the compact simplex tree must preserve the functionalities of the original structure (e.g. admitting efficient algorithms for searching a simplex). Our article focus on the global tree representation (equivalent to one of the structures introduced in [START_REF] Boissonnat | Building efficient and compact, data structures for simplicial complexes[END_REF]) and on the local tree representation. These two representations satisfy the additional constraints seen before.

Our contributions. In Section 2, we prove that there is no efficient algorithm for the problem of searching a given maximal simplex in a tree representation. We thus introduce local and global tree representations that permit to design efficient algorithms for the problems of searching, removing, and adding a given maximal simplex. Both these two tree representations are efficient depending on the objective parameter: the local tree representation is to be chosen for the size of the structure and the global tree representation is to be chosen for the time complexity for searching a given simplex.

We then analyze the complexity of the combinatorial optimization problems, namely the tree representation problems, introduced in this paper. In Section 3, we prove that these problems are equivalent when the maximal simplices are all of size two (class of graphs), are NP-complete even in the class of planar graphs of maximum degree at most three, and admit a linear time 2-approximation algorithm for this class of instances.

In Section 4, we show that the tree representation problems are in P when all the vertices are in at most two maximal simplices (hypergraphs with maximum degree at most two), are APX-complete even when all the vertices are in at most three maximal simplices (hypergraphs of maximum degree three), and admit polynomial time constant factor approximation algorithms in the class of bounded degree complexes.

Local and global tree representations of hypergraphs

We first motivate the introduction of the local and global tree representations. We then analyze the complexity of the problem of searching, removing, and adding a given simplex. We finally define the associated combinatorial optimization problems and analyze quantitatively the difference between the different tree representations.

Need for additional constraints

As mentioned before, the problems of searching, removing, and adding a given maximal simplex must admit efficient algorithms. We formally prove in Lemma 1 that there is no efficient algorithm for the problem of searching a given maximal simplex in a tree representation (that it when only the properties of Definition 1 are satisfied). To illustrate that point, consider the tree representation T = (V, E, L 1 ) rooted at r ∈ V depicted in Figure 2(A). We cannot easily verify if the hyperedge e = {a 1 , a 2 , a 3 , a 4 , b 1 , c 1 } belongs to the hypergraph H represented by T . Indeed, the root r of T has two neigbhors u, u ∈ N T (r) such that L 1 (u) = a 1 ∈ e and L 1 (u ) = b 1 ∈ e. Thus, we do not know if hyperedge e is represented by a path (r, u, . . .) or by a path (r, u , . . .).

Lemma 1 (simplex search algorithm for tree representation) Let A be any algorithm for the problem of searching a given maximal simplex. Then, there exists a hypergraph H = (V, E) and a tree representation T of H such that the time complexity of A is Ω(|V| 2 ) = Ω(|V (T )|).

Proof Let n ≥ 1 be any integer. Let H = (V, E) be a hypergraph, where V = {v 1 , . . . , v 2n } and E = {e 1 , . . . , e n } with e i = {v i , v n+1 , . . . , v 2n } for every i ∈ 1, n . We construct a tree representation

T = (V, E, L 1 ) rooted at r ∈ V of H as follows. Let V = {r} ∪ V 1 ∪ . . . ∪ V n ∪ {u 1 , . . . , u n } with V i = {u n+1 i , . . . , u 2n i }. Let E = {{r, u n+1 i } | 1 ≤ i ≤ n} ∪ {{u j i , u j+1 i } | n + 1 ≤ RR n°8647 j ≤ 2n -1, 1 ≤ i ≤ n} ∪ {{u 2n i , u i } | 1 ≤ i ≤ n}. Let L 1 (u j i ) = v j and L 1 (u i ) = v i
for every j ∈ n + 1, 2n and for every i ∈ 1, n .

Let A be any algorithm for the problem of deciding if a given simplex belongs to a tree representation. Assume, without loss of generality, that the maximal simplex is e n ∈ E. Since, for every i ∈ 1, n , the path P i = (r, u n+1 i , . . . , u 2n i ) is such that L 1 (u) ∈ e n for every u ∈ V (P i ) \ {r}, then, in the worst case, Algorithm A visits all nodes of every path P i for every i ∈ 1, n . Thus, the time complexity of Algorithm A is Ω(|V| 2 ) = Ω(|V (T )|).

Consequently, we propose in the next section some additional requirements and we get two more constrained definitions of tree representation.

Definitions and equivalences

We introduce in Definition 2 the notion of local tree representation, a recursively constructed tree that represents a given hypergraph.

Definition 2 (local tree representation

) Let H = (V, E) be a hypergraph. A local tree rep- resentation of H is a node-labeled tree T = (V, E, L 1 , L 2 ) rooted at r ∈ V , L 1 : V → V, L 2 : V → 0, |V| , such that: 1. if |E| = 0, then T = ({r}, ∅); 2. if |E| ≥ 1, then there exists a node u ∈ N T (r), with L 1 (u) = v ∈ V, such that: (a) for every u ∈ N T (r) \ {u}, then L 2 (u) < L 2 (u ); (b) the tree T [u] rooted at r = u is a local tree representation of (V \ {v}, E v ); (c) the tree T \ T [u] rooted at r is a local tree representation of (V \ {v}, Ēv ).
Property (1) deals with the case where there are no hyperedges. Property (2.b) states that all the hyperedges containing v are represented in T [u] and Property (2.c) states that all the other hyperedges are represented in T \ T [u]. Furthermore, as proved in Lemma 4, Property (2.a) allows to search efficiently the path of T that represents a given hyperedge (if it exists). We prove in Lemma 2 an equivalent definition of a local tree representation.

Lemma 2 (equivalence for the local tree representation) Let H = (V, E) be a hypergraph.

A tree T = (V, E, L 1 , L 2 ) rooted at r ∈ V , L 1 : V → V, L 2 : V → 0, |V| , is a local tree representation of H if and only if 1.
T is a tree representation of H (Definition 1), 2. every simple path P e representing e ∈ E is such that for all u ∈ V (P e ) \ {r} and for all

u ∈ N T [p T (u)] (p T (u)) with L 1 (u ) ∈ e, then L 2 (u) < L 2 (u ).
Proof ⇒ Let H = (V, E) be any hypergraph. Let T = (V, E, L 1 , L 2 ) rooted at r ∈ V be any local tree representation of H. We prove that T satisfies the properties of Lemma 2. We prove the result by induction on the number of hyperedges. The result is clearly true for every hypergraph H = (V, E) such that |E| ≤ 1. Assume now that the result is true for every hypergraph H = (V, E) such that |E| ≤ m, for any m ≥ 2. We prove that it is also true for every hypergraph H = (V, E) such that |E| ≤ m + 1. Let H = (V, E) be any hypergraph such that |E| ≤ m + 1 and let

T = (V, E, L 1 , L 2 ) rooted at r ∈ V be any local tree representation of H. Let u ∈ N T (r) such that L 2 (u) < L 2 (u ) for every u ∈ N T (r) \ {u}. Let v = L 1 (u) ∈ V.
By assumption, the tree T [u] rooted at r = u is a local tree representation of (V \ {v}, E v ) and the tree T \ T [u] rooted at r is a local tree representation of (V \ {v}, Ēv ). There are two cases.

• If |E v | ≤ m, then, by induction hypothesis, T [u] and T \ T [u] satisfy the properties of Lemma 2. Thus, T satisfies the properties of Lemma 2 and the result is true for every hypergraph H = (V, E) such that |E| ≤ m + 1.

• If |E v | = m + 1, then we prove the result for T [u] instead of T , and so for (V \ {v}, E v ) instead of (V, E). Indeed, the number of nodes of the hyperedge strictly decreases, that is |V \ {v}| = |V| -1. Thus, this procedure ends with a hypergraph H = (V , E ) such that |E | ≤ m because if there are no nodes in a hypergraph, then there are no hyperedges in it. Finally, T satisfies the properties of Lemma 2 and the result is true for every hypergraph

H = (V, E) such that |E| ≤ m + 1.
⇐ Let H = (V, E) be any hypergraph. Let T = (V, E, L 1 , L 2 ) be any tree rooted at r ∈ V that satisfies the properties of Lemma 2. We prove that T satisfies the properties of Definition 2. We prove the result by induction on the number of hyperedges. The result is clearly true for every hypergraph H = (V, E) such that |E| ≤ 1. Assume now that the result is true for every hypergraph H = (V, E) such that |E| ≤ m, for any m ≥ 2. We prove that it is also true for every hypergraph H = (V, E) such that |E| ≤ m + 1. Let H = (V, E) be any hypergraph such that |E| ≤ m + 1 and let T = (V, E, L 1 , L 2 ) be any tree rooted at r ∈ V that satisfies the properties of Lemma 2 for H.

Let u ∈ N T (r) such that L 2 (u) < L 2 (u ) for every u ∈ N T (r) \ {u}. Let v = L 1 (u) ∈ V. From Property (2) of Lemma 2, every hyperedge e ∈ E[v]
, that is every hyperedge that contains v, is represented by a path (r, u, . . .) in T . Thus, every hyperedge e ∈ Ē[v] = Ēv , that is every hyperedge that does not contain v, is represented by a path (r, u , . . .) in T , for some u ∈ N T (r) \ {u}. Consider the tree T [u] rooted at r = u and the tree T \ T [u] rooted at r. There are two cases.

• If |E v | ≤ m, then, by induction hypothesis, T [u] is a local tree representation of (V \ {v}, E v ),
and T \T [u] is a local tree representation of (V \{v}, Ēv ). Thus, T is a local tree representation of H, and so the result is true for every hypergraph H = (V, E) such that |E| ≤ m + 1.

• If |E v | = m + 1, then we prove the result for T [u] instead of T , and so for (V \ {v}, E v ) instead of (V, E). Indeed, the number of nodes of the hyperedge strictly decreases, that is |V \ {v}| = |V| -1. Thus, this procedure ends with a hypergraph H = (V , E ) such that |E | ≤ m because if there are no nodes in a hypergraph, then there are no hyperedges in it. Finally, T is a local tree representation of H, and so the result is true for every hypergraph

H = (V, E) such that |E| ≤ m + 1.
In conclusion, the properties of Definition 2 and the properties of Lemma 2 are equivalent.

Property [START_REF] Alimonti | Hardness of approximating problems on cubic graphs[END_REF] states that a local tree representation is a tree representation. Property (2) allows to determine efficiently the path in the tree that corresponds to any given hyperedge. Figure 2(B) depicts a local tree representation for some hypergraph.

We now formalize in Definition 3 the notion of global tree representation from an ordering of the set of nodes of a hypergraph. Definition 3 (global tree representation) Let H = (V, E) be a hypergraph. Let σ be any ordering of V. A global tree representation of H is a node-labeled tree

T σ = (V, E, L 1 , L 2 ) rooted at r ∈ V , L 1 : V → V, L 2 : V → 0, |V| , constructed as follows. Set T σ = ({r}, ∅).
For all e ∈ E:

1. let P = (u 0 = r, . . . , u t ) be the maximal path in T σ such that L 1 (u i ) = σ e i for all i ∈ 1, t ;

2. add the path (u e t+1 , . . . , u e |e| ) and the edge {u t , u e t+1 } in T σ ;

E = {{a 1 , a 2 , a 3 , a 4 , b 1 , c 1 }, {a 1 , a 2 , a 3 , a 4 , b 2 , c 2 }, {a 1 , a 2 , a 3 , a 4 , b 3 , c 3 }, {a 1 , a 2 , a 3 , a 4 , b 4 , c 4 }, {b 1 , b 2 , b 3 , b 4 , a 1 , c 5 }, {b 1 , b 2 , b 3 , b 4 , a 2 , c 6 }, {b 1 , b 2 , b 3 , b 4 , a 3 , c 7 }, {b 1 , b 2 , b 3 , b 4 , a 4 , c 8 }, {a 1 , a 2 , a 3 , a 4 , b 1 , b 2 , b 3 , b 4 }}. A filled red node u with i ∈ 1, 4 is such that L 1 (u) = a i and L 2 (u) = i. A white node u with i ∈ 1, 4 is such that L 1 (u) = b i and L 2 (u) = i + 4. A blue node u with i ∈ 1, 8 is such that L 1 (u) = c i and L 2 (u) = i + 8. (A) Tree representation of H. (B) Local tree representation of H. Let u 1 be such that L 1 (u 1 ) = a 1 . The tree T [u 1 ] rooted at u 1 is a local tree representation of (V \ {a 1 }, E a1 ). Note that E a1 = {{a 2 , a 3 , a 4 , b 1 , c 1 }, {a 2 , a 3 , a 4 , b 2 , c 2 }, {a 2 , a 3 , a 4 , b 3 , c 3 }, {a 2 , a 3 , a 4 , b 4 , c 4 }, {b 1 , b 2 , b 3 , b 4 , c 5 }}. The tree T \ T [u 1 ] rooted at r is a local tree representation of (V \ {a 1 }, Ēa1 ). Note that Ēa1 = {{b 1 , b 2 , b 3 , b 4 , a 2 , c 6 }, {b 1 , b 2 , b 3 , b 4 , a 3 , c 7 },

for all

i ∈ t + 1, |e| , set L 1 (u e i ) = σ e i and L 2 (u e i ) = k, where σ k = L 1 (u e i ).
Recall that, for every e ∈ E, σ e = (σ e 1 , . . . , σ e |e| ) is the ordering induced by the subset of nodes of e ∈ E from σ. We prove in Lemma 3 an equivalent definition of the global tree representation.

Lemma 3 (equivalence for the global tree representation

) Let H = (V, E) be a hyper- graph. A tree T = (V, E, L 1 , L 2 ) rooted at r ∈ V , L 1 : V → V, L 2 : V → 0, |V| , is a global tree representation of H if and only if 1. T is a local tree representation of H; 2. for all u, u ∈ V , then L 1 (u) = L 1 (u ) if and only if L 2 (u) = L 2 (u ); 3. for every simple path P = (r, u 1 , . . . , u t ) of T , then L 2 (u i ) < L 2 (u i+1 ) for all i ∈ 1, t -1 .
Property (1) states that a global tree representation is a local tree representation. Property [START_REF] Boissonnat | Building efficient and compact, data structures for simplicial complexes[END_REF] ensures that if two different nodes of the tree represent a same node of the hypergraph, then these two nodes have the same label for L 2 . Property (3) means that every path in the tree is strictly increasing for the labeling function L 2 . Figure 2(C) depicts a global tree representation for some hypergraph.

Proof Let H = (V, E) be any hypergraph. Let n = |V|. ⇐ Let T = (V, E, L 1 , L 2 ) rooted at r ∈ V be any tree that satisfies the properties of Lemma 3. We prove that T is a global tree representation of H. In other words, we prove that there exists an ordering σ

= (σ 1 , . . . , σ n ) of V such that T σ = T is constructed from σ (Definition 3). From Property (2) of Lemma 3, for all u, u ∈ V such that L 1 (u) = L 1 (u ), then L 2 (u) = L 2 (u ). Let σ = (σ 1 , . . . , σ n ) be an ordering of V such that for all u, u ∈ V such that L 1 (u) = σ i and L 1 (u ) = σ j with 1 ≤ i < j ≤ n, then L 2 (u) < L 2 (u ). It follows that, from the ordering σ, we get T σ = T . ⇒ Let T = (V, E, L 1 , L 2 )
be any global tree representation of H rooted at r ∈ V . Let σ = (σ 1 , . . . , σ n ) be an ordering of V such that T σ = T is constructed from σ (Definition 3). We prove that T σ satisfies the properties of Lemma 3. We prove the result by induction on the number m of hyperedges added in T σ . The result is true for m = 0 because T σ = ({r}, ∅) satisfies the properties of Lemma 3 for the hypergraph (∅, ∅). The result is true for m

= 1 because T σ is the path (r, u 1 1 , . . . , u 1 |e1| ) with L 1 (u 1 i ) = σ 1 i and L 2 (u 1 i ) = k, where σ k = L(u j i ) for all i ∈ 1, |e 1 |
. Indeed, the path represents the hyperedge e 1 because every node of e 1 is represented and the path is increasing for L 2 .

Suppose it is true for m added hyperedges, 1 ≤ m < m. We prove it is also true for m + 1. The tree T σ satisfies the properties of Lemma 3 for the hypergraph induced by the set of hyperedges {e 1 , . . . , e m }. We now represent the hyperedge e m +1 . We add in T σ the path (u m +1 t+1 , . . . , u m +1

|e|

) and the edge {u t , u m +1 t+1 }. Recall that t ≥ 0 is the largest integer such that there exists a simple path

P = (r = u 0 , u 1 , . . . , u t ) in T σ with L 1 (u i ) = σ m +1 i for all i ∈ 1, t . We set L 1 (u m +1 i ) = σ m +1 i and we set L 2 (u m +1 i ) = k, where σ k = L(u m +1 i
), for all i ∈ t + 1, |e m +1 | . Thus, T σ satisfies the properties of Lemma 3 for the hypergraph induced by the set of hyperedges {e 1 , . . . , e m +1 }.

Efficient simplex search, remove, and add algorithms

We prove in Lemma 4 (Lemma 5, respectively) that a local (global, respectively) tree representation admits an efficient algorithm for searching, removing, and adding a simplex.

Lemma 4 (simplex search/remove/add algorithm for local tree representation) Let H be any hypergraph and let T be a local tree representation of H. There exists a O(d 2 H log 2 (∆ T ))-time complexity algorithm for the problem of searching/removing/adding a given maximal simplex.

Proof Let H = (V, E) be any hypergraph. Let T = (V, E, L 1 , L 2 ) rooted at r ∈ V be a local tree representation of H. We first prove the result for the problem of searching a simplex. Without loss of generality, assume that the given maximal simplex belongs to H. Let e ∈ E be any hyperedge of H. We prove that the problem of computing the node u ∈ N T (r) such that the path that represents e in T is (r, u, . . .) can be solved in O(d H log 2 (∆ T ))-time. For every node v ∈ e, we compute the node u ∈ N T (r) (if it exists) such that L 1 (u) = v. This can be done in O(log 2 (∆ T ))-time. Note that we suppose that the set of nodes N T (r) is ordered. Since |e| ≤ d H , then we get a O(d H log 2 (∆ T ))-time complexity. This computation is done for every node of the path of T that represents e. Thus, we get a O(d 2 H log 2 (∆ T ))-time complexity algorithm for the problem of searching the path (if it exists) representing a given maximal simplex. Finally, the problem of removing a simplex consists in first searching the path corresponding to this simplex and then removing a subpath of this path, and the problem of adding a simplex consists in searching a path representing a subset of nodes of this simplex.

Lemma 5 (simplex search/remove/add algorithm for global tree representation) Let H be any hypergraph and let T be a global tree representation of H. There exists a O(d H log 2 (∆ T ))time complexity algorithm for the problem of searching/removing/adding a given maximal simplex.

Proof Let H = (V, E) be any hypergraph. Let T = (V, E, L 1 , L 2 ) rooted at r ∈ V be a global tree representation of H. Let σ = (σ 1 , . . . , σ n ) be an ordering of V corresponding to T . Without loss of generality, assume that the given maximal simplex belongs to the hypergraph. Thus, let e ∈ E be any hyperedge of H. We prove that the problem of computing the node u ∈ N T (r) such that the path that represents e in T is (r, u, . . .) can be solved in O(log 2 (∆ T ))-time. Indeed, it is sufficient to search the node v ∈ e such that σ i = v and for every v ∈ e \ {v}, then σ j = v is such that j > i. That computation can be done in O(log 2 (∆ T ))-time. Note that we suppose that the set of nodes N T (r) is ordered. We repeat this computation for every node of the path of T that represents e, and so we get a O(d H log 2 (∆ T ))-time algorithm. Finally, the problem of removing a simplex consists in first searching the path corresponding to this simplex and then removing a subpath of this path, and the problem of adding a simplex consists in searching a path representing a subset of nodes of this simplex.

Note that log 2 (∆ T ) = O(log 2 (|V|)). The time complexity for searching, removing, and adding a given simplex is better for the global tree representation. However, we prove in Section 2.5 that the size of an optimal global tree representation is always greater than the size of an optimal local tree representation. We present in the next section the different combinatorial optimization problems studied in this article.

Combinatorial optimization problems

In this paper, we aim at computing tree representations of a given hypergraph with the smallest number of nodes. Intuitively, we aim at determining the maximum number of nodes that can be factorized in the different tree representations. The problems investigated in this article and some equivalences are formally described below. From Lemma 2, we deduce Corollary 6.

Corollary 6 (equivalence for the local tree representation problem) Let H = (V, E) be any hypergraph. Then, max

* local = -f (V, E) + e∈E |e|, that is |V (T * local )| = f (V, E) + 1, where the function f is defined as follows: f (V, E) = 0 if |E| = 0 and f (V, E) = min v∈V (f (V \ {v}, E v ) + f (V \ {v}, Ēv )) + 1 if |E| ≥ 1.

Comparison between the three tree representations

From Lemma 2 and Lemma 3, we first deduce Property 1. . Note that we do not consider the set of nodes C because every c ∈ C appears in a unique hyperedge and so we cannot factorize any node of the tree corresponding to a node of C. Thus, without loss of generality, we represent these nodes as leaves of the tree. Furthermore, we do not represent the hyperedge {a 1 , . . . , a n , b 1 , . . . , b n }. Indeed, for any tree representation for E defined above, adding this hyperedge consists in adding n -1 nodes (as path) in this tree representation. Thus, we add 2n -1 nodes in order to get the tree representation for the orginal hypergraph.

Claim 1 |V (T * local )| ≤ 5n. Proof Let us construct a local tree representation T local rooted at r ∈ V (T local ) such that |V (T local )| = 5n. Let V (T local ) = {r} ∪ {u 1 , . . . , u n } ∪ {v 1 , . . . , v n } ∪ {u 2 , . . . , u n } ∪ {v 1 , . . . , v n } ∪ {w 1 , . . . , w n }. Set L 1 (u i ) = a i , L 2 (u i ) = i, L 1 (v i ) = b i , L 2 (v i ) = i + n, L 1 (v i ) = b i , L 2 (v i ) = i + n, L 1 (w i ) = b i , and L 2 (w i ) = i + n for all i ∈ 1, n . Set L 1 (u i ) = a i and L 2 (u i ) = i for all i ∈ 2, n -1 . Finally, let E(T local ) = {{r, u 1 }} ∪ {{u i , u i+1 } | 1 ≤ i ≤ n -1} ∪ {{u n , v i } | 1 ≤ i ≤ n} ∪ {u 1 , w 1 } ∪ {{w i , w i+1 } | 1 ≤ i ≤ n -1} ∪ {{r, v 1 }} ∪ {{v i , v i+1 } | 1 ≤ i ≤ n -1} ∪ {{v n , u i } | 2 ≤ i ≤ n}. Figure 2(b) depicts T local for n = 4.
We now prove that T local is an admissible solution for Problem 2. First, for every e ∈ E, there exists a path between the root r and a leaf of T local that corresponds to e. For all i ∈ 1, n , we associate the path (r, u 1 , . . . , u n , v i ) with the hyperedge {a 1 , . . . , a n , b i }. For all i ∈ 2, n , we associate the path (r, v 1 , . . . , v n , u i ) with the hyperedge {b 1 , . . . , b n , a i }. We finally associate the path (r, u 1 , v 1 , . . . , v n ) with the hyperedge {b 1 , . . . , b n , a 1 }. By construction of L 2 , T local is an admissible solution for Problem 2. We get that

|V (T * local )| ≤ |V (T local )| = 5n. RR n°8647 Claim 2 |V (T * global )| ≥ n 2 .
Proof We show that any global tree representation T global is such that |V (T global )| ≥ n 2 . Let us consider any ordering (σ 1 , . . . , σ 2n ) of V. Without loss of generality, we assume that σ 1 ∈ A. Let α 1 , β 1 , . . . , α n , β n and t a , t b be such that: Recall that we assume that σ i ∈ A for all i ∈ 1, α 1 , and that From T A1,B1 , the minimum number of nodes we have to add in order to represent the set of hyperedges E A1,B1 = {{a 1 , . . . , a n , b}

           σ i ∈ A for all i ∈ 1 + j-1 k=1 α k + β k , 1 + α j + j-1 k=1 α k + β k , for all j ∈ 1, n ; σ i ∈ B for all i ∈ 1 + α j + j-1 k=1 α k + β k , 1 + j k=1 α k + β k for all j ∈ 1, n ; α j ≥ 1 for all j ∈ 1, t a ; α j = 0 for all j ∈ t a + 1, n ; β j ≥ 1 for all j ∈ 1, t b ; β j = 0 for all j ∈ t b + 1, n ; n k=0 α k = n; n k=0 β k = n.
σ i ∈ B for all i ∈ α 1 + 1, α 1 + β 1 . Let us consider V A1,B1 = A 1 ∪ B 1 with A 1 = {a 1 , . . . , a α1 } and B 1 = {b 1 , . . . , b β1 }, and E A1,B1 = {{a 1 , . . . , a α1 , b} | b ∈ B 1 } ∪ {{b 1 , . . . , b β1 , a} | a ∈ A 1 }. The global tree representation T A1,B1 of (V A1,B1 , E A1,B1 ), with the ordering (a 1 , . . . , a α1 , b 1 , . . . , b β1 ), is such that |V (T A1,B1 )| = α 1 β 1 + 2α 1 . More precisely, V (T A1,B1 ) = {r} ∪ {u 1 , . . . , u α1 } ∪ {u 2 , . . . , u α1 } ∪ {v 1 , . . . , v β1 } ∪ α1 i=1 {v i 1 , . . . , v i β1 }. Furthermore, L 1 (u j ) = a j for all j ∈ 1, α 1 ; L 1 (u j ) = a j for all j ∈ 2, α 1 ; L 1 (v j ) = b j for all j ∈ 1, β 1 ; L 1 (v i j ) = b j for all j ∈ 1, β 1 and for all i ∈ 1, α 1 . We set E(T A1,B1 ) = {r, u 1 } ∪ {{r, u j } | 2 ≤ j ≤ α 1 } ∪ {{u j , u j+1 } | 1 ≤ j ≤ α 1 -1} ∪ {{u α1 , v j } | 1 ≤ j ≤ β 1 } ∪ {u 1 , v 1 1 } ∪ {{u i , v i 1 } | 2 ≤ i ≤ α 1 } ∪ {{v i j , v i j+1 } | 1 ≤ i ≤ α 1 , 1 ≤ j ≤ β 1 -1}. We get |V (T A1,B1 )| = α 1 β 1 + 2α 1 + β 1 .
| b ∈ B 1 } ∪ {{b 1 , . . . , b n , a} | a ∈ A 1 }, is α 1 (n - β 1 ) + β 1 (n -α 1 )
. Indeed, we obtain this number of additional nodes for any ordering for the set of nodes {a α1+1 , . . . , a n , b β1+1 , . . . , b n }. The resulting tree T A1,B1 is then such that

|V (T A1,B1 )| = n(α 1 + β 1 ) -α 1 β 1 + 2α 1 + β 1 .
In order to represent the set of hyperedges {{a 1 , . . . , a n , b}

| b ∈ B \ B 1 } ∪ {{b 1 , . . . , b n , a} | a ∈ A \ A 1 }
, we now add new nodes from T A1,B1 . By construction, we can only use 2α 1 nodes of T A1,B1 , namely {r, u 1 , . . . , u α1 , u 2 , . . . , u α1 }, because there is a unique hyperedge that contains the subset of nodes {a 1 , . . . , a α1,bj } for all j ∈ 1, n , and there is a unique hyperedge that contains the subset of nodes {b 1 , b 2 , a j } for all j ∈ 1, n .

Thus, the total number of nodes

|V (T global )| is at least |V (T A1,B1 )| -2α 1 plus the minimum number of nodes |V | to represent the set of hyperedges E = {{a α1+1 , . . . , a n , b} | b ∈ B \ B 1 } ∪ {{b β1+1 , . . . , b n , a} | a ∈ A \ A 1 }. By induction hypothesis, |V | ≥ (n -α 1 )(n -β 1 ). We finally get |V (T global )| ≥ |V (T A1,B1 )| -2α 1 + |V | ≥ n(α 1 + β 1 ) -α 1 β 1 + β 1 + (n -α 1 )(n -β 1 ). Thus, we get |V (T global )| ≥ n 2 = |A||B|, and so |V (T * global )| ≥ n 2 .
The two previous claims conclude the proof of Lemma 8.

To summarize, both local and global tree representations are efficient depending on the objective parameter (size of the optimal representation or time complexity for searching/removing/adding a given simplex).

RR n°8647

3 Computing optimal tree representations is difficult even for graphs

We consider here the class of graphs (hyperedges of size two). We prove in Theorem 11 that the decision variants of the tree representation problem, the local tree representation problem, and the global tree representation problem are NP-complete. Our NP-completeness result holds when the graph has no triangle. On the positive side, we show that there exists a linear time 2-approximation algorithm for these problems. We first prove in Lemma 9 that the three tree representation problems are equivalent in graphs. Let us first construct

T global = (V , E , L 1 , L 2 ) of G such that |V | ≤ |V |. Let N T (r) = {u 1 , . . . , u k }, where k = |N T (r)
| is the degree of r in T . Without loss of generality, assume that L 1 (u i ) = L 1 (u j ) for every i ∈ 1, k and for every j ∈ 1, i . Indeed, otherwise, we consider in our construction the tree obtained by merging any two nodes u ∈ N T (r) and

u ∈ N T (r) such that L 1 (u) = L 1 (u ). The construction of T global rooted at r ∈ V from T is sequential. Initially, set T global = T , that is V = V , E = E, and L 1 = L 1 . Let L 2 (u ) = 0 for every u ∈ V . Observe that |V | = |V |. Let N T global (r ) = {u 1 , . . . , u k }.
Then, for i = 1, . . . , k, we apply the following procedure. Let

F = {{u j , u } ∈ E | L 1 (u ) = L 1 (u i ), i < j ≤ |N T global (r )|}.
For every e = {u j , u } ∈ F , for some j ∈ i + 1, |N T global (r )| , we remove e from E and we remove u fron V ; and we add u in V and we add In the reduction of the proof of Theorem 11, we use the vertex cover problem. Let G = (V, E) be any graph. A set X ⊆ V is a vertex cover of G if and only if for all {u, v} ∈ E, then {u, v} ∩ X = ∅. The vertex cover problem consists in computing the minimum k such that there exists a vertex cover X of G of size |X| = k. The decision variant of the vertex cover problem is NP-complete even for the class of cubic graphs [START_REF] Garey | Some simplified NP-complete problems[END_REF] and for the class of planar graphs of degree at most three [START_REF] Garey | The rectilinear Steiner tree problem is NP-complete[END_REF]. The set X = {v 1 , v 6 , v 8 } ⊆ V of filled red nodes is an optimal solution for the vertex cover problem for the graph G = (V, E) depicted in Figure 3 . We now prove that the decision variant of the vertex cover problem is NP-complete even for graphs without triangle. Actually, we prove a stronger result in Lemma 10. Recall that

{u i , u } in E with L 1 (u ) = L 1 (u j ). Let L 2 (u) = i for every u ∈ V such that L 1 (u) = L 1 (u i ). Finally, consider the set of nodes X = {u ∈ V \ {r } | L 2 (u ) = 0} for which L 2 has not been defined. Let L 1 (X) = {L 1 (u ) | u ∈ X} ⊂ V. Without loss of generality, let L 1 (X) = {v k+1 , . . . , v |V| }. Then, for i = k + 1, . . . , v |V| , set L 2 (u) = i for every u ∈ V such that L 1 (u) = v i .
N G [v] is the close neighborhood of any node v ∈ V (G) in G, that is N G [v] = N G (v) ∪ {v}.

Lemma 10 The decision variant of the vertex cover problem is NP-complete even if the graph

G = (V, E) is planar, |N G (v)| ≤ 3, and |N G (v) ∩ N G (v )| ≤ 1 for all v, v ∈ V, v = v .
Proof In [START_REF] Garey | The rectilinear Steiner tree problem is NP-complete[END_REF], the vertex cover problem has been proved NP-complete in the class of planar graphs of degree at most three. Let G = (V, E) be any planar graph of degree at most three. Let n = |V| and let m = |E|. Let k ≥ 1 be any integer. We now construct a graph

G = (V , E ) from G such that |N G (u)| ≤ 3 and |N G (u) ∩ N G (v)| ≤ 1 for all u, v ∈ V , u = v. Let V = {v 1 , . . . , v n } and let E = {e 1 , . . . , e m }. Set V = V ∪ {u 1 , u 1 , . . . , u m , u m }. Set E = {{u i , u i } | 1 ≤ i ≤ m} ∪ W , where W is constructed as follows. If e t = {v i , v j } ∈ E, 1 ≤ i < j ≤ n, 1 ≤ t ≤ m, then {v i , u t } ∈ W and {v j , u t } ∈ W .
To summarize, the graph G is constructed from G by replacing every edge of G by a path composed of four nodes.

We now prove that there exists a vertex cover X of G of size |X| ≤ k if, and only if, there exists a vertex cover of G of size |X | ≤ k + m.

⇒ Assume that there exists a vertex cover X of G of size |X| ≤ k. We prove that there exists a vertex cover of G of size |X | ≤ k + m. Without loss of generality, assume that |X| = k and that X = {v 1 , . . . , v k }. We construct X as follows. For every edge e t = {v i , v j } ∈ E, 1 ≤ i < j ≤ n, 1 ≤ t ≤ m, then u t ∈ X . Note that v i ∈ X because i < j and X ∩ {v i , v j } = ∅. Finally we add X into X . We get that X = |X| + m = k + m. The set X is a vertex cover of G because X is a vertex cover of G and for every path (v i , u t , u t , v j ) of G that replaces the edge e t = {v i , v j } ∈ E,

1 ≤ i < j ≤ n, 1 ≤ t ≤ m, then v i , u t ∈ X .
⇐ Assume that there exists a vertex cover of G of size |X | ≤ k + m. We prove that there exists a vertex cover X of G of size |X| ≤ k. By construction of G , {u t , u t } ∩ X = ∅ for all t ∈ 1, m . Set X = X ∩ V. By the previous remark, |X| ≤ k. If X is not a vertex cover of G, then it means that there exists an edge e

t = {v i , v j } ∈ E, 1 ≤ i < j ≤ n, 1 ≤ t ≤ m, such that {v i , v j } ∩ X = ∅.
But since X is a vertex cover of G , then it means that u t , u t ∈ X , and so that |X \ V| ≥ m + 1 and |X| < k. We add v i in X. If X is a vertex cover of G, then it is done. Otherwise, we apply the same construction while X is not a vertex cover of G.

Finally, we have proved that there exists a vertex cover X of G of size |X| ≤ k if, and only if, there exists a vertex cover of G of size |X | ≤ k + m. Note that the construction of G can be done in polynomial time in the size of G. Thus, the decision variant of the vertex cover problem is NP-complete even if the graph G = (V , E ) is a planar graph of degree at most 3 and

|N G (u) ∩ N G (v)| ≤ 1 for all u, v ∈ V , u = v.
To illustrate the construction described in the proof of Lemma 10, Figure 4

(a) represents a planar graph G = (V, E) with V = {v 1 , v 2 , v 3 , v 4 , v 5 } and E = {{v 1 , v 2 }, {v 1 , v 3 }, {v 2 , v 3 }, {v 2 , v 4 }, {v 3 , v 5 }, {v 4 , v 5 }}. The maximum degree of G is three. A node with the integer i ∈ 1, 6 represents v i ∈ V. Note that |N G (v 2 ) ∩ N G (v 4 )| = 2. The set of red nodes represents a minimum vertex cover X = {v 1 , v 3 , v 4 } of G of size |X| = 3. Figure 4(b) represents the planar graph G = (V , E ) constructed from G (proof of Lemma 10). The maximum degree of G is three. Furthermore, we have |N G (v) ∩ N G (v )| ≤ 1 for all v, v ∈ V , v = v . The set of red nodes in Figure 4(b) represents a minimum vertex cover X of G of size |X | = |X| + |E| = 9.
We now prove Theorem 11.

Theorem 11 The decision variants of the tree representation problems are NP-complete even if the graph

G = (V, E) is planar, |N G (v)| ≤ 3, and |N G (v) ∩ N G (v )| ≤ 1 for all v, v ∈ V, v = v .
Proof From Lemma 9, it is sufficient to prove the NP-completeness of the decision variant of the local tree representation problem. First, since the problem of deciding if a tree is a local tree representation can be clearly solved in polynomial time, then the decision variant of the local tree representation problem is in NP.

RR n°8647

(a) (b)

Figure 3: (a) Graph G = (V, E) with V = {v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 , v 8 , v 9 } and E = {{v 1 , v 2 }, {v 1 , v 4 }, {v 1 , v 5 },
)| = 1 + |X| + |E| = 15. A node u with i ∈ 1, 9 is such that L 1 (u) = v i . Furthermore, L 2 (u) = 1 if L 1 (u) = v 1 , L 2 (u) = 2 if L 1 (u) = v 6 , L 2 (u) = 3 if L 1 (u) = v 8 , L 2 (u) = 4 if L 1 (u) = v 2 , L 2 (u) = 5 if L 1 (u) = v 3 , L 2 (u) = 6 if L 1 (u) = v 4 , L 2 (u) = 7 if L 1 (u) = v 5 , L 2 (u) = 8 if L 1 (u) = v 7 , and L 2 (u) = 9 if L 1 (u) = v 9 .
Let G = (V, E) be any graph and let k ≥ 1 be any integer. Let n = |V| and let V = {v 1 , . . . , v n }. Let m = |E| and let E = {e 1 , . . . , e m }. Since we consider the class of graphs, then any local tree representation T of G has m leaves and has height 2.

We prove that there exists a local tree representation T of G such that |V (T )| ≤ m + k + 1 if and only if there exists a vertex cover X ⊆ V of G of size |X| ≤ k.

⇐ Suppose there exists a vertex cover X ⊆ V of G of size |X| ≤ k. We prove that there exists a local tree representation T of G such that |V (T )| ≤ m + k + 1. Without loss of generality, assume that X = {v 1 , . . . , v k }. Since X is a minimum vertex cover of G, then for all v ∈ X, there exists e = {v, v } ∈ E, v ∈ V, such that v / ∈ X. Indeed, otherwise, we would have a vertex cover X = X \ {v} of size |X | ≤ k -1, a contradiction because X is a minimum vertex cover of G. We now construct a local tree representation

T = (V, E, L 1 , L 2 ) rooted at r ∈ V of G. Let N T (r) = {u 1 , . . . , u k } be the set of neighbors of r such that L 1 (u i ) = v i and L 2 (u i ) = i for all i ∈ 1, k . For all i ∈ 1, k , let V i = {v j ∈ V | {v i , v j } ∈ E, i < j ≤ n}. For all i ∈ 1, k , let N T (u i ) \ {r} = {u i j | v j ∈ V i , i < j ≤ n} be the set of neighbors of u i (but r) in T . For all i, j, 1 ≤ i ≤ k, i < j ≤ n, such that u i j ∈ N T (u i ) \ {r}, we set L 1 (u i j ) = v j and L 2 (u i j ) = k + 1.
Thus, the number of nodes is |V (T )| = m + k + 1. We finally prove that T satisfies the properties of Definition 2 (local tree representation). We first show that T is a tree representation. Since X = {v 1 , . . . , v k } is a vertex cover of G, then every edge e = {v i , v j } ∈ E is such that 1 ≤ i < j ≤ n and i ≤ k. Thus, by construction of T , the path P e = (r, u i , u i j ) represents the edge e, that is

L 1 (u i ) = v i and L 1 (u i j ) = v j .
By construction, the number of leaves of T is m. Thus, T is a tree representation of G. We finally prove that T satisfies the second property of Lemma 2. Consider any edge e = {v i , v j } ∈ E, 1 ≤ i < j ≤ n, i ≤ k, that is represented by the path P e = (r, u i , u i j ) with L 1 (u i ) = v i and L 1 (u i j ) = v j . Then, there is no node u ∈ N T (r) such that L 1 (u) = v i , and for every node u ∈ N T (r) such that L 1 (u) = v j , we necessarily have L 2 (u) > i = L 2 (u i ). Thus, T is a local tree representation of G.

⇒ Suppose that there exists a local tree representation T rooted at r ∈ V (T ) of G such that |V (T )| ≤ m + k + 1. We prove that there exists a vertex cover X ⊆ V of G of size |X| ≤ k. As RR n°8647 previously mentioned, the number of leaves of T is m. Thus, the number of neigbhors of r in T is

|N T (r)| ≤ k.
We first prove, by contradiction, that L 1 (u) = L 1 (u ) for all u, u ∈ N T (r) with u = u . Suppose that there exist two nodes u, u ∈ N T (r) such thatL 1 (u) = L 1 (u ). Since |e| = 2 for all e ∈ E, then u and u are not leaves of T . Thus, there exist two nodes u 1 , u 1 ∈ V (T ) such that u 1 ∈ N T (u) \ {r} and u 1 ∈ N T (u ) \ {r}. Then, for all possible values for L 2 (u) and for L 2 (u ), the second property of Definition 2 is not satisfied for the path (r, u, u 1 ) that represents {L 1 (u), L 1 (u 1 )} ∈ E or for the path (r, u , u 1 ) that represents {L 1 (u ), L 1 (u 1 )} ∈ E. Indeed, we cannot have L 2 (u) < L 2 (u ) and L 2 (u ) < L 2 (u). We get a contradiction because T is a local tree representation of G. Thus, L 1 (u) = L 1 (u ) for all u, u ∈ N T (r) with u = u .

Let N T (r) = {u 1 , . . . , u k }. Recall that |N T (r)| ≤ k because the number of leaves of T is m and |V (T )| ≤ m + k + 1. Without loss of generality, set L 1 (u i ) = v i for all i ∈ 1, k . Thus, for every e = {v, v } ∈ E, there exists i ∈ 1, n such that v i ∈ {v, v } and such that there exists u ∈ N T (u i ) \ {r} with L 1 (u) ∈ {v, v }, v i = L 1 (u). We deduce that every edge e ∈ E is covered by X = {v 1 , . . . , v k }, and so that there exists a vertex cover of G of size |X| = k.

Since the decision variant of the vertex cover problem is NP-complete even if the graph

G = (V, E) is planar, |N G (v)| ≤ 3, and |N G (v) ∩ N G (v )| ≤ 1 for all v, v ∈ V, v = v .
Lemma 10, then the decision variants of the tree representation problems are NP-complete for this class of graphs.

Despite this NP-hardness result, a maximal matching of G, that can be greedily obtained in linear time, gives a 2-approximation algorithm for the vertex cover problem, and so for the tree representation problems (Corollary 12).

Corollary 12 Let G be any graph. There is a linear time algorithm that computes max such that

2 max ≥ max * = max * local = max * global . RR n°8647 (

Tree representations of bounded degree hypergraphs

In this section, we study the relation between the complexity of the tree representation problems and the maximum degree ∆ H = max v∈V |E[v]| of the hypergraphs. We prove that the tree representation problems are in P when ∆ H ≤ 2, are APX-complete even if ∆ H = 3, and admit a polynomial time k-approximation algorithm when ∆ H ≤ k.

A polynomial time algorithm for hypergraphs of degree two

In Theorem 13, we prove a polynomial time algorithm for the global and local tree representation problems for hypergraphs of maximum degree at most two. To do that, we first define the notion of intersection edge-weighted graph of a hypergraph and the notion of node-weighted line graph.

Let H = (V, E) be a hypergraph. The intersection edge-weighted graph G = (E, I, w) of H is such that for all nodes e, e ∈ E, there is an edge {e, e } ∈ I if and only if e ∩ e = ∅. Furthermore, w e,e = |e ∩ e | for all {e, e } ∈ I. The node-weighted line graph L = (I, E , w ) of G is such that for all nodes i 1 = {e 1 , e 1 }, i 2 = {e 2 , e 2 } ∈ I, there is an edge {i 1 , i 2 } ∈ E if and only if {e 1 , e 1 } ∩ {e 2 , e 2 } = ∅. Furthermore, w i = w e,e for all i = {e, e } ∈ I. Figures 5(b) and (c) illustrate the previous constructions for the hypergraph depicted in and Figure 5(a).

In order to prove Theorem 13, we define the notion of independent set and the associated optimization problem. Given a graph G = (V, E), a set X ⊆ V is an independent set of G if for every v ∈ X, then N G (v) ∩ X = ∅. The maximum independent set problem consists in computing the maximum k such that there exists an independent set X of G of size |X| = k. The maximum independent set problem is well known to be hard to approximate. For instance, it is APX-complete in the class of cubic graphs [START_REF] Alimonti | Hardness of approximating problems on cubic graphs[END_REF]. A cubic graph is a 3-regular graph, that is every node has degree 3.

Theorem 13

The global and local tree representation problems are in P for hypergraphs with maximum degree at most two.

Proof Let H = (V, E) be a hypergraph such that |E[v]| ≤ 2 for all v ∈ V. Thus, |{u ∈ V (T * global ) | L 1 (u) = v}| ≤ 2 for all v ∈ V.
Then, the global tree representation problem is equivalent to the problem of maximizing the number of nodes

u such that |{u ∈ V (T * global ) | L 1 (u) = v}| = 1. Observe that |{u ∈ V (T * global ) | L 1 (u) = v}| = 1 for all v ∈ V such that |E[v]| = 1. Thus, in the following, we only consider nodes v ∈ V such that |E[v]| = 2. For any two nodes v, v ∈ V such that E[v] ∩ E[v ] = ∅ and E[v] = E[v ]
(that is such that there exist a hyperedge containing both v and v , a hyperedge containing v but not containing v , and a hyperedge containing v but not containing v), then we have

|{u ∈ V (T * global ) \ {r} | L 1 (u) = v}| + |{u ∈ V (T * global ) \ {r} | L 1 (u ) = v }| ≥ 3. Thus, by the first remark, we cannot have |{u ∈ V (T * global ) \ {r} | L 1 (u) = v}| = 1 and |{u ∈ V (T * global ) \ {r} | L 1 (u ) = v }| = 1. Equivalently, this means that two nodes v, v ∈ V, v is in the intersection i 1 = {e 1 , e 1 } ∈ I and v is in the intersection i 2 = {e 2 , e 2 } ∈ I, {i 1 , i 2 } ∈ E , are such that |{u ∈ V (T * global ) \ {r} | L 1 (u) = v}|+|{u ∈ V (T * global )\{r} | L 1 (u ) = v }| ≥ 3.
Thus, since the global tree representation problem is equivalent to maximize the number of nodes u such that |{u ∈ V (T * global ) | L 1 (u) = v}| = 1, then the global tree representation problem is equivalent to the maximum weighted independent set problem for L. Finally, since L is a node-weighted line graph of a graph, then the maximum weighted independent set problem for L is in P [START_REF] Th | Combinatorial Optimization and Theoretical Computer Science -Interfaces and Perspectives: 30th Anniversary of the LAMSADE[END_REF], and so the global tree representation problem is in P.

APX-hardness result for hypergraphs of degree three

We prove in Theorem 20 that if the maximum degree of the hypergraph is three, then the global and local tree representation problems are APX-complete. In other words, there is a constant k > 1 such that there is no polynomial time k-approximation algorithm for the global and local tree representation problems, unless P = NP. In our reduction, we use a new problem, called induced induced-star decomposition problem (IISD problem). We formalize this decomposition and the corresponding optimization problem in Definition 4 and Definition 5.

Let G = (V, E) be a graph. Let k ≥ 0. The graph S induced by the set of nodes {v, v 0 , . . . , v k } ⊆ V is an induced star of center v if and only if {v, v i } ∈ E and {v i , v j } / ∈ E for all i, j, 0 ≤ i < j ≤ k. Let S, S be two induced stars of G. The distance between S et S is

d G (S, S ) = min v∈V (S),v ∈V (S ) d G (v, v ),
where d G (v, v ) is the usual distance between two nodes, that is the number of edges of a shortest path between v and v in G. We prove in Theorem 16 that the IISD problem is APX-complete in the class of cubic graphs. To do that, we use the fact that the maximum independent set problem is APX-complete in the class of cubic graphs [START_REF] Alimonti | Hardness of approximating problems on cubic graphs[END_REF]. We first show in Lemma 14 that the IISD problem is APX-hard in the class of cubic graphs. We then prove in Lemma 15 that the IISD problem is in APX in that class of graphs.

Lemma 14

The IISD problem is APX-hard in the class of cubic graphs.

Proof We prove the result by contradiction. Let us assume that for every k > 1, there is a polynomial time k-approximation algorithm for the IISD problem in the class of cubic graphs. Thus, there is a polynomial time algorithm that computes an IISD S of any cubic graph

G = (V, E) such that k( S∈S 1 + |V (S)|) ≥ S∈S * 1 + |V (S)|
, where S * is an optimal solution for the IISD problem for G. We have

S∈S * 1 + |V (S)| ≥ 2|X * M IS | because S * is optimal, where X *
M IS is a maximum independent set of G. For every i ∈ {1, 2, 3, 4}, let us consider the independent set X i ⊂ V of G induced by the centers of all induced stars of S composed of exactly i node(s). Note that |X 1 ∪ X 2 ∪ X 3 ∪ X 4 | = |S| because G has maximum degree three and because S is an IISD of G. We get that k(2|X

1 | + 3|X 2 | + 4|X 3 | + 5|X 4 |) ≥ 2|X * M IS | because S∈S 1 + |V (S)| = 2|X 1 | + 3|X 2 | + 4|X 3 | + 5|X 4 |. Let X app = X 1 ∪ X 2 ∪ X 3 ∪ X 4 .
Note that X app is an independent set of G. We obtain that 5k/2|X app | ≥ |X * M IS |. Thus, we get a polynomial time (5k/2)-approximation for the maximum independent set problem in the class of cubic graphs for every k > 1. A contradiction because the maximum independent set problem is APX-hard in the class of cubic graphs [START_REF] Alimonti | Hardness of approximating problems on cubic graphs[END_REF]. Therefore, the IISD problem is APX-hard in the class of cubic graphs.

Lemma 15

The IISD problem is in APX in the class of cubic graphs.

Proof Let c > 1 be a constant such that there is a polynomial time c-approximation algorithm for the maximum independent set problem for the class of cubic graphs. Such a constant c exists because the maximum independent set problem is in APX in the class of cubic graphs [START_REF] Alimonti | Hardness of approximating problems on cubic graphs[END_REF]. In other words, there is a polynomial time algorithm that computes a maximum independent set X app M IS of any cubic graph G = (V, E) such that c|X app M IS | ≥ |X * M IS |, where X * M IS is an optimal solution for the maximum independent set problem for G. Since G has maximum degree three, then every induced star of G is composed of at most four nodes. Thus, S∈S * 1 + |V (S)| ≤ 5|X * M IS |, where S * is an optimal solution for the IISD problem for G. We deduce that for any constant c ≥ 5c, then 2c

|X app M IS | ≥ 5|X * M IS | ≥ S∈S * 1 + |V (S)|.
Since X app M IS is an IISD of G, we conclude that the previous polynomial time c-approximation algorithm for the maximum independent set problem gives a 5c-approximation algorithm for the IISD problem.

Lemma 14 and Lemma 15 prove Theorem 16.

Theorem 16

The IISD problem is APX-complete in the class of cubic graphs.

We prove in Lemma 17 that any cubic graph can be labeled in a specific way. The properties of this labeling will be useful to prove the main result of this section (Theorem 20).

Lemma 17 Given a cubic graph G = (V, E), there exist two labeling functions L V and L E , L V : V → N 3 and L E : E → N such that:

1. for every v ∈ V such that L V (v) = {a 1 , a 2 , a 3 }, then a i = a j for all 1 ≤ i < j ≤ 3,

for every

u, v ∈ V such that {u, v} / ∈ E, then |L V (u) ∩ L V (v)| = 0, 3. for every {u, v} ∈ E, then |L V (u) ∩ L V (v)| = 1 and L E ({u, v}) = L V (u) ∩ L V (v),
4. for every e, e ∈ E, then L E (e) = L E (e ).

Proof Our proof is constructive. Let n = |V | and V = {v 1 , . . . , v n }. Set L V (v 1 ) = {1, 2, 3}. Let e 1 , e 2 , e 3 be the three adjacent edges of v 1 . For every j ∈ {1, 2, 3}, set L E (e j ) = j. Suppose that the properties are satisfied for the set of nodes {v 1 , . . . , v i } with 1 ≤ i ≤ n -1, and the set of edges that have at least one incident node in {v 1 , . . . , v i }. Note that for every edge e ∈ E that has exactly one incident node in {v 1 , . . . , v i }, the constraint (3) can be written as L E (e) ∈ L V (v), where v ∈ {v 1 , . . . , v i }. The result is true for i = 1. We prove that we can assign labels to node v i+1 and to some of its adjacent edges such that the properties are satisfied for the set of nodes {v 1 , . . . , v i+1 } and the set of edges that have at least one incident node in {v 1 , . . . , v i+1 }.

Let e 1 , e 2 , e 3 be the three adjacent edges of v i+1 . For every j ∈ {1, 2, 3}, let t j be such that: t j = L E (e j ) if L E (e j ) has been defined before, t j be the j-th smallest integer that does not belong to any node labels if L E (e j ) has not been defined before. We set L V (v i+1 ) = {t 1 , t 2 , t 3 }, and L E (e j ) = t j for every j ∈ {1, 2, 3}. By construction and by induction hypothesis, the properties are satisfied. Thus, we get the labeling properties for G.

From the proof of Lemma 17, we get Corollary 18.

RR n°8647 In the following, a labeled cubic graph is a cubic graph G = (V, E) and labeling functions L V and L E that satisfy the properties of Lemma 17. Figure 7 describes a labeled cubic graph.

We now define the notion of 3-intersection graph of a hypergraph of maximum degree three (Definition 6) and we then prove in Lemma 19 that any cubic graph is the 3-intersection graph of a hypergraph of maximum degree three. Definition 6 (3-intersection graph) Let H = (V, E) be a hypergraph of maximum degree three. The 3-intersection graph G = (V, E) of H is defined as follows:

1. for every set of hyperedges {e 1 , e 2 , e 3 } ⊆ E such that e i = e j for 1 ≤ i < j ≤ 3 and such that e 1 ∩ e 2 ∩ e 3 = ∅, then there is a node u ∈ V that corresponds to {e 1 , e 2 , e 3 }, 2. for every node u ∈ V that corresponds to the set of hyperedges {e 1 , e 2 , e 3 } ⊆ E and for every node u ∈ V that corresponds to the set of hyperedges {e 1 , e 2 , e 3 } ⊆ E, then there is an edge {u, u } ∈ E if and only if |{e 1 , e 2 , e 3 } ∩ {e 1 , e 2 , e 3 }| ≥ 1.

Lemma 19 Every labeled cubic graph G = (V, E) is the 3-intersection graph of a hypergraph H = (V, E).

Proof Let G = (V, E) be any labeled cubic graph. We construct a hypergraph H = (V, E) as follows. For every node u ∈ V with L V (u) = {i, j, k}, i, j, k ≥ 1, there are three corresponding hyperedges e i , e j , e k ∈ E that share at least one node v ∈ V, that is v ∈ e i ∩ e j ∩ e k . Furthermore, for every i, j, k ≥ 1, if there is no node u ∈ V such that L V (u) = {i, j, k}, then there is no node v ∈ V that belongs to e i ∩ e j ∩ e k . From the properties of the labeling of G, then there is an edge {u, u } ∈ E if and only if there is a hyperedge e ∈ E that corresponds to both node u and node u . Then, for every hyperedge e ∈ E, we add at least one vertex that only belongs to e. Finally, G satisfies the properties of Definition 6, and so G is the 3-intersection graph of H.

Figure 7 describes a labeled cubic graph that is a 3-intersection graph of the hypergraph H = (V, E) composed of |E| = 27 hyperedges. Let E = {e 1 , . . . , e 27 }. Every integer i ∈ 1, 27 represents e i . Every set of three integers {i, j, k} that is represented in a node of the graph, 1 ≤ i < j < k ≤ 27, represents the intersection of the three hyperedges e i , e j , e k . There is a unique node v ∈ e i ∩ e j ∩ e k . Furthermore, for every hyperedge e ∈ E, there is at least one node that belongs only to e.

We are now able to prove Theorem 20.

Theorem 20 The global and local tree representation problems are APX-complete even if the maximum degree of the hypergraph is three. By assumption, there is a unique node v ∈ V that corresponds to u i , for every i, 1 ≤ i ≤ n, that is only v belongs to e j ∩ e k ∩ e l , where L V (u i ) = {e j , e k , e l }. For every i, 1 ≤ i ≤ n, such a node is denoted h(u i ). Without loss of generality, let {u 1 , . . . , u |S| } be the centers of the stars of S. Let σ = (h(u 1 ), . . . , h(u |S| ), . . . , h(u n ), v n+1 , . . . , v N ) be an ordering for the global tree representation T of H. By definition of a global tree representation and by construction of σ, there is a unique node in T that represents h(u i ) for every i, 1 ≤ i ≤ |S|. Note that h(u i ) belongs to three different hyperedges of H. Furthermore, there are two nodes in T that represent h(u j ) for every j, |S| + 1 ≤ j ≤ S∈S |V (S)|. Note that h(u j ) belongs to three different hyperedges of H. We obtain that max *

Proof Let G = (V,
global ≥ 2|S| + ( S∈S |V (S)| -|S|) = S∈S 1 + |V (S)| ≥ k. ⇒ Suppose that max * global ≥ k.
We prove that there exists an IISD S of G such that S∈S 1 + |V (S)| ≥ k. Without loss of generality, let σ = (v 1 , . . . , v N ) be an ordering for the global tree representation T of H such that max * global ≥ k. Recall that the set of nodes of H that belong to a unique hyperedge is {v n+1 , . . . , v N }. Let k ≥ 1. Every node v i , 1 ≤ i ≤ n, appears in exactly three different hyperedges. Thus, there are either one, two, or three nodes in T that represent v i , 1 ≤ i ≤ n. Let us define the function g as follows: g(v i ) = 2 if there is one node in T that represents v i , g(v i ) = 1 if there are two nodes in T that represent v i , and g(v i ) = 0 if there are three nodes in T that represent v i . By assumption, n i=1 g(v i ) ≥ k. Let u(v i ) be the node of G such that the three corresponding hyperedges of the labeling for u(v i ) contain node v i . We first prove that {u(v i ), g(v i ) ≥ 1, i = 1 . . . n} forms an IISD S of G. Without loss of generality, assume that g(v i ) ≥ g(v j ) for all i, j, 1 ≤ i < j ≤ n. We prove the result by induction. Let us assmume that {u(v i ), g(v i ) ≥ 1, i = 1 . . . t} forms an IISD of G for any t, 1 ≤ t ≤ n -1. It is clearly true for t = 1. We prove that it is also true for

t + 1, that is {u(v i ), g(v i ) ≥ 1, i = 1 . . . t + 1} forms an IISD of G. Consider the node u(v t+1 ). RR n°8647 • If g(v t+1 ) = 2, then d G (u(v t+1 ), u(v j )) ≥ 2 for all j, 1 ≤ j ≤ t. Indeed, otherwise, we would have g(v t+1 ) ≤ 1 if d G (u(v t+1 ), u(v j )) = 1 for some j, 1 ≤ j ≤ t.
Recall that in that case u(v t+1 ) and u(v j ) would have a common integer label and so a common hyperedge. Thus, {u(v i ), g(v i ) ≥ 1, i = 1 . . . t + 1} forms an IISD of G.

• If g(v t+1 ) = 1, then u(v t+1 ) has a unique neighbor u(v j ) such that g(v j ) ≥ 1 for some j, 1 ≤ j ≤ t. More precisely, g(v j ) = 2. Indeed, otherwise, we would have g(v t+1 ) = 2. Furthermore, every node u(v j ) / ∈ N G (u(v j )) such that g(v j ) ≥ 1 is such that d G (u(v t+1 ), u(v j )) ≥ 2. Indeed, otherwise, we would have g(v t+1 ) = 0 because g(v j ) = 2 and g(v j ) ≥ 1. In that case, the node v j would be represented three times in T : one time when representing the hyperedge that u(v t ) and u(v j ) share; one time when representing the hyperedge that u(v j ) and u(v j ) share; and one other time when representing the other (and different) hyperedge that contains u(v j ). Thus, {u(v i ), g(v i ) ≥ 1, i = 1 . . . t + 1} forms an IISD of G.

• If g(v t+1 ) = 0, then it is done, that is {u(v i ), g(v i ) ≥ 1, i = 1 . . . t + 1} forms an IISD of G.

We now prove that {u(v i ), g(v i ) ≥ 1, i = 1 . . . n} forms an IISD S of G such that S∈S 1+|V (S)| ≥ k. By the previous induction proof, we observe that there is a unique node u ∈ S such that g(u) = 2 for every S ∈ S. In other words, |{u, u ∈ S, g(u) = 2}| = 1 for every S ∈ S. If g(v i ) = 2, we set that u(v i ) is the center of its star for all i, 1 ≤ i ≤ n. Otherwise, u(v i ) is a leaf of a star (if g(v i ) = 1) or it is not in a star (if g(v i ) = 0). Thus, we get that S∈S 1 + |V (S)| ≥ k.

Constant factor approximations

In this section, we prove that the global and local tree representation problems admit a polynomial time k 2 -approximation algorithm for hypergraphs of maximum degree k, where k ≥ 3 is a constant integer. To do that, we transform the instances of global and local tree representation problems into instances of the weighted set packing problem. Let us first define the weighted set packing problem. Let U be any set of elements and let S be any set of weighted subsets of U . A subset C ⊆ S is a packing of S if and only if for all c, c ∈ C, c = c , then c ∩ c = ∅. The weighted set packing problem consists in computing the maximum k such that there exists a packing C of S with c∈C w c = k, where w c is the weight of c ∈ C. The decision variant of the weighted set packing problem is a well known NP-complete problem [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF][START_REF] Hochbaum | Efficient bounds for the stable set, vertex cover and set packing problems[END_REF]. We formalize in Definition 7 the auxiliary instance of the weighted set packing problem constructed from a hypergraph. The set U = E of the elements represents all the hyperedges. The set S represents all the different non-empty intersections of all the hyperedges of E. Note that w s ∈ N for all s ∈ S. Proof Let H = (V, E) be any hypergraph and let (U, S) be the instance of the weighted set packing problem constructed from H. Let k ≥ 1 be any integer. Recall that w s represents the weight of any subset s ∈ S. We prove that there exists a packing C of S such that c∈C w c ≥ k if and only if max * local ≥ k. Then, we will prove that max * local = max * global . ⇒ Suppose that there exists a packing C = {c 1 , . . . , c q } of S such that c∈C w c ≥ k, where q ≥ 1 is an integer such that, without loss of generality, for every e ∈ E, there exists an i, 1 ≤ i ≤ q, such that e ∈ c i . We prove that max * local ≥ k. By definition of C, we have c i ∩ c j = ∅ for all i, j, 1 ≤ i < j ≤ q. For all i, 1 ≤ i ≤ q, let t i = |c i | and c i = {e 1 i , . . . , e ti i }. Without loss of generality, assume that w e 1 i ,...,e j i = (j -1)|e 1 i ∩ . . . ∩ e j i | + (j -2)(w e 1 i ∩...∩e j-1 i -|e 1 i ∩ . . . ∩ e j i |) for all i, j, 1 ≤ i ≤ q, 1 ≤ j ≤ t i . For all i, j, 1 ≤ i ≤ q, 1 ≤ j ≤ t i , let Y j i = (e 1 i ∩ . . . ∩ e j i ) \ (e j+1 i ∪ . . . ∪ e ti i ). Let us construct T local = (V, E, L 1 , L 2 ) rooted at r ∈ V as follows. For all i = 1, . . . , q, for all j = t i , . . . , 1, we add |Y j i | nodes in T , namely u j,x i , where x = 1, . . . , |Y j i |. For all i = 1, . . . , q, for all j = t i , . . . , 1, for all x = 1, . . . , |Y j i |, for all x = x + 1, . . . , |Y j i |, we choose L 1 (u j,x i ) ∈ Y j i such that L 1 (u j,x i ) = L 1 (u j,x i

). For all i = 1, . . . , q, for all j = t i , . . . , 1, for all x = 1, . . . , |Y j i | -1, we add an edge {u j,x i , u j,x+1 i } ∈ E(T local ). For all i = 1, . . . , q, we add an edge {r, u ti,1 i } ∈ E(T local ). For all i = 1, . . . , q, for all j = t i , . . . , 2, we add an edge {u j,|Y j i | i , u j-1,1 i } ∈ E(T local ).

RR n°8647

Figure 1 :

 1 Figure 1: (a) Simplicial complex K composed of eight vertices {v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 , v 8 }. A vertex with i ∈ 1, 8 represents v i . The set of maximal simplices is composed of two tetrahedrons induced by {v 1 , v 3 , v 4 , v 6 } and {v 2 , v 4 , v 5 , v 8 }, and two triangles induced by {v 4 , v 6 , v 7 } and {v 4 , v 7 , v 8 }. (b) Hypergraph H= (V, E), where V = {v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 , v 8 } and E = {{v 1 , v 3 , v 4 , v 6 }, {v 2 , v 4 , v 5 , v 8 }, {v 4 , v 6 , v 7 }, {v 4 , v 7 , v 8 }}, that models K. A node with i ∈ 1, 8 represents v i . (c) Tree representation T of H. A node u with i ∈ 1, 8 is such that L 1 (u) = v i .

Figure 2 :

 2 Figure 2: Let H = (V, E), where V = {a 1 , . . . , a 4 , b 1 , . . . , b 4 , c 1 , . . . , c 8 } andE = {{a 1 , a 2 , a 3 , a 4 , b 1 , c 1 }, {a 1 , a 2 , a 3 , a 4 , b 2 , c 2 }, {a 1 , a 2 , a 3 , a 4 , b 3 , c 3 }, {a 1 , a 2 , a 3 , a 4 , b 4 , c 4 }, {b 1 , b 2 , b 3 , b 4 , a 1 , c 5 }, {b 1 , b 2 , b 3 , b 4 , a 2 , c 6 }, {b 1 , b 2 , b 3 , b 4 , a 3 , c 7 }, {b 1 , b 2 , b 3 , b 4 , a 4 , c 8 }, {a 1 , a 2 , a 3 , a 4 , b 1 , b 2 , b 3 , b 4 }}. A filled red node u with i ∈ 1, 4 is such that L 1 (u) = a i and L 2 (u) = i. A white node u with i ∈ 1, 4 is such that L 1 (u) = b i and L 2 (u) = i + 4. A blue node u with i ∈ 1, 8 is such that L 1 (u) = c i and L 2 (u) = i + 8. (A) Tree representation of H. (B) Local tree representation of H. Let u 1 be such that L 1 (u 1 ) = a 1 . The tree T [u 1 ] rooted at u 1 is a local tree representation of (V \ {a 1 }, E a1 ). Note that E a1 = {{a 2 , a 3 , a 4 , b 1 , c 1 }, {a 2 , a 3 , a 4 , b 2 , c 2 }, {a 2 , a 3 ,a 4 , b 3 , c 3 }, {a 2 , a 3 , a 4 , b 4 , c 4 }, {b 1 , b 2 , b 3 , b 4 , c 5 }}. The tree T \ T [u 1 ] rooted at r is a local tree representation of (V \ {a 1 }, Ēa1 ). Note that Ēa1 = {{b 1 , b 2 , b 3 , b 4 , a 2 , c 6 }, {b 1 , b 2 , b 3 , b 4 , a 3 , c 7 }, {b 1 , b 2 , b 3 , b 4 , a 4 , c 8 }}. All the hyperedges containing a 1 are represented in T [u 1 ] and all the other hyperedges are represented in T \ T [u 1 ]. (C) Global tree representation of H. A corresponding ordering is σ = (a 1 , . . . , a 4 , b 1 , . . . , b 4 , c 1 , . . . , c 8 ).

  Figure 2: Let H = (V, E), where V = {a 1 , . . . , a 4 , b 1 , . . . , b 4 , c 1 , . . . , c 8 } andE = {{a 1 , a 2 , a 3 , a 4 , b 1 , c 1 }, {a 1 , a 2 , a 3 , a 4 , b 2 , c 2 }, {a 1 , a 2 , a 3 , a 4 , b 3 , c 3 }, {a 1 , a 2 , a 3 , a 4 , b 4 , c 4 }, {b 1 , b 2 , b 3 , b 4 , a 1 , c 5 }, {b 1 , b 2 , b 3 , b 4 , a 2 , c 6 }, {b 1 , b 2 , b 3 , b 4 , a 3 , c 7 }, {b 1 , b 2 , b 3 , b 4 , a 4 , c 8 }, {a 1 , a 2 , a 3 , a 4 , b 1 , b 2 , b 3 , b 4 }}. A filled red node u with i ∈ 1, 4 is such that L 1 (u) = a i and L 2 (u) = i. A white node u with i ∈ 1, 4 is such that L 1 (u) = b i and L 2 (u) = i + 4. A blue node u with i ∈ 1, 8 is such that L 1 (u) = c i and L 2 (u) = i + 8. (A) Tree representation of H. (B) Local tree representation of H. Let u 1 be such that L 1 (u 1 ) = a 1 . The tree T [u 1 ] rooted at u 1 is a local tree representation of (V \ {a 1 }, E a1 ). Note that E a1 = {{a 2 , a 3 , a 4 , b 1 , c 1 }, {a 2 , a 3 , a 4 , b 2 , c 2 }, {a 2 , a 3 ,a 4 , b 3 , c 3 }, {a 2 , a 3 , a 4 , b 4 , c 4 }, {b 1 , b 2 , b 3 , b 4 , c 5 }}. The tree T \ T [u 1 ] rooted at r is a local tree representation of (V \ {a 1 }, Ēa1 ). Note that Ēa1 = {{b 1 , b 2 , b 3 , b 4 , a 2 , c 6 }, {b 1 , b 2 , b 3 , b 4 , a 3 , c 7 }, {b 1 , b 2 , b 3 , b 4 , a 4 , c 8 }}. All the hyperedges containing a 1 are represented in T [u 1 ] and all the other hyperedges are represented in T \ T [u 1 ]. (C) Global tree representation of H. A corresponding ordering is σ = (a 1 , . . . , a 4 , b 1 , . . . , b 4 , c 1 , . . . , c 8 ).

Problem 1 (

 1 tree representation problem) Let H = (V, E) be any hypergraph. The tree representation problem consists in computing the maximum max * such that there exists a tree representation T * of H with |V (T * )| = -max * + 1 + e∈E |e|. The term e∈E |e| represents the size of E, and so the size of H, without optimization. The term 1 is added for the root of the tree. Problem 2 (local tree representation problem) Let H = (V, E) be any hypergraph. The local tree representation problem consists in computing the maximum max * local such that there exists a local tree representation T * local of H with |V (T * local )| = -max * local + 1 + e∈E |e|.

Problem 3 (

 3 global tree representation problem) Let H = (V, E) be any hypergraph. The global tree representation problem consists in computing the maximum max * global such that there exists a global tree representation T * global of H with |V (T * global )| = -max * global + 1 + e∈E |e|. From Lemma 3, we deduce Corollary 7. Corollary 7 (equivalence for the global tree representation problem) Let H = (V, E) be any hypergraph. Then, max * global = -min σ∈Σ(V) |V (T σ )| + 1 + e∈E |e|, that is |V (T * global )| = min σ∈Σ(V) |V (T σ )|. As an illustration, we have max * = 29 and |V (T * )| = 28 (Figure 2(A)), max * local = 26 and |V (T * local )| = f (V, E) + 1 = 31 (Figure 2(B)), and max * global = 18 and |V (T * global )| = 39 (Figure 2(C)). Intuitively, max * (max * local , max * global , respectively) represents the maximum number of nodes that can be factorized for the (local, global, respectively) tree representation problem.

Property 1

 1 Let H be any hypergraph. Then, |V (T * global )| ≥ |V (T * local )| ≥ |V (T * )| and max * global ≤ max * local ≤ max * . We now prove in Lemma 8 that there exists an infinite class of hypergraphs C such that for every hypergraph H = (V, E) ∈ C, then |V (T * local )| = O(|V|) and |V (T * global )| = Ω(|V| 2 ). Lemma 8 For any n ≥ 1, there exists a hypergraph H = (V, E), with n = |V|/4, such that |V (T * local )| ≤ 8n and |V (T * global )| ≥ n 2 . Proof The proof is based on the generalization of the hypergraph described in Let n ≥ 1 be any integer. Let A = {a 1 , . . . , a n } and B = {b 1 , . . . , b n }. We now define the hypergraph H = (V, E). Let V = A ∪ B be the set of nodes. Let E = {{a 1 , . . . , a n , b} | b ∈ B} ∪ {{b 1 , . . . , b n , a} | a ∈ A} be the set of 2n hyperedges. We prove that |V (T * local )| ≤ 5n and |V (T * global )| ≥ n 2

  For any two subsets of nodes A = {a 1 , . . . , a |A | } ⊆ A and B = {b 1 , . . . , b |B | } ⊆ B, consider the hypergraph (V A ,B , E A ,B ), where V A ,B = A ∪ B and E A ,B = {{a 1 , . . . , a |A | , b} | b ∈ B } ∪ {{b 1 , . . . , b |B | , a} | a ∈ A }. We prove by induction that a global tree representation T A ,B of (V A ,B , E A ,B ) is such that |V (T A ,B )| ≥ |A ||B | for all A ⊆ A, B ⊆ B, and so we prove that |V (T global )| ≥ |A||B| = n 2 . It is true for |A | = |B | = 1 because |V (T A ,B )| = 3. Suppose it is true for all A and B such that |A | ≤ n -1 and |B | ≤ n -1.

Figure 2 (

 2 b) depicts T A1,B1 for α 1 = 4 and β 1 = 4.

Lemma 9

 9 Let G be any graph. Then, |V (T * global )| = |V (T * local )| = |V (T * )| and max * global = max * local = max * . Proof Let G = (V, E) be any graph. The number of leaves of T * global , T * local , and T * is the number of edges |E| of G. The height of T * global , T * local , and T * is 2 because |e| = 2 for every e ∈ E. Let T = (V, E, L 1 ) be any tree representation rooted at r ∈ V of G. We prove that there exist a global tree representation T global of G and a local tree representation T local of G such that |V (T global )| = |V (T local )| ≤ |V (T )|.

  By construction, the tree T global is a global tree representation of G and is such that |V | = |V |. From Lemma 3, a global tree representation is a local tree representation. Thus, T local = T global is a local tree representation such that |V (T local )| ≤ |V (T )|. Finally, from Property 1, we have |V (T * global )| ≥ |V (T * local )| ≥ |V (T * )|. Thus, we get that |V (T * global )| = |V (T * local )| = |V (T * )|.

  (a).

Figure 3 (

 3 b) depicts an optimal global tree representation T * global of G with |V (T * global )| = 1 + |X| + |E| = 15, and so x * global = 8

Figure 4 :

 4 Figure 4: (a) Planar graph G = (V, E) of maximum degree three, with V= {v 1 , v 2 , v 3 , v 4 , v 5 } and E = {{v 1 , v 2 }, {v 1 , v 3 }, {v 2 , v 3 }, {v 2 , v 4 }, {v 3 , v 5 }, {v 4 , v 5 }}. A node with the integer i ∈ 1, 6 represents v i ∈ V. Note that |N G (v 2 ) ∩ N G (v 4 )| = 2.The set of red nodes represents a minimum vertex cover X = {v 1 , v 3 , v 4 } of G of size |X| = 3. (b) Planar graph G = (V , E ) constructed from G in the proof of Lemma 10. The maximum degree of G is three and |N G (v) ∩ N G (v )| ≤ 1 for all v, v ∈ V , v = v . Every edge of G is replaced by a path composed of four nodes. The set of red nodes represents a minimum vertex cover X of G of size |X | = |X| + |E| = 9.

Figure 5 :

 5 Figure 5: (a) Hypergraph H = (V, E) such that |E[v]| ≤ 2 for all v ∈ V. Let E = {e 1 , e 2 , e 3 , e 4 , e 5 , e 6 }. An edge with j ∈ 1, 6 represents e j ∈ E. The set of filled nodes represents the maximal cardinality subset of nodes of V that can be factorized in the tree representation. (b) Intersection edge-weighted graph G = (E, I, w) constructed from H. A node with j ∈ 1, 6 represents e j ∈ E. For every i ∈ I, the weight w i is represented by the integer j ∈ N. (c) Node-weighted line graph L = (I, E , w ) of G. For every i ∈ I, the weight w i is represented by the integer j ∈ N. The set of filled red nodes represents a maximum weighted independent set of L of total weight 9. From Theorem 13, max * local = max * global = 9.

Definition 4 (Definition 5 (

 45 Induced induced-star decomposition) Given a graph G = (V, E), an induced induced-star decomposition (IISD) of G is a set S of induced stars such that d G (S, S ) ≥ 2 for every S, S ∈ S, S = S . Induced induced-star decomposition problem) Given a graph G = (V, E), the induced induced-star decomposition problem (IISD problem) consists in computing an IISD S of G such that S∈S 1 + |V (S)| ≥ k. Note that S∈S 1 + |V (S)| = S∈S 2 + |E(S)|. Observe also that if |V (S)| = 1 for all S ∈ S, then S is an independent set of G, and if |V (S)| = 2 for all S ∈ S, then S is an induced

Figure 6 :

 6 Figure 6: (a) Cubic graph G = (V, E). (b) Maximum independent set X of G such that 2|X| = 14. (c) Maximum induced matching F of G such that 3|F | = 15. (d) Optimal solution S * for the IISD problem for G such that S∈S * 1 + |V (S)| = 16.

Figure 7 :

 7 Figure 7: Labeled cubic graph and 3-intersection graph of the hypergraph H = (V, E) composed of |E| = 27 hyperedges, E = {e 1 , . . . , e 27 }. Every integer i ∈ 1, 27 represents e i . Every set of three integers {i, j, k} that is represented in a node of the graph, 1 ≤ i < j < k ≤ 27, represents the intersection of the three hyperedges e i , e j , e k . There is a unique node v ∈ e i ∩ e j ∩ e k , and for every hyperedge e ∈ E, there is at least one node that belongs only to e.

Definition 7 (

 7 instance of weighted set packing problem from a hypergraph) Let H = (V, E) be a hypergraph with E = {e 1 , . . . , e m }. The instance (U, S) of the weighted set packing problem from H is defined as follows. Set U = E. Let e s1 , . . . , e st ∈ E be any t hyperedges, with 2 ≤ t ≤ m. The subset {e s1 , . . . , e st } ∈ S if and only if e s1 ∩ . . . ∩ e st = ∅. Furthermore, w s = |e s1 ∩e s2 | if t = 2 and w s = (t-1)|e s1 ∩. . .∩e st |+(t-2)(max e∈s (w {es 1 ,...,es t }\{e} )-|e s1 ∩. . .∩e st |) if t ≥ 3.

Figure 8 Figure 8 :

 88 Figure 8: Hypergraph H = (V, E) with E = {e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e 7 }. A hyperedge with i ∈ 1, 7 represents e i ∈ E. The auxiliary instance (U, S) of the weighted set packing problem from H is such that U = {e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e 7 } and S = {{e 1 , e 2 }, {e 1 , e 6 }, {e 1 , e 7 }, {e 2 , e 3 }, {e 2 , e 4 }, {e 2 , e 7 }, {e 3 , e 4 }, {e 3 , e 7 }, {e 4 , e 5 }, {e 4 , e 7 }, {e 5 , e 6 }, {e 5 , e 7 }, {e 6 , e 7 }, {e 1 , e 2 , e 7 }, {e 1 , e 6 , e 7 }, {e 2 , e 3 , e 7 }, {e 2 , e 3 , e 4 }, {e 3 , e 4 , e 7 }, {e 2 , e 4 , e 7 }, {e 4 , e 5 , e 7 }, {e 5 , e 6 , e 7 }, {e 2 , e 3 , e 4 , e 7 }}. Furthermore, w {e1,e2} = 6, w {e1,e6} = 2, w {e1,e7} = 4, w {e2,e3} = 6, w {e2,e4} = 3, w {e2,e7} = 6, w {e3,e4} = 7, w {e3,e7} = 1, w {e4,e5} = 4, w {e4,e7} = 4, w {e5,e6} = 2, w {e5,e7} = 4, w {e6,e7} = 6, w {e1,e2,e7} = 9, w {e1,e6,e7} = 7, w {e2,e3,e7} = 7, w {e2,e3,e4} = 10, w {e3,e4,e7} = 8, w {e2,e4,e7} = 7, w {e4,e5,e7} = 5, w {e5,e6,e7} = 8, and w {e2,e3,e4,e7} = 11. For instance, {e 2 , e 3 , e 4 } ∈ S and w {e2,e3,e4} = 10 because |e 2 ∩ e 3 ∩ e 4 | = 3 and max(w {e2,e3} , w {e2,e4} , w {e3,e4} ) -3 = 4. The packing C * = {{e 1 , e 2 }, {e 3 , e 4 }, {e 5 , e 6 , e 7 }} is such that c∈C * w c = 21 and is optimal for the weighted set packing problem for (U, S). From Theorem 21, we get that max * local = max * global = 21.

  We then show that max * local = max * global . ⇐ Suppose there exists an IISD S of G such that S∈S 1 + |V (S)| ≥ k. We prove that max

E) be any labeled cubic graph. Let n = |V | and V = {u 1 , . . . , u n }. From Lemma 19, there is a hypergraph

H = (V, E) such that G is the 3-intersection graph of H. Let N = |V| and let V = {v 1 , . . . , v N }. Let E = {e 1 , e 2 , . . .}. A label i of G corresponds to hyperedge e i ∈ E.

We assume that for all e 1 , e 2 , e 3 ∈ E, if e 1 ∩ e 2 ∩ e 3 = ∅, then |e 1 ∩ e 2 ∩ e 3 | = 1. We assume that the set of nodes of H that belong to a unique hyperedge is {v n+1 , . . . , v N }. Let k ≥ 1. We prove that max * global ≥ k for H if and only if there exists an IISD S of G such that S∈S 1 + |V (S)| ≥ k. * global ≥ k.

RR n°8647

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

* This research has been partially supported by the European Research Council under Advanced Grant 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions).

† Inria Sophia Antipolis -Méditerranée, France

Let Y = ∪ q i=1 ∪ ti j=1 Y j i . For all i = 1, . . . , q, for all j = t i , . . . , 1, let {u j,1 i , . . . , u j,ti i } = (V ∩ e j i ) \ Y . For all i = 1, . . . , q, for all j = t i , . . . , 1, let P i,j be the longest path in T between r and u i,j such that for all u ∈ V (P i,j ), then L 1 (u) ∈ e j i . For all i = 1, . . . , q, for all j = t i , . . . , 1, we add in T the path (u i,j , u j,1 i , . . . , u j,ti i ); we obtain the path P i,j between r and u j,ti i . We define L 1 (u) ∈ e j i such that L 1 (u) = L 1 (u ) for all u, u ∈ V (P i,j ) \ {r}, u = u . We now easily define L 2 such that every simple path P e = (r, u 1 , . . . , u |e| ) representing the hyperedge e ∈ E is such that L 2 (u i ) < L 2 (u j ) for all i, j, 1 ≤ i < j ≤ |e|.

The tree T local satisfies the properties of Definition 2, and the number of nodes of

We prove that there exists a packing C = {c 1 , . . . , c q } of S such that c∈C w c ≥ k, where q ≥ 1 is an integer. We prove the result by induction on the number of hyperedges. It is true when the hypergraph contains one or two hyperedges. Suppose it is true when there are at most |E| -1 hyperedges. We prove that it is also true with |E| hyperedges.

Let N T local (r) = {u 1 , . . . , u q }, where q is the degree of the root r. We construct the packing C = {c 1 , . . . , c q } of S as follows. For all i, 1 ≤ i ≤ q, let c i = {e 1 i , . . . , e ti i } such that L 1 (u i ) ∈ e j i and L 1 (u i ) / ∈ e for all j, 1 ≤ j ≤ t i and for all e ∈ E \ c i . Since T local satisfies the properties of Definition 2, then c i ∩ c j = ∅ for all i, j, 1 ≤ i < j ≤ q. Consider the q subproblems induced by the neigbhors of r, that is the q subtrees T 1 local , . . . , T q local rooted at u 1 , . . . , u q , respectively. By induction hypothesis and by the previous remark, there exists a packing C i such that c∈Ci w c ≥ x i local for all i, 1 ≤ i ≤ q. Thus, the packing C is such that c∈C w c ≥ k = q i=1 x i local . The trees previously described satisfy the properties of Definition 2 and the properties of Definition 3. Thus, max * local = max * global . Finally, the k 2 -approximation algorithm for the weighted set packing problem proved in [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF], gives a k 2 -approximation algorithm for our problems.

Future works

As future works, we plan to implement the algorithms described in this article and to design new ones (e.g. branch and bound algorithm that guarantees any approximation ratio). We are also studying the problem of representing maximal simplices by directed (acyclic) graphs. We think that these new representations may reduce significantly the size of the representation of simplicial complexes.