Nabil Adrar

Philippe Jégou

Cyril Terrioux

Computing Partial Hypergraphs of Bounded Width *

Keywords:

In this paper, we are interested in the computation of partial hypergraphs whose width is bounded by an integer k. Given a hypergraph H = (V, E) the task is to find a "partial" hypergraph H ′ = (V, E ′ ) (with E ′ ⊆ E) for which the width of its 2-section is at most k -1. Several criteria can be considered for the optimality of the result. The first one is related to the maximum number of hyperedges to include in H ′ (maximum criteria). Another one is based on the fact that for all E ′′ ⊆ E with E ′ ⊊ E ′′ , the width is then strictly greater than k -1 (maximal criteria). Unfortunately, each one of these tasks is NP-hard.

So, as this task can be useful in practice for the processing of graphical models (e.g. constraint networks, cost function networks, Bayesian networks, Markov random fields, . . . ), we propose a polynomial-time algorithm that finds such partial hypergraphs but with no guarantee with respect to optimality. Nevertheless, we show that for an important class of hypergraphs, it can be optimal. Finally, we present experiments performed on a large benchmark containing more than 11,000 instances from different communities. These experiments allow us to evaluate the efficiency of this algorithm from two points of view: first the proximity of the optimality of the result, then its time efficiency in practice.

Introduction

It is well known that many problems can be represented by graphs, or even beyond, by hypergraphs. To mention only a few domains, it can be for example constraint networks, in the sense of CSP (Constraint Satisfaction Problem), with valuation [START_REF] Schiex | Valued Constraint Satisfaction Problems: hard and easy problems[END_REF] or not [START_REF] Montanari | Networks of Constraints: Fundamental Properties and Applications to Picture Processing[END_REF][START_REF] Dechter | Constraint processing[END_REF], and more generally, graphical models in the sense of cost function networks, Bayesian networks, or Markov Random Fields [START_REF] Koller | Probabilistic Graphical Models: Principles and Techniques[END_REF][START_REF] Dechter | Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms[END_REF]. On another level, one can also evoke the conjunctive queries in relational databases [START_REF] Beeri | On the desirability of acyclic database schemes[END_REF]. In addition to the interest of representing these problems by their structure, this approach makes it possible to use at the same time many works stemming from the (algorithmic) graph theory, both in terms of properties that can be exploited and results in terms of complexity bounds, or even the whole set of algorithms available for the manipulation of these graphs or hypergraphs. And at the level of the most exploited theoretical results to help in the treatment of these graphical models, there is the work around the exploitation of structural properties. Among the different notions developed in this framework, we find mainly the notion of tree-decomposition [START_REF] Robertson | Graph minors II: Algorithmic aspects of treewidth[END_REF] as well as its numerous variants and extensions which have been proposed in the literature for years while constituting today an extremely active field of work [START_REF] Bui-Xuan | Rank-width and vertex-minors[END_REF][START_REF] Jeong | Maximum matching width: new characterizations and a fast algorithm for dominating set[END_REF][START_REF] Gajarsky | Parameterized Algorithms for Modular-Width[END_REF][START_REF] Wollan | The structure of graphs not admitting a fixed immersion[END_REF][START_REF] Nesetril | Bounded height trees and tree-depth[END_REF]. In this field, tree-decomposition has been exploited both theoretically to provide complexity bounds as well as to define tractable classes using the notion of bounded width [START_REF] Courcelle | The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs[END_REF][START_REF] Gottlob | A Comparison of Structural CSP Decomposition Methods[END_REF]. On a practical level, this notion allows offering to process and solving methods that are often very efficient (see [START_REF] Jégou | Hybrid backtracking bounded by tree-decomposition of constraint networks[END_REF]), as long as the structure of the processed instances has good properties such as a small width (see [START_REF] De Givry | Exploiting Tree Decomposition and Soft Local Consistency in Weighted CSP[END_REF]). On another level, it has been known for a long time that conjunctive queries in relational databases can be processed in polynomial time when the structure of the concerned relations is defined by an α-acyclic hypergraph [START_REF] Beeri | On the desirability of acyclic database schemes[END_REF]. In fact, the link between acyclicity and tree-decomposition is very strong since the notion of treewidth is intended in particular as a kind of measure of the cyclicity of a graph, and beyond, of a hypergraph. But the link is even stronger formally. Indeed, it is well known that if we consider a tree-decomposition, then the hypergraph defined by the set of vertices and taking as hyperedges the bags of the decomposition is an α-acyclic hypergraph.

However, while tree-decomposition provides a very useful tool on the theoretical level, there are often difficulties on the practical level. On the one hand, the calculation of an optimal tree-decomposition, i.e. whose width is equal to the treewidth, is an NP-hard problem [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF] if this treewidth is not bounded by a constant. On the other hand, depending on the instances, as soon as the treewidth is too large, it becomes difficult to exploit the solving methods based on the exploitation of the structure by this kind of approach.

Therefore, alternative approaches have been proposed to get around this type of difficulty. About the treatment of acyclic hypergraphs, Hirata et al. were interested in such a question [START_REF] Hirata | On Finding Acyclic Subhypergraphs[END_REF]. They studied several questions including the problem called "Spanning connected Acyclic Subhypergraph" which consists, given a hypergraph H, in determining if there exists a partial α-acyclic hypergraph that is connected and covering all the vertices of H. They show that this problem is NP-complete. They also studied the so-called "Maximum Acyclic Subhypergraph Problem", itself NP-complete. In this problem, given a hypergraph H and an integer k, the question is whether there exists a partial sub-hypergraph (subsets of vertices and hyperedges) of k hyperedges that is α-acyclic. Because of these two negative results, they became interested in the problem which consists, given a hypergraph H, in calculating a maximum α-acyclic partial subhypergraph in the sense of the set of hyperedges. They propose for this purpose a linear time algorithm based on the algorithm of Tarjan and Yannakakis [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF] that deals with the question of the recognition of α-acyclic hypergraphs and chordal graphs.

Within the framework of CSPs, Jégou and Terrioux have been interested in the search sub-networks of binary CSPs of limited width in order to propose new filtering techniques based on the internal structural properties of the constraint networks [START_REF] Jégou | A new filtering based on decomposition of constraint sub-networks[END_REF]. This approach was essentially guided by the study and exploitation of substructures in terms of filtering on the basis of a problem that is relaxed because it contains only a subset of the constraints of the problem to be solved. Such an approach gave interesting experimental results for this task. To this end, they dealt with the question of the calculation of sub-networks by introducing the notion of w-P ST which corresponds to "partial spanning tree-decompositions" of width w. This question not being central in their work, the calculation was limited to a heuristic constructing from the input graph, a partial graph constituted by a partial k-tree [START_REF] Beineke | Properties and characterizations of k-trees[END_REF].

It is in the Markov random fields framework that the issue seems to have been most studied. But in a way, as with the work on CSPs, the value of the work carried out is to be assessed in terms of its contribution to the field of application, i.e. the practical efficiency of the treatments of Markov random fields. Karger and Srebro [START_REF] Karger | Learning Markov networks: maximum bounded tree-width graphs[END_REF] are interested in the problem called "Maximal Hypertree problem" which, given an integer k, a set of vertices V , and a weight function with real values on hyperedges of size at most k + 1, seeks to find a hypertree H of treewidth at most k which minimizes the sum of the weights of the hyperedges of H. In fact, hypertree is to be understood as tree-decomposition. They show (the proofs are to be found in [START_REF] Srebro | Maximum likelihood Markov networks: An algorithmic approach[END_REF]) that the (associated decision) problem restricted to graphs is NP-complete. Moreover, the associated optimization problem belongs to the class max-SNP-hard. They also specify that even with unit weights, this problem remains NP-hard. Beyond this theoretical study, their main contribution consists in giving the first approximation algorithms for the problem, achieving a polynomial-time constant-factor approximation for any fixed treewidth objective.

More recently, still in the context of Markov random fields, several works have taken an interest in this question, such as [START_REF] Shahaf | Learning Thin Junction Trees via Graph Cuts[END_REF] or [START_REF] Fix | Approximate MRF Inference Using Bounded Treewidth Subgraphs[END_REF]. In [START_REF] Fix | Approximate MRF Inference Using Bounded Treewidth Subgraphs[END_REF], Fix et al. study the problem called "Maximum Bounded-Treewidth Subgraph problem" which, given a graph with weights on the edges, consists in finding a subgraph of treewidth at most k and of maximum weight. To solve it, they propose a greedy algorithm to find a subgraph of treewidth k and large weight. In addition to the quality of their algorithm, they show its interest in terms of its practical use, and this was its main objective. To do this, their algorithm exactly solves the inference problem in the subgraph using dynamic programming. Then, using a proof of lower bound, the authors argue that the solution for the subgraph is a good approximation to the optimum for the original energy.

This type of work has also been developed in the management of Bayesian networks. In [START_REF] Nie | Learning Bayesian Networks with Bounded Tree-width via Guided Search[END_REF], Nie et al. propose an algorithm to find k-trees with maximum informative scores, which is a measure of quality for the k-tree in yielding good Bayesian networks. The algorithm achieves close to optimal performance compared to exact solutions in small domains and can discover better networks than existing approximate methods can in large domains. It also provides an optimal elimination order of variables that guarantees small complexity for later runs of exact inference.

In this paper, we are interested in the question specifically expressed in terms of hypergraphs. Indeed, if the literature has a very large number of graph processing algorithms, it seems necessary to enrich this corpus with algorithms that directly process hypergraphs. In this work, we seek to calculate a partial hypergraph whose width, in the sense of treedecomposition, is bounded by a constant k. It turns out that this problem is NP-hard if one is interested in the maximum number of hyperedges to be selected. But it also turns out to be NP-hard if we limit ourselves to a maximal set in the sense of inclusion. So, we propose a polynomial-time algorithm called k-P H (for Partial Hypergraph of width k -1) which looks neither for optimality in terms of the number of hyperedges, nor for maximality in set terms (i.e. for inclusion). However, its interest is already justified on a theoretical level. Indeed, we show that for the case where the input hypergraph is α-acyclic, and if the value of the parameter k is equal to the size of the largest hyperedge, then the algorithm calculates the optimal result. But the interest of this algorithm is also shown experimentally.

To this end, we conducted experiments on a large benchmark containing 11,302 instances from different communities and whose treewidth is known, and we consider the proportion of hyperedges included in the calculated partial hypergraph. For example, these experiments show that for about 90% of the instances, more than 70% of the hyperedges are retained in the calculated partial hypergraph, and more than 80% of the hyperedges are retained in 75% of the instances. These experiments also make it possible to verify that calculation times remain limited because they are on average well below one second on a basic computer. Finally, this algorithm can easily be adapted according to the considered objective. Indeed, one can thus add to it different heuristics which make it possible, for example, to take into account weights for hyperedge to be selected in the partial hypergraph. This should make it easier to process different types of graphical models.

In the following section, we introduce the notations and we formally specify the different problems associated with this type of question. Section 3 presents the scheme of the k-P H algorithm and after having provided proof of its validity, we show its optimality for the case of α-acyclic hypergraphs. We give an evaluation of the time complexity of this algorithm but its analysis needs to presents the details of the implementation. So, these details are given in Appendix A. The penultimate section provides an experimental study to assess the quality of the results as well as the runtimes. Finally, we conclude and give some perspectives in Section 5.

Preliminaries

A hypergraph H = (V, E) is defined by a set V of vertices and a set E ⊆ 2 V of hyperedges. The size of V is denoted n while the size of E is e. For v ∈ V , d(v) is the degree of v, that is the number of hyperedges containing v while r is the rank of the hypergraph (i.e. the maximum number of vertices per hyperedge).

Definition 1 (subhypergraph) Given a hypergraph H = (V, E) and V ′ ⊆ V , the subhypergraph of H induced by V ′ is the hypergraph H[V ′ ] = (V ′ , E ′ ), where E ′ = {E i ∈ E | E i ⊆ V ′ }.
Note that all hyperedges appearing in H[V ′ ] must be included in V ′ . It is not the case for what we call expanded subhypergraph:

Definition 2 (expanded subhypergraph) Given a hypergraph H = (V, E) and V ′ ⊆ V , the expanded subhypergraph of H induced by V ′ is the hypergraph H[[V ′ ]] = (V ′ , E ′ ), where E ′ = {E i ⊆ V ′ | ∃E j ∈ E, E j ∩ V ′ ̸ = ∅, E i = E j ∩ V ′ and E i is maximal}.
In this definition, maximal means that there is no E i ′ satisfying the same conditions as E i such that E i ⊊ E i ′ . So, by verifying this condition, in an expanded subhypergraph, if a hyperedge does not appear in H[V ′ ] but has a non-empty intersection with V ′ , H[[V ′ ]] contains as hyperedge this maximal intersection.

Definition 3 (partial hypergraph) Given a hypergraph H = (V, E) and E ′ ⊆ E, the partial hypergraph of H induced by E ′ is the hypergraph H[E ′ ] = (V, E ′ ).
To define the width of a hypergraph, we recall the definition of the 2-section [START_REF] Berge | Graphs and hypergraphs[END_REF] of a hypergraph (note that this graph is sometimes called the primal graph [START_REF] Dechter | Constraint processing[END_REF]): Definition 4 (2-section of hypergraph) Given a hypergraph H = (V, E), the 2-section of H is the graph 2 SEC (H ) = (V , E ′ ) where an edge {x, y} ∈ E ′ if and only if there is a hyperedge

E i ∈ E such that {x, y} ⊆ E i .
Given a hypergraph H = (V, E), a path of length ℓ in H between two vertices x and y is a sequence of vertices

(x = v 0 , v 1 , . . . , v ℓ = y) such that ∀i, 1 ≤ i ≤ ℓ, ∃E i ∈ E such that {v i-1 , v i } ⊆ E i .
We can see that there is a path in H if and only if there is a path in 2 SEC (H ). In the sequel, we call connected component of a hypergraph H = (V, E) a subset of vertices1 of V which is a connected component in 2 SEC (H ). In other words, two vertices of H appear in the same connected component if there is a path between them in H, as for graphs. So, if

V ′ ⊆ V is a connected component of the hypergraph H = (V, E), for all hyperedge E i ∈ E, either E i ⊆ V ′ , or E i ∩ V ′ = ∅.
To define the tree-decomposition and the treewidth of a hypergraph, we need to use the corresponding definitions for graphs [START_REF] Robertson | Graph minors II: Algorithmic aspects of treewidth[END_REF]: Definition 5 (tree-decomposition and treewidth of hypergraph) A tree-decomposition of a graph G = (V, E) is a pair (B, T ) where T = (I, F ) is a tree (I is a set of nodes and F a set of edges) and B = {B i : i ∈ I} a family of subsets of V such that every B i ∈ B (called bag) corresponds to a node i of T and satisfies:

(i) ∪ i∈I B i = V , (ii) ∀{x, y} ∈ E, ∃i ∈ I such that {x, y} ⊆ B i , and (iii) ∀i, j, k ∈ I, if k is on a path between i and j in T , then B i ∩ B j ⊆ B k
The width of a tree-decomposition is equal to max i∈I |B i | -1. The treewidth of G denoted w is equal to the minimum width among all the tree-decompositions of G. So, given a hypergraph H = (V, E) and its 2-section 2 SEC (H ), a treedecomposition of H is a tree-decomposition of 2 SEC (H ), and the treewidth of H is the treewidth of 2 SEC (H ).

In this paper, we study the issue of calculating a partial hypergraph that includes as many hyperedges as possible while guaranteeing a bounded width. Also, we are interested in the question of a maximum (size) set of hyperedges or, at least, maximal (for inclusion). This problem is based on the following definitions.

Definition 6 (k partial hypergraph) Given a hypergraph H = (V, E) and an integer k, a k partial hypergraph of H is a hypergraph H ′ = (V, E ′ ) with E ′ ⊆ E, such that 2 SEC (H ′ ) has a treewidth at most k -1. A k partial hypergraph H ′ of H is maximal if there is no E ′′ such that E ′ ⊊ E ′′ ⊆ E and such that the treewidth of H ′′ = (V, E ′′ ) is at most equal to k -1.
It is maximum if it is a partial hypergraph of treewidth at most k -1 with as many hyperedges as possible.

Note that for a hypergraph H and an integer k, it is possible that no partial hypergraph H ′ exists which has a width exactly equal to k -1. Indeed, if a hypergraph contains two edges, one of size k -2 and the other of size k + 1, it does not have any partial hypergraph whose treewidth is equal to k -1. Before considering the associated optimization problems, we define a first decision problem: In fact, this problem has already been studied in the case of Markov random fields under consideration of weighted hyperedges and as an optimization problem called MAXIMAL HYPERTREE [START_REF] Karger | Learning Markov networks: maximum bounded tree-width graphs[END_REF][START_REF] Srebro | Maximum likelihood Markov networks: An algorithmic approach[END_REF]: MAXIMAL HYPERTREE INSTANCE: A weighted hypergraph H = (V, E, w) with w : E → R and an integer k ≤ |V |. QUESTION: Find a partial hypergraph of H for which the sum of the weights of its hyperedges is maximum and whose treewidth is at most k -1.

MAXIMUM PARTIAL HYPERGRAPH OF BOUNDED WIDTH INSTANCE: A hypergraph H = (V, E),
In [START_REF] Karger | Learning Markov networks: maximum bounded tree-width graphs[END_REF], it is shown that this optimization problem is max-SNP-hard and that the associated decision problem restricted to graphs is NP-complete. The authors specify that even with unit weights, this problem is NP-hard. The details of the proofs are to be found in [START_REF] Srebro | Maximum likelihood Markov networks: An algorithmic approach[END_REF]. This being, in fact, we can deal with two questions here, depending on whether we are interested in the maximum in terms of weights (or number of hyperedges for unit weights), or in terms of the maximality of the set of the selected hyperedges. We present these two variants: It can be observed that the associated decision problem is trivial because, except for having only hyperedges of which size is strictly greater than k, the answer to the question of the existence of a partial hypergraph of treewidth at most k -1 is always yes. It is then necessary to reformulate the question by removing "maximal", and by replacing "of treewidth at most k -1" by "of treewidth k -1":

PARTIAL HYPERGRAPH OF GIVEN WIDTH INSTANCE: A hypergraph H = (V, E) and an integer k ≤ |V |. QUESTION: Does H have a partial hypergraph of treewidth k -1?
Unfortunately, this problem is as difficult as the problems associated with the tree-decomposition and treewidth in graphs. And we know that given a graph G and an integer k, it is NP-complete to determine whether the treewidth of G is at most k [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF]. So, to determine whether a graph G have a partial graph of treewidth k -1 is also NP-complete and thus, PARTIAL HYPERGRAPH OF GIVEN WIDTH is NP-complete. Another immediate consequence is that MAXIMAL PARTIAL HYPERGRAPH OF GIVEN WIDTH is NP-hard. Finally, it is useful to recall, as mentioned above, that for a given hypergraph and an integer k, there may exist a partial hypergraph of treewidth k -2 while there exists no partial hypergraph of treewidth k -1. Therefore, in the following (see Section 3), we will be interested in finding partial hypergraphs whose treewidth is bounded by k -1 rather than of treewidth k -1 exactly.

In the following section, we propose a polynomial-time algorithm, called k-P H, which, given a hypergraph and an integer k, calculates a partial hypergraph whose width is at most k -1, that is a k partial hypergraph. We show that this algorithm is of theoretical interest since it guarantees optimality of the result for the case of α-acyclic hypergraphs [START_REF] Beeri | On the desirability of acyclic database schemes[END_REF] (see Theorem 2). Before that, we recall here some properties related to the notion of acyclic hypergraphs.

Definition 7 (chordal graph [START_REF] Hajnal | Uber die Auflosung von Graphen in vollstandige Teilgraphen[END_REF]) A graph is chordal (or triangulated) if it contains no chordless induced cycle of length 4 or more, a chord being an edge joining two non consecutive vertices along a path. Dirac [29] that a graph is chordal if and only if all its minimal separators are cliques. Chordal graphs can also be characterized by means of perfect elimination orderings: Definition 8 (perfect elimination ordering) Given a graph G = (V, E), a perfect elimination ordering on V is a function σ : V → [1, n] such that N + σ (x) is a clique for every x ∈ V , where N + σ (x) = {y ∈ V | {x, y} ∈ E and σ(x) < σ(y)}.

It has been shown by

In fact, this ordering σ corresponds to a numbering of the vertices from 1 to n. So, in the following, we will speak about numbering to evoke this ordering. It has been shown by Fulkerson and Gross [START_REF] Fulkerson | Incidence matrices and interval graphs[END_REF] that a graph is chordal if and only if it admits a perfect elimination ordering. We can now define the notion of acyclicity in hypergraphs. It should be noted that different types of acyclicity have been defined such as Berge-acyclicity [START_REF] Berge | Graphes et Hypergraphes[END_REF], γ-acyclicity [START_REF] Fagin | Degrees of Acyclicity for Hypergraphs and Relational Database Schemes[END_REF], β-acyclicity [START_REF] Fagin | Degrees of Acyclicity for Hypergraphs and Relational Database Schemes[END_REF] and α-acyclicity [START_REF] Beeri | On the desirability of acyclic database schemes[END_REF], but the most usable and used in practice is clearly the last one:

Definition 9 (α-acyclicity) A hypergraph H = (V, E) is α-acyclic if 2 SEC (H ) is chordal and H is conformal, that is if for any clique X ⊆ V of 2 SEC (H ), there is at least one hyperedge E i ∈ E such that X ⊆ E i .
It should be noted that the relationship between hypergraph α-acyclicity and tree-decomposition are very close. Indeed, for any graph G = (V, E), for any tree-decomposition of G, it is well known that the set B of bags allows defining a hypergraph H = (V, B) which is α-acyclic.

Finally, in the next section, we use the notion of neighborhood of a vertex and neighborhood of sets of vertices in a hypergraph. We give below the associated definitions.

Definition 10 (neighborhood in a hypergraph) Let H = (V, E) be a hypergraph. For x ∈ V , the neighborhood N H (x) of x in H is defined as {y ∈ V | ∃E i ∈ E, x, y ∈ E i }. For X ⊆ V , the neighborhood N H (X) of X in H is defined as ∪ x∈X N H (x). The subset of vertices of a set Y which are neighbors of a set of vertices X is denoted N H (X, Y ) = {y ∈ Y | ∃x ∈ X : ∃E j ∈ E, {x, y} ⊆ E j }.
It is obvious that N H (X, ∅) = ∅.

Finding a Partial Hypergraph of Bounded Width

In this section, we present the algorithm k-P H (for Partial Hypergraph parametrized by an integer k). Given a hypergraph H = (V, E) and an integer k, this algorithm computes a partial hypergraph H ′ = (V, E ′ ) of H and a tree-decomposition of its 2-section whose width is at most k -1. This tree-decomposition will be represented by the set B of its bags, that is B = {B 1 , B 2 , . . . }. In practice, B is constructed bag by bag and, at the end, E ′ is the set of hyperedges of H which are covered by a bag B i . Roughly speaking, the bag B i is built by selecting some hyperedges of H ′ (B i is then defined as the union of these hyperedges) in such a way that the size of B i does not exceed k. This computation only depends on the previously built bags and the way the hyperedges are selected. So, the hyperedge selection is an important step in the construction of H ′ and its associated decomposition. Since our algorithm does not aim to guarantee to obtain an optimal solution, this step is achieved thanks to a heuristic H that constitutes the third input argument of k-P H. Note that H only relies on the previously built bags and the current value of H ′ . Once B i is built, all the hyperedges of H ′ that call into question the validity of the built tree-decomposition are removed from E ′ . Now, we give a detailed description of this algorithm and all the arguments to ensure its correctness. The time complexity is given in this section. However, our analysis requires a precise presentation of the implementation of the algorithm (e.g. the data structures used in the algorithm to ensure its efficiency). So, these elements of complexity analysis are presented in great detail in Appendix A. Then, to facilitate the understanding of k-P H, we describe it by considering the H α heuristic which will be also used in the proof of Theorem 3. Finally, without loss of generality, we consider that the rank of the hypergraph is at most k, that is no hyperedge of H has a size strictly greater than k. If some hyperedges do not satisfy this condition, we only consider the partial hypergraph of H induced by the removal of these hyperedges. Moreover, we assume that any vertex of this hypergraph belongs to at least one hyperedge.

Initially, H ′ is equal to H (line 1) and it is computed by gradually removing some of its hyperedges. The obtained tree-decomposition of 2 SEC (H ′ ) is represented by a set of bags called B (initially, B = ∅, line 2) which is also computed by gradually adding at each step a new bag denoted B i . As it is possible that H is not connected, we first compute its connected components X 1 , X 2 , . . . X n0 using the Comp-CC algorithm 2 . This algorithm takes as inputs the current partial Algorithm 1: k-P H Input: A hypergraph H = (V, E), an integer k and a heuristic H. Output: A partial hypergraph H ′ = (V, E ′ ) of H and a tree-decomposition of 2 SEC (H ′ ) represented by B (a set of bags) whose width is at most k -1.

1 H ′ = (V, E ′ ) ← (V, E) 2 B ← ∅ 3 i ← 1 4 Q ← ∅ 5 Enqueue(Q, Comp-CC(i, H ′ , V, ∅)) 6 while Q ̸ = ∅ do 7 X i ← Dequeue(Q) 8 B i ← ∅ 9 N i ← N H ′ (X i , ∪ 1≤j≤i-1 B j ) 10 if H = Hα then 11 if N i = ∅ then 12
Sort the hyperedges E j ∈ E ′ such that E j ⊆ X i in descending order of their size

13
Visit this ordered list and insert the current hyperedge

E j into B i if |B i ∪ E j | ≤ k 14 else 15 N H ′ (N i , X i ) ← {y ∈ X i | ∃x ∈ N i : ∃E j ∈ E ′ , {x, y} ⊆ E j } 16 S i ← {E j ∈ E ′ | E j ⊆ N i ∪ N H ′ (N i , X i )} 17 Select B ℓ ∈ B such that |B ℓ ∩ N i | is maximum 18 Sort the hyperedges E j ∈ S i such that E j ̸ ⊆ N i and E j ̸ ⊆ N H ′ (N i , X i ) in descending order of the size of |B ℓ ∩ E j | 19
Visit this ordered list and insert the current hyperedge

E j into B i if |B i ∪ E j | ≤ k 20
Insert in B i the hyperedges E j ∈ S i such that E j ⊆ B i which were not selected in the previous step

21
Remove from H ′ the hyperedges Once these preliminary processes have been realized, at each new step of the loop in line 6, a connected component X i is removed from the queue Q to build a new bag B i (line 7). So, before, B i is initialized to the empty set (line 8). This new bag will be added to the tree-decomposition already computed (current set of bags B), and H ′ will be updated by removing the hyperedges whose conservation would distort the tree-decomposition. Considering the connected component X i removed from the queue Q, the set of nodes N i is initialized (line 9). N i is the set of vertices that belong to at least one of the bags in B = {B 1 , B 2 , . . . , B i-1 } and that are adjacent to at least one vertex of X i in H ′ . Formally, 1 and recall Definition 10). There are then two cases to consider for the connections in the hypergraph H ′ :

E j ∈ S i such that E j ̸ ⊆ N i and E j ̸ ⊆ N H ′ (N i , X i ) and E j ̸ ⊆ B i 22 B ← B ∪ {B i } 23 Enqueue(Q, Comp-CC(i, H ′ , X i , B i )) 24 i ← i + 1
N i = N H ′ (X i , ∪ 1≤j≤i-1 B j ) (see Figure
(1) (Basic case) Either X i has no neighbor in N i (this is the case, for instance, in the first step since the set N i is empty because B = ∅);

(2) (General case) Or X i has at least one neighbor in N i .

In case (1), we proceed by searching within X i a new bag B i . This bag is obtained by computing a set of hyperedges included in X i whose union is equal to the bag B i and such that |B i | ≤ k. Such a bag is found using a given heuristic H. In the description of k-P H presented in Algorithm 1, this step is illustrated with the H α heuristic (lines 12 and 13). For this case, no hyperedge has to be deleted from H ′ . Case (2) is the general case and it is more intricate. The new bag B i is calculated in the neighborhood of an already computed bag

B ℓ (1 ≤ ℓ < i) such that B i ∩ B ℓ = N i ∩ B ℓ ̸ = ∅.
This guarantees that we obtain a tree-decomposition because any new bag B i is linked to at least one bag

B ℓ ∈ {B 1 , B 2 , . . . , B i-1 } and such that (∪ 1≤j≤i-1 B j )∩B i ⊆ (B ℓ ∩B i ).
This condition allows us to verify that the computed set of bags can be structured as a tree. Moreover, it allows satisfying the third condition (condition (iii)) of tree-decompositions which deals with the links between bags. About the bag B ℓ , note that there are two options. Either this bag B ℓ can be pre-determined and then B i is defined with respect to B ℓ , or, on the contrary, B ℓ is determined with respect to the new bag B i . This choice depends on the used heuristic H. Several heuristics are conceivable but we consider here as a reference and as for case 1, the H α heuristic, which is a very simple and natural heuristic that chooses first as bag B ℓ the one with the largest intersection with N i and then, chooses as the first hyperedge to be in B i the one that shares the maximum number of vertices with B ℓ (the next hyperedges are taken with the same principle, in descending order of the size of their intersection with B ℓ ).

B j U 1≤j<i N i N i N ( , ) H' X i X i class 1 class 3 class 2 class 2
∪ 1≤j≤i-1 B j , N i , X i and N H ′ (N i , X i ). 4 hyperedges illustrate the 3 possible classes of hyperedges inside N i ∩ N H ′ (N i , X i ).
The set of hyperedges that are candidates for the construction of B i is denoted S i and is defined by

S i = {E j ∈ E ′ | E j ⊆ N i ∪ N H ′ (N i , X i )}.
To compute B i , some hyperedges from S i are selected and they constitute a set S ′ i ⊆ S i . Thus, B i is obtained by the union of the hyperedges from S ′ i , i.e. B i = ∪ Ej ∈S ′ i E j . So, we analyze the hyperedges E j of S i . We have three classes of hyperedges:

(1) E j ⊆ N i and therefore

E j ∩ N H ′ (N i , X i ) = ∅.
In this case, the hyperedge E j appears in N i , thus in at least one bag already computed.

(

) E j ̸ ⊆ N i and E j ̸ ⊆ N H ′ (N i , X i ). Thus E j ∩ N i ̸ = ∅ and E j ∩ N H ′ (N i , X i ) ̸ = ∅. In this case, the hyperedge E j overlaps N i and N H ′ (N i , X i ). 2
(

) E j ⊆ N H ′ (N i , X i ) ⊆ X i and thus E j ∩ N i = ∅. 3
Figure 1 shows the sets ∪ 1≤j≤i-1 B j , N i , X i and N H ′ (N i , X i ), and indicates the location of the hyperedges in relation to the class to which they belong.

The hyperedges E j of class (1) have already been treated during the calculation of the previous bags. They can therefore be ignored and they will appear in the hypergraph H ′ at the end of processing. They will therefore not be taken into account in the calculation of B i even if they may eventually be included inside. Likewise, calculating B i , we will not consider the hyperedges of class (3). However, some of these could also be included in B i . Thus, only the hyperedges of class (2) will be explicitly considered for the calculation of B i . We analyze this case.

B i will be defined as ∪ Ej ∈S ′ i E j . So, when selecting a subset S ′ i of hyperedges of S i , a first condition to satisfy is related to the bound of the width and therefore we must calculate a subset

S ′ i of S i such that |B i | ≤ k. In addition, we must impose that B i ∩ N H ′ (N i , X i ) ̸ = ∅,
that is B i must include at least one vertex which does not appear in the bags already computed. This second condition is necessary because one must ensure that the size of the tree-decomposition grows strictly during the calculation (i.e. at each step of the loop) so as to guarantee the termination of the algorithm. So, by increasing the size of the tree-decomposition, we mean the number of bags of the tree-decomposition, and thus, the number of new vertices appearing in at least one bag of B. Note that this second condition necessarily holds since only class (2) hyperedges are taken into account and each of them contains at least one vertex that does not appear in an already calculated bag. A third condition must be verified to make sure that there exists an already built bag B ℓ , with

1 ≤ ℓ < i, such that (∪ 1≤j≤i-1 B j ) ∩ B i ⊆ (B ℓ ∩ B i ).
By fulfilling these three conditions, we just have to choose, with the heuristic, hyperedges of S i which will define the set S ′ i . Recall that we suppose that this heuristic takes as a bag B ℓ the one that has the largest intersection with N i . Figure 2 shows different possibilities for the selection of hyperedges in a new bag.

Once S ′ i is calculated, H ′ has to be updated (line 21). Only hyperedges E j ∈ S i belonging to the class (2) such that E j ̸ ⊂ B i may be removed. Indeed, all hyperedges from class (1) are preserved because they belong to bags already computed. Hyperedges from classes (3) are preserved too: if they are included in B i , they must be retained; and it is also the case if they are not included in B i because they will be considered later. It is the same for hyperedges E j from class [START_REF] Montanari | Networks of Constraints: Fundamental Properties and Applications to Picture Processing[END_REF] such that E j ⊆ B i . The hyperedges E j ∈ S i that must be deleted are exactly such that E j ∩ N i ̸ ⊂ B i and E j ∩ B i ̸ ⊂ N i . In other words, these are the hyperedges that have disjoint intersections with at least two bags already constructed, because including them later in a bag will prevent us from maintaining the tree structure of B.

After updating H ′ (for case 2) and computing B i , we calculate the connected components of

H ′ [[X i \B i ]] (line 23), that is X i1 , X i2 , . . . X in i which are then be inserted into Q. This task is repeated until the queue Q is empty. E i B i B l E j' B j U 1≤j<i N i N i N ( , ) H' X i X i E j
Figure 2: Bag building stage. Bags B ℓ and B i are in blue. Among the 3 hyperedges of class 2, E j must be deleted while E i will be preserved in the final partial hypergraph and E j ′ is temporary at least preserved.

x 1

x 2 x 3 x 4 x 5 E 1 E 2 E 3 E 4 E 5 x 1 x 2 x 3
x 4

x 5

x 6

x 7

x 8

x 9

x 11

x 10

x 12

x 13

x 14

x 15

x 16

x 17

x 18 Note that at the end of the while loop, some vertices may not have been processed. Indeed, this case is possible if some vertices only appear in the hyperedges deleted during the construction of H ′ . So, none of these vertices can be included in a bag when constructing B during the loop. This is why, at the end of processing (line 25), specific bags are defined for each of these vertices, so as to ensure that B will correspond to the bags of a tree-decomposition of 2 SEC (H ′ ) since every vertex must appear in at least one bag. Note that if at the end of the process, H ′ is not connected, we finally obtain a collection of trees, and thus a forest of tree-decompositions.

E 1 E 2 E 3 E 4 E 5 E 6 E 7 E 8 E 9 E 10 E 11 E 12 (a) (b)
We illustrate how k-P H with the heuristic H α works on the two instances of Figure 3. First, we apply k-P H with k = 2 on the graph (V = {x 1 , . . . , x 5 }, E = {E 1 , . . . , E 5 }) depicted in Figure 3(a). Initially, X 1 corresponds to V since the graph is connected, N 1 = ∅ and any edge can be selected by the heuristic. In line 13 of k-P H, suppose that the first chosen edge is

E 1 = {x 1 , x 2 }. It ensues that B 1 = {x 1 , x 2 }.
The call of Comp-CC then builds two connected components, {x 3 } and {x 4 , x 5 }, which will be inserted in Q. In the next step, suppose that {x 3 } is removed from Q and so that X 2 = {x 3 }. In this case, line 9 calculates N 2 = {x 2 } and line 14 is executed. So we have

N H ′ (N 2 , X 2 ) = {x 3 } (line
B ℓ = B 1 , or B ℓ = B 3 (line 17). If B ℓ = B 1 , E 3 is
necessarily used to build B 4 , and no edge will be added to it (line 20). Then, E 5 is removed from H ′ since we have

E 5 ̸ ⊆ N 4 , E 5 ̸ ⊆ N H ′ (N 4 , X 4
) and E 5 ̸ ⊆ B 4 . Running Comp-CC (line 23) will not compute a new connected component, and since Q is empty, the algorithm will stop. We notice that if B ℓ = B 3 , the algorithm will calculate B 4 = E 5 because E 5 will be kept but E 3 deleted from H ′ . Now, let us consider the hypergraph (V = {x 1 , . . . , x 18 }, E = {E 1 , . . . , E 12 }) of Figure 3(b). We illustrate the execution of k-P H over it when k is set to 5 thanks to Table 1. This table specifies the state of the various objects manipulated at each stage. Let us note that, unlike the first example, and because of the deletion of the hyperedge E 3 from H ′ , a vertex will be isolated, namely the vertex x 7 which belongs to E 3 but which does not appear in any hyperedge kept in H ′ . Also, the bag B 7 which contains only x 7 is calculated on Line 25 of k-P H.

i Xi Ni N H ′ (Ni, Xi) Si B ℓ Bi H ′ Q - - - - - - - (V, E) [V ] 1 V ∅ - - - E6 ∪ E4 = (V, E) [{x12, . . . ,
4 {x14, x16, {x9, x15} {x14, x17, x18} {E7, E9, E11} B2 E7 ∪ E9 ∪ E11 = (V, E) [{x1, x4, x7}, x17, x18} {x9, x14, x15, x17, x18} {x16}] 5 {x1, x4, x7} {x2, x3, x6} {x1, x4, x7} {E1, E3} B3 E1 = (V, E\{E3}) [{x16}] {x1, . . . , x4} 6 {x16} {x14, x17, x18} {x16} {E10, E12} B4 E10 ∪ E12 = (V, E\{E3}) ∅ {x14, x16, x17, x18} 7 - - - - - B7 = {x7} (V, E\{E3}) - Table 1: Execution of k-P H on the hypergraph of Figure 3(b) with k = 5.
As k-P H exploits a heuristic H, its correctness also depends on that of H. So, before proving the correctness of k-P H, we specify the necessary conditions that H must verify. To be correct, the heuristic H must therefore :

• calculate a new bag B i of size at most k,
• select at least one hyperedge of S i whose class is 2,

• make sure that the new bag B i is such that there exists one already computed bag

B ℓ such that (∪ 1≤j≤i-1 B j ) ∩ B i ⊆ (B ℓ ∩ B i ).
For example, it can easily be shown that the heuristic H α satisfies these conditions.

Theorem 1 k-P H is correct under the assumption that the heuristic H is correct.

Proof: To prove the correction of k-P H, we must show that:

(1) k-P H ends;

(2)

H ′ = (V, E ′ ) is a partial hypergraph of H;
(3) B is a the set of bags of a tree-decomposition of 2 SEC (H ′ ) whose width is at most k -1.

We prove each of these assertions.

(1) At each step of the loop, we add to B a new bag that contains at least one vertex that does not appear in any previous bag. Also, after a finite number of iterations through the loop, no new connected components will be inserted into the queue, and this queue will become empty and thus the loop will stop.

(2) By construction, H ′ = (V, E ′ ) is a partial hypergraph of H.

(3) We must show that the 3 conditions required for a tree-decomposition are verified:

(i) (∪ i∈I B i = V ) By construction, we know that each vertex of H ′ belongs to at least one bag. It should be remembered here that for each one of the vertices that do not appear in any hyperedge selected in H ′ , the last step of k-P H builds a specific bag. So, this property is satisfied.

(ii) (For every edge {x, y} of the graph, ∃i ∈ I such that {x, y} ⊆ B i ) This property is verified since the bags in B are defined by the hyperedges of H ′ and thus, every hyperedge of H ′ is included in at least one bag. Since we consider here 2 SEC (H ′ ), that is the 2-section of H ′ , all the edges of this graph are included in at least one bag.

(iii) (∀i, j, k ∈ I, if k is on a path between i and j in T , then B i ∩ B j ⊆ B k ) We know that by construction, for any new bag B i , there is at least one previous bag

B ℓ such that (∪ 1≤j≤i-1 B j ) ∩ B i ⊆ (B ℓ ∩ B i ).
So, if we assume that in the tree-decomposition, there is an edge that connects B ℓ to B i , it is easy to see that for any previous bag B j (that is 1 ≤ j ≤ l), necessarily we have B i ∩ B j ⊆ B ℓ . Then by induction, it is easy to see that this property holds for every B ℓ ′ which is on a path between B i and B j in the tree-decomposition, that is B i ∩ B j ⊆ B ℓ ′ . So, this third property of tree-decompositions is satisfied.

Finally, by construction, we know that the size of bags belonging to B is at most k. So, the width of the treedecomposition of 2 SEC (H ′ ) induced by B is at most k -1.

To conclude, it should be remembered that the validity of the algorithm is of course conditioned by the validity of the used heuristics. In fact, it is enough to consider heuristics that will be compatible with the conditions imposed. Indeed, trivially, a heuristic allowing to build bags whose size is strictly greater than k will not allow ensuring the correctness of k-P H algorithm if it uses it. 2

The time complexity of k-P H cannot be evaluated without knowing in detail the cost of the different internal treatments such as Comp-CC, the computing of a new bag B i , the cost of the heuristic H, and also, the cost of updating H ′ . In order to make these different treatments efficient, several data structures must be implemented and these must be detailed. These descriptions and a detailed version of the different algorithms and their time complexity analysis are given in Appendix A. We present here the results of this evaluation. So, before that, we recall some notations:

• n is the number of vertices in V ;

• e is the number of hyperedges in E;

• d is the maximum degree among all the vertices in H (the degree d(v) of a vertex v is the number of hyperedges in E containing v);

• r is the rank of the hypergraph, that is the maximum size of the hyperedges in E;

• N is the number of bags in the computed tree-decomposition.

Moreover, to assess the complexity of k-P H, we assume that the cost of the considered heuristic H is h.

Theorem 2 The time complexity of k-P H is in O(N (h + e • r + n • d(N + r))).
To give an illustration of this complexity, we consider the complexity of the heuristic H α which is O(n • k + e • r). So, using this heuristic, the time complexity of

k-P H is O(N (h + e • r + n • d(N + r))) = O(N (n • k + e • r + n • d(N + r))).
This expression can be rephrased if we consider certain upper bounds. Indeed, we know that N ≤ n, we thus obtain the complexity O(n(n

• k + e • r + n • d(n + r))) = O(n • n • k + n • e • r + n • n • d • n + n • n • d • r) = O(n 2 • k + n • e • r + n 3 • d + n 2 • d • r) = O(n 2 • (k + n • d + r • d) + n • e • r)
. On the other hand, if we also consider that the width k -1 is a constant, and therefore that the treatments will only consider hyperedges whose size is less than or equal to k, this complexity can be reduced to

O(n 3 • d + n • e).
As mentioned previously, this algorithm does not guarantee that the obtained hyperedge set is maximal for inclusion. However, it has certain properties related to optimality, as soon as hypergraphs belonging to particular classes are considered as input. Among these classes, one can find α-acyclic hypergraphs [START_REF] Beeri | On the desirability of acyclic database schemes[END_REF]. In this case, it is sufficient to adapt the parameter k to show that their processing is optimal using k-P H. It should be noted that the relationship between hypergraph α-acyclicity and tree-decomposition are very close. Indeed, for any graph G = (V, E), for any tree-decomposition of G, it is well known that the set B of bags allows defining a hypergraph H = (V, B) which is α-acyclic. Moreover, the associated tree-decomposition is then a join tree, and in this case, assuming that k is the rank of the hypergraph H, the maximal partial hypergraph H ′ that must be computed is exactly H. So, in this case, the MAXIMAL PARTIAL HYPERGRAPH OF BOUNDED WIDTH problem can be solved efficiently. Finally, given an α-acyclic hypergraph, it is easy (possible in linear time [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF]) to recognize it and then compute an optimal tree decomposition of its 2-section. Nevertheless, we show here that k-P H is optimal in terms of result without knowing beforehand that the hypergraph is α-acyclic.

To show the optimality of the result of k-P H for α-acyclic hypergraphs, we first need to give a particular value for the parameter k which is related to the size of the largest hyperedge in H. Then we have to consider the heuristic H α recalling that H α constructs the first bag B 1 by choosing as many maximum size hyperedges as possible while making sure that the condition |B 1 | ≤ k holds. By so doing, when k is equal to m, B 1 will contain a hyperedge of size k, and possibly smaller included hyperedges. Then, for building a bag B i , it first chooses as bag B ℓ the existing bag having the largest intersection with N i . Once B ℓ selected, it selects as the first hyperedge to be in B i the one that shares the maximum number of vertices with N i . Finally, this latter step is repeated until no hyperedge can be added without violating the condition |B i | ≤ k.

Theorem 3 If a connected hypergraph H = (V, E) is α-acyclic and if k is equal to the maximum size of hyperedges in H, then the result of k-P H with H α is optimal, that is k-P H finds a partial hypergraph H ′ = (V, E ′ ) such that E ′ = E.

Proof: We have to show that during the calculation of H ′ , no hyperedge is deleted.

In k-P H, the removed hyperedges belong to class [START_REF] Montanari | Networks of Constraints: Fundamental Properties and Applications to Picture Processing[END_REF]. These are the hyperedges that overlap N i and N H ′ (N i , X i ), namely, hyperedges

E j ∈ E ′ such that E j ⊆ N i ∪ N H ′ (N i , X i ) and N H ′ (N i , X i ) ∩ E j ̸ = ∅ and N i ∩ E j ̸ = ∅. The hyperedges E j ∈ S i that are deleted are exactly such that E j ∩ N i ̸ ⊂ B i and E j ∩ B i ̸ ⊂ N i .
The hyperedges E j that are deleted are such that E j ∩ B i ̸ = ∅ and of course also E j ̸ ⊂ B i , but among these, the ones that satisfy E j ∩ N i ⊆ B ℓ ∩ B i must not be deleted. We show that if H is α-acyclic, none of these hyperedges can appear during the calculation of H ′ , and thus no hyperedge is deleted. To do this, we show that at each step of the algorithm, the partial sub-hypergraph taken into account for the calculation of the bags is acyclic and that this ensures that there is at least one hyperedge that avoids any deletion of hyperedge. The proof is organized first by treating the basic case for the calculation of the first bag, then for each of the subsequent steps.

First, we take for B 1 a hyperedge of maximum size, that is k. It is the only particular adaptation of the algorithm to find the optimal result. B 1 contains a hyperedge of size k, and possibly smaller included hyperedges. Then, connected components induced by the deletion of B 1 are calculated and inserted into Q. Of course, no hyperedge is removed for the calculation of H ′ since it is the particular case of the first step. Moreover, once B 1 has been calculated, if X 1 , X 2 , . . . X n1 are the n 1 sets stored in Q, one can observe that for each

X i (1 ≤ i ≤ n 1 ), the hypergraph H ′ [B 1 ∪ X i ] is α-acyclic. We prove this below.
We know that a hypergraph is α-acyclic if and only if it is conformal and chordal. As any subgraph of a chordal graph is chordal, then the graph

2 SEC (H ′ [B 1 ∪ X i ]) is chordal because it is a subgraph of 2 SEC (H ). We now show that H ′ [B 1 ∪ X i ] is conformal. No hyperedge included in B 1 ∪ X i is deleted, and no new edge has appeared in 2 SEC (H ′ [B 1 ∪ X i ]). Indeed, all edges of 2 SEC (H ′ [B 1 ∪ X i ]) induced by hyperedges of H intersecting B 1 and which do not appear in H ′ [B 1 ∪ X i ] are already in 2 SEC (H ′ [B 1 ∪ X i ]) due to the existence of the hyperedge B 1 in H ′ [B 1 ∪ X i ].
It follows that no new clique which would not be covered by a hyperedge of

H ′ [B 1 ∪ X i ] does not appear in 2 SEC (H ′ [B 1 ∪ X i ]) and thus that the hypergraph H ′ [B 1 ∪ X i ] is conformal.
We need another property to show the maximality of the calculation performed by k-P H, i.e. no hyperedge is removed when calculating H ′ . It deals with the interaction between the already constructed bags and the connected components stored in Q. We first study this property concerning the computation of B 1 . We know that B 1 is a hyperedge of H ′ [B 1 ∪X i ] and thus, there is at least one hyperedge

E i of H ′ [B 1 ∪ X i ] such that E i ∩ X i ̸ = ∅ and E i ∩ B 1 = N i .
We show the existence of such a hyperedge. Since the graph 2 SEC (H ′ [B 1 ∪ X i ]) is chordal, it admits a perfect elimination ordering. In this perfect elimination ordering, we consider the numbering of the vertices among those of N i ∪ N H ′ (N i , X i ). More precisely, rather than considering

N H ′ (N i , X i ) we consider Sep ⊆ N H ′ (N i , X i ) which is a minimal separator in 2 SEC (H ′ [B 1 ∪ X i ])
between N i and the vertices of X i that do not belong to

N H ′ (N i , X i ). Since 2 SEC (H ′ [B 1 ∪ X i ]
) is a chordal graph and any minimal separator in such a graph is a clique, we know that Sep is a clique of

2 SEC (H ′ [B 1 ∪ X i ]). Since Sep is a separator in 2 SEC (H ′ [B 1 ∪ X i ]
), we know that all the edges that connect N i to X i have a vertex in Sep. We will consider two cases. Either (case 1) a vertex of N i is numbered before the first vertex of Sep is numbered, or (case 2) some vertices of Sep are numbered before vertices of N i are numbered:

(1) Let x be the first vertex of N i which is numbered before the vertex of Sep that is numbered first. As we consider a perfect elimination ordering, necessarily, all neighbors of x in

N i ∪ N H ′ (N i , X i ) constitute a clique. The neighbors of x in N i ∪ N H ′ (N i , X i
) are on the one hand all the other vertices of N i and on the other hand at least one vertex of Sep because there is at least one edge from x linking an unnumbered vertex of Sep in 2 SEC (H ′ [B 1 ∪ X i ]). On the other hand, as H ′ [B 1 ∪ X i ] is α-acyclic, this hypergraph is thus conformal, and it has at least one hyperedge E i which contains all the vertices of this clique formed of N i and at least the neighboring vertex of x in N H ′ (N i , X i ).

(2) Consider now that the first numbered vertices appear in Sep. We distinguish two cases:

(i) All the vertices of Sep are numbered before the ones of N i . In this case, each time a vertex of Sep is numbered, its neighbors in N i must be linked to all vertices of Sep not yet numbered because Sep is a clique. And so, the last vertex of Sep which is numbered has for neighbors all the vertices of N i because they all have at least one neighbor vertex in Sep. Thus, the last vertex of Sep which is numbered is a neighbor of all the vertices of N i and thus all these vertices constitute a clique.

(ii) A vertex x of N i is numbered before that all the vertices of Sep are numbered. We then consider the first vertex of N i which is numbered. In cases (i) and (ii), we have thus shown that there is a clique consisting of all the vertices of N i and at least one vertex of Sep in 2 SEC (H ′ [B 1 ∪ X i ]). Thus, because of the conformity of H ′ [B 1 ∪ X i ], there is at least one of its hyperedges E i which contains all these vertices.

Assume now that what is valid for this first stage holds for any stage, namely that for any X i memorized in Q, X i was built then inserted in Q starting from a bag B ℓ such that the hypergraph H ′ [B ℓ ∪ X i ] to which one adds a hyperedge formed by the vertices of B ℓ is α-acyclic (this hypergraph is denoted

H ′ [B ℓ ∪ X i ] + B ℓ ). Moreover, there is at least one hyperedge E i of H ′ [B ℓ ∪ X i ] + B ℓ such that E i ∩ X i ̸ = ∅ and B ℓ ∩ E i = N i .
Now, for the i th step (1 < i), B contains the bags B 1 , . . . B i-1 . Let X i be the connected component removed from Q, and let B ℓ be the existing bag used to build X i . We recall that the heuristic H α first chooses as bag B ℓ the existing bag having the largest intersection with N i and then, chooses as the first new hyperedge to be in B i the one that shares the maximum number of vertices with N i . First, the previous bag selected by H α is necessarily the same bag B ℓ that was used to construct X i and insert it into Q (or a bag with the same intersection with N i ). By induction hypothesis, we know that the hypergraph H ′ [B ℓ ∪ X i ] + B ℓ is α-acyclic and that there is at least one hyperedge

E i of H ′ [B ℓ ∪ X i ] + B ℓ such that E i ∩ X i ̸ = ∅ and B ℓ ∩ E i = N i .
So, for the calculation of B i , necessarily such a hyperedge E i is chosen by the heuristic H α and belongs to the new bag B i (E i ⊆ B i ). Other hyperedges from S i can be added to B i . By induction hypothesis, since B ℓ ∩ E i = N i , we have N i ⊂ E i . Thus, all the hyperedges E j of class 2 verify E j ∩ N i ⊆ E i and as by construction

E i ⊆ B i , necessarily E j ∩ N i ⊆ B i . As the hyperedges E j ∈ S i that are deleted are such that E j ∩ N i ̸ ⊂ B i (and E j ∩ B i ̸ ⊂ N i ), no hyperedge of H ′ is deleted.
So, after the calculation of the new connected components induced by B i , we must ensure that the induction property holds. First, for the connected components of

H ′ [[X i \B i ]], that is X i1 , X i2 , . . . X in i which will then be inserted into Q, we must verify that each hypergraph H ′ [B i ∪ X ij ] + B i (with 1 ≤ j ≤ n i ) is α-acyclic and that there exists at least one hyperedge E ij belonging to H ′ [B i ∪ X ij ] + B i such that E ij ∩ X ij ̸ = ∅ and B i ∩ E ij = N ij .
We prove first that ∀j, 1 ≤ j ≤ n i , the hypergraph H ′ [B i ∪ X ij ] + B i is α-acyclic. The proof is close to the one given above for B 1 but slightly more complicated because of the existence in H ′ [B i ∪ X ij ] + B i of the hyperedge B i . We know that a hypergraph is α-cyclic if and only if it is conformal and chordal.

• (Chordal). As H ′ [B ℓ ∪ X i ] + B ℓ is α-acyclic, so the graph 2 SEC (H ′ [B ℓ ∪ X i ] + B ℓ ) is chordal. Contrary to the basic
case where B 1 is both a bag and a hyperedge of H, here B i is not necessarily a hyperedge of H and therefore

2 SEC (H ′ [B i ∪ X ij ] + B i ) is not necessarily a subgraph of 2 SEC (H ′ [B ℓ ∪ X i ] + B ℓ ) because edges that are not in 2 SEC (H ′ [B ℓ ∪ X i ] + B ℓ ) may belong to 2 SEC (H ′ [B i ∪ X ij ] + B i )
due to the existence of the hyperedge B i and its completion in the 2-section. We show that no chordless cycle can have been created by the addition of such edges. For such a cycle to be created, it must contain at least 4 vertices of which two vertices x and y belong to B i , and two other vertices u and v belong to X ij , with {x, u} et {y, v}, edges of

2 SEC (H ′ [B i ∪ X ij ] + B i ) considering that x and y are not neighbors in 2 SEC (H ′ [B ℓ ∪ X i ] + B ℓ ) but are neighbors in 2 SEC (H ′ [B i ∪ X ij ] + B i ) (by completion of the hyperedge B i ).
We know that there is necessarily a path from u to v internal to

X ij in 2 SEC (H ′ [B i ∪ X ij ] + B i ) (and thus already in 2 SEC (H ′ [B ℓ ∪ X i ] + B ℓ )) because X ij is a connected component.
Adding the edge {x, y} would then create a chordless cycle in

2 SEC (H ′ [B i ∪ X ij ] + B i ).
(H ′ [B i ∪ X ij ] + B i ).
Therefore, this graph is chordal.

• (Conformal). It is necessary to show that H ′ [B i ∪X ij ]+B i is conformal, and thus that any clique of 2 SEC (H ′ [B i ∪ X ij ] + B i ) is included in a hyperedge of H ′ [B i ∪ X ij ] + B i .
We know that all the cliques included in B i are covered by the hyperedge B i . In the same way, all the cliques included in X ij are covered by a hyperedge appearing in this part of It remains now to be proved that there exists at least one hyperedge

H ′ [B i ∪ X ij ] + B i since it
E ij belonging to H ′ [B i ∪ X ij ] + B i such that E ij ∩ X ij ̸ = ∅ and B i ∩ E ij = N ij .
In fact, it is sufficient to use the same scheme of proof as in the basic case. Indeed, and unlike the case of the α-acyclicity of the hypergraph H ′ [B i ∪ X ij ] + B i , here the conditions of the basic case are preserved and the proof is identical. 2 Surprisingly, unless the basic heuristic proposed here is modified, the class of chordal graphs is unfortunately not processed optimally by this algorithm. One can very easily find counter-examples based on a few vertices (e.g. a k-tree with k = 2).

The following section presents an evaluation of the performance of this algorithm both in terms of computation times and the quality of the computation results, and thus the proportion of hyperedges belonging to the obtained partial hypergraph.

Experimental Evaluation

In this section, we study the behavior of k-P H on a large benchmark of hypergraphs from various communities. We first describe our experimental protocol. Then, we assess its efficiency by considering its capacity to get closer to the optimum and its runtime. Finally, we consider the behavior of k-P H depending on the value of k.

Experimental Protocol

We implement k-P H in our own C++ hypergraph library. The experiments are performed on Dell PowerEdge R440 servers with Intel Xeon Silver 4112 processors (clocked at 2.6 GHz) under Ubuntu 18.04. For each instance and a given integer k, k-P H with a given heuristic H is allocated a slot of 30 minutes and at most 16 GB of memory per instance.

We describe below the heuristics H we consider in k-P H and the benchmark exploited in our experimentations.

The Considered Heuristics

We considered and implemented several heuristics. In this section, we only report the results obtained by the two more interesting ones. Moreover, in the following definitions, we assume that the hyperedges whose size exceeds the parameter k of k-P H have been deleted first.

The first heuristic we consider is the heuristic H α defined for the need of Theorem 3 and which is used in the description of the k-P H algorithm. We give some more details about this heuristic. H α constructs the first bag B 1 by choosing as many maximum size hyperedges as possible while making sure that the condition |B 1 | ≤ k holds. Then, for building a bag B i , it first chooses as bag B ℓ the existing bag having the largest intersection with N i . Once B ℓ is selected, it selects as the first hyperedge to be in B i the one that shares the maximum number of vertices with N i . Finally, this latter step is repeated until no hyperedge can be added without violating the condition |B i | ≤ k. As mentioned above, H α is designed in order to ensure the optimality of k-P H on α-acyclic hypergraphs when k = m.

The second one, denoted H ∩ , starts the construction of B 1 like H α by choosing a hyperedge of maximum size. Then it adds as many hyperedges as possible in B 1 (that is under the condition |B 1 | ≤ k) by selecting first the hyperedges having the largest intersection with B 1 . Regarding the build of B i , it first chooses as bag B ℓ the existing bag which intersects the largest number of candidate hyperedges from S i . By so doing, we want to preserve as many hyperedges as possible among the hyperedges of S i . Finally, H ∩ builds B i like B 1 but by only considering the hyperedges of S i which intersect B ℓ . In some manner, H ∩ aims to built bags whose hyperedges overlap each others. Such a property may be notably of interest when we consider the problems related to these hypergraphs (e.g. solving graphical models). Whereas solving the related problems is out of the scope of this paper, studying such a heuristic has sense here.

Regarding the time complexity, H α and H ∩ run respectively in O(n

• k + e • r) and O(n 2 • e + k 2 • e 2 )
. For H ∩ , using the Bag list data structure, the selection of B ℓ can be achieved in O(N • |S i |). Indeed we have to count the number of hyperedges of S i which intersect each existing bag and the number of existing bags is bounded by N . Building a bag B i can be achieved in O(k 2 • |S i | 2 ). Indeed, computing the intersection of each candidate hyperedge with B i is feasible in O(k 2 ) because the hyperedges and the bag have a size bounded by k and this is done at most

|S i | times. So it results that H ∩ has a time complexity in O(N • |S i | + k 2 • |S i | 2 ) = O(n • e + k 2 • e 2 ) knowing that N ≤ n and |S i | ≤ e.

Benchmarks

In order to make our experimentations as representative as possible, we consider hypergraphs from various communities. The considered hypergraphs are produced from instances that are usually exploited for benchmarking by these communities. Notably, in each community, these instances make it possible to compare solving methods for different problems which are generally at least NP-complete. They model both academic and real-world problems. We divide the benchmark into five categories depending on their origin. In each category, we only consider hypergraphs whose treewidth can be computed by the method of Tamaki3 [START_REF] Dell | The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration[END_REF]. We now describe each category:

• B CSP : We consider 5,996 instances from the CSP3 repository 4 . From each CSP instance I, we build a hypergraph (called the constraint hypergraph) whose vertices correspond to the variables of I and the hyperedges correspond to the scopes of its constraints.

• B W CSP : We consider 1,535 WCSP instances from the EvalGM repository5 and the ERGO repository 6 . The Weighted Constraint Satisfaction Problem (WCSP) allows to express optimization problems [START_REF] Rossi | Handbook of Constraint Programming[END_REF]. Like for CSP instances, from each WCSP instance I, we build a hypergraph whose vertices correspond to the variables of I and the hyperedges correspond to the scopes of its weighted constraints (or cost functions). Note that these hypergraphs are computed after applying a preprocessing step on the original WCSP instances. This preprocessing step is performed thanks to Toulbar27 . It consists in enforcing VAC (for Virtual Arc-Consistency [START_REF] Cooper | Virtual arc consistency for weighted csp[END_REF]) and applying the MSD (for Min Sum Diffusion) algorithm with 1,000 iterations. It is usually exploited in this community and may lead to reduce the number of variables and cost functions before solving the instances.

• B H : We consider 2,871 hypergraphs from the HyperBench repository8 [START_REF] Fischl | Hyperbench: A benchmark and tool for hypergraphs and empirical findings[END_REF][START_REF] Bonifati | An Analytical Study of Large SPARQL Query Logs[END_REF][START_REF] Bonifati | Navigating the Maze of Wikidata Query Logs[END_REF][START_REF] Pottinger | MiniCon: A scalable algorithm for answering queries using views[END_REF][START_REF] Benedikt | Benchmarking the chase[END_REF]. These hypergraphs have been produced from Conjunctive Queries and CSP instances with the aim in view to study their hypertree width, generalized hypertree width and fractional hypertree width [START_REF] Grohe | Constraint solving via fractional edge covers[END_REF].

• B M C : We consider 511 instances of model counting from the Cachet repository9 [START_REF] Sang | Performing Bayesian inference by weighted model counting[END_REF]. Each instance models a Bayesian Inference problem as a weighted model counting instance. From each instance I, we build a hypergraph whose vertices correspond to the Boolean variables of I and the hyperedges correspond to its clauses.

• B M N : We consider 389 Markov networks from the Probabilistic Inference Challenge 2011 10 . From each instance I, we build a hypergraph whose vertices correspond to the variables of I and the hyperedges correspond to the scopes of its functions.

Table 2 provides some information about the hypergraphs of each category, namely the minimum, maximum, average and standard deviation for the number of vertices, the number of hyperedges, the maximum size of hyperedges and the treewidth for each category. Finally, we denote B all the union of the five categories. So B all involves 11,302 hypergraphs.

Optimality and Runtime of k-P H

In this part, we aim to assess how close k-P H can be to optimality. For this purpose, we consider the percentage of hyperedges that are retained by k-P H when the parameter k is set to the treewidth of the considered hypergraph plus one. The higher the percentage is, the closer k-P H will be to optimality. Table 3 presents the number of hypergraphs depending on the percentage of hyperedges retained by k-P H for H α and H ∩ . First, we can observe that about 12.5% of hypergraphs (respectively 13%) in B all are optimally processed by k-P H with H α (resp. H ∩ ). These hypergraphs are not necessarily α-acyclic. Indeed, there exist 20 α-acyclic hypergraphs in B CSP (resp. 484 in B H and 5 in B M N ) while there is none in B W CSP and B M C . Note that all the α-acyclic hypergraphs except 20 are also β-acyclic. Now, we consider the algorithm MCS [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF] in order to determine whether the 2-section of a hypergraph is chordal. If not, we exploit the number of edges that will be added if we triangulate the 2-section according to the elimination order produced by MCS. This number allows us to estimate how the 2-section is close to being chordal. We then observe that 1,117 hypergraphs have a chordal 2-section among the hypergraphs which are processed optimally. This number includes of course the 509 α-acyclic hypergraphs. Moreover, 131 hypergraphs are close to being chordal with at most 10 edges added by the triangulation based on MCS. In the same spirit, we remark that k-P H with H α and H ∩ respectively retains more than 75% of hyperedges for about 93% and 96% of hypergraphs having a chordal 2-section ( 2: Minimum, maximum, average and standard deviation for the number of vertices, the number of hyperedges, the maximum size of hyperedges and the treewidth for each category. hypergraphs). At the same time, the corresponding percentage for non-chordal hypergraphs is about 82%. So, having a chordal 2-section turns to be an interesting property to guarantee a result close to the optimality. Now, if we compare the results obtained by k-P H with H α and H ∩ , we can note that no heuristic outperforms the other. H α seems to perform better on the category B W CSP while H α obtains better results on B H and B M N . The results for B CSP depend on the desired percentage of retained hyperedges. Indeed, H ∩ turns to be more relevant when this percentage exceeds 90%.

Finally, we consider the runtime of k-P H. Table 4 provides the minimum and maximum runtime, the average runtime and the standard deviation for the runtime of k-P H for H α and H ∩ . Clearly, we can observe that H α and H ∩ lead to the same behavior with respect the runtime. Indeed, on each category, the runtimes are very close. Moreover, whatever the heuristic, applying k-P H requires very little time. In our experiments, the runtime does not exceed 3 minutes. Note that this runtime is reached for a hypergraph from B W CSP having 500 vertices and 120,792 hyperedges and explains why the standard deviation for B W CSP is larger than that of the other categories. Finally, it can be noted that, for 99.6% of the considered hypergraphs, the runtime does not exceed 1 second. So our approach is very efficient.

Percentage

# instances of retained In this part, we evaluate the behavior of k-P H when we do not make an assumption on the value of the treewidth of the considered instance. This makes sense from a practical viewpoint because it is not always possible to compute it for a matter of time, depending on the size of the instances. At this aim, we assess the behavior of k-P H on the whole benchmark B all by varying the value of k as a percentage of the number n of vertices. For each considered category, Figures 45678present, for each heuristic, the percentage of instances for which k-P H retains a given percentage of hyperedges when k varies from 5% to 100% of the number of vertices in steps of 5%. Figure 9 does the same for the whole benchmark. Whatever the considered category, we can observe that k-P H behaves similarly with H α and H ∩ . However, we can note that for a given k, k-P H with H ∩ often turns out to be able to retain a few more hyperedges than k-P H with H α . This trend is clearly visible for the category B M C and less marked for the other categories.

B CSP B W CSP B H B M C B M N B all hyperedges H α H ∩ H α H ∩ H α H ∩ H α H ∩ H α H ∩ H α H ∩ = 100%
Regarding the runtime of k-P H, again the heuristics H α and H ∩ lead to similar results. Processing any hypergraph from B H or B M C requires less than one second whatever the heuristic we consider. Likewise, about 99% (resp. 97%) of hypergraphs of B CSP (resp. B W CSP ) are processed in less than one second. Processing a hypergraph among the remaining ones of B CSP (resp. B W CSP ) require at most 154 seconds (resp. 205 seconds). These runtimes are reached for the largest hypergraphs in terms of number of hyperedges. The trend is different for B M N . Indeed, applying k-P H requires less than one second for a percentage of hypergraphs varying between 68% and 95% depending on the value of k. For the remaining hypergraphs, the runtime is generally about 30 seconds and rarely exceeds 4 minutes. Again, this concerns the largest hypergraphs in terms of number of hyperedges.

Conclusion

In this paper, we have proposed an algorithm called k-P H which calculates for a given hypergraph and a given constant k, a partial hypergraph for which the width of its 2-section is at most k -1. We have also shown that k-P H allows constructing an optimal partial hypergraph in the sense that all the hyperedges are selected for the case of α-acyclic hypergraphs. To assess the efficiency of k-P H with respect to the optimality criterion related to the maximum number of selected hyperedges, we performed experiments on a large benchmark including 11,302 instances from several communities. These experiments show for example that for about 90% of the instances, more than 70% of the hyperedges are retained in the calculated partial hypergraph when the value of k is equal to the treewidth plus one of the instances while runtimes being limited in practice. Moreover, this algorithm can easily be adapted according to the considered objective of selection of hyperedges. Indeed, one can thus add to it different heuristics which make it possible, for example, to take into account weights for hyperedge to be selected in the partial hypergraph. This should make it easier to process different types of graphical models. To conclude, the interest of this algorithm must now be evaluated for the treatment of graphical models. • e is the number of hyperedges in E;

• d is the maximum degree among all the vertices in H (the degree d(v) of a vertex v is the number of hyperedges in E containing v);

• r is the rank of the hypergraph, that is the maximum size of the hyperedges in E;

• N is the number of bags in the computed tree-decomposition.

A.1 Data structures

We present the different data structures required to run the algorithms. These data structures which were not described in the previous section are used by k-P H in order to improve its complexity. They are updated in particular when calculating the connected components, also for reasons of complexity. Before, note that the size of an input is in Θ(n + e + Σ Ei∈E |E i |) which can be simplified by Θ(n + Σ Ei∈E |E i |).

(1) To represent and manage hypergraphs, we use arrays:

• One is indexed by the set of hyperedges E. For a given hyperedge E i , it represents the list of the vertices included in E i . Its size and the cost of its initialization are in Θ(e + Σ Ei∈E |E i |).

• Another one is indexed by the set of vertices V . For a given vertex v, it represents the list of the hyperedges containing v. Its size and the cost of its initialization are in Θ(n + Σ Ei∈E |E i |).

• To represent a partial hypergraph H ′ = (V, E ′ ) of H = (V, E), we only need an array of Booleans indexed on the set E of hyperedges which specifies the edges belonging to E ′ . Its size and the cost of its initialization are in Θ(e).

(2) An array B memorizes the set B of bags associated to the computed tree-decomposition. It is an array of lists indexed by its rank during the computation. Each list represents the set of vertices of the corresponding bag. As the number of bags is at most n (necessarily, we have N ≤ n), the cost of its initialization is in Θ(n) and its size is in Θ(n + Σ Bi∈B |B i |) which is exactly the size of the result of k-P H.

(3) Throughout the execution, we manage a queue Q memorizing the connected components. So Q can express as a list of connected component X ij , that is a list of sets. The size of such a data structure is bounded by the number of vertices since it is a partition of a subset of the vertices of the hypergraph. The cost of its initialization is in Θ(1) while at some point of the computation, its size is in O(n).

(4) Once B i has been calculated, for the calculation of the associated connected components, we will use a marking table. This array, called status[], is indexed by the set V of vertices. For a given vertex v, we have:

• status[v] = -1 if the vertex v belongs to a built bag,

• status[v] = j if the vertex v has been processed when computing the connected components of H ′ for the j-th time,

• status[v] = 0 if the vertex v has never been considered.

The cost of its initialization and its size are in Θ(n).

(5) For the computation of bags, we use several data structures that allow to improve the efficiency of k-P H. These data structures will be assigned after the computation of a new bag B i , during the computation of the new connected components X ij :

• A set of candidate hyperedges associated to each new connected component X ij . It is a list of hyperedges denoted S ij . So, the data structure S is a list of lists of hyperedges. The cost of the initialization for S, for one S i (and thus for one S ij ) is feasible in constant time, i.e. in Θ(1). Note that in the description of the algorithm k-P H, when a set X i is removed from the queue Q to compute a new bag B i , such a list S ij is denoted S i .

• For a new connected components X ij which will be considered later to find a future bag, we memorize the possible potential parent bags (to connect it to the future new bag in the resulting tree-decomposition). These are bags B ℓ already calculated (i.e. such that 1 ≤ l ≤ i) and such that there exists a hyperedge intersecting simultaneously X ij and B ℓ . Such bags will be represented in a list denoted P ij . So, we need a data structure P which is a list of lists of bags, and, the cost of the initialization for P , for one P i (and thus for one P ij ) is feasible in constant time, i.e. in Θ [START_REF] Schiex | Valued Constraint Satisfaction Problems: hard and easy problems[END_REF].

inserted in a stack called Sta and initializations are realized (lines 8-10). At the same time, x is marked as visited for the current call to Comp-CC (line 11). From there, the connected component X ix is computed starting from vertex x (lines 13-27). To do this, we first select an untreated vertex y in Sta and remove it from Sta (line 14). From this vertex, all hyperedges E j containing y must be considered (note that the considered hyperedges E j are those of which a part appears in the expanded subhypergraph H ′ [[X i \ B i ]]). First, if all the vertices of E j which belong to a computed bag appears in B i , it means that E j is necessarily connected to B i (lines [START_REF] De Givry | Exploiting Tree Decomposition and Soft Local Consistency in Weighted CSP[END_REF][START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF]. Afterwards, these hyperedges are exploited by determining the already computed bags that intersect E j because the latter are potential parents of the bag that will be constructed from X ix (lines [START_REF] Hirata | On Finding Acyclic Subhypergraphs[END_REF][START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF]. Then, the vertices z of each E j hyperedge are processed depending on their status (lines 20-27). If the vertex z belongs to an already constructed bag (1 ≤ status[z] ≤ i), the hyperedges containing it must then be selected (lines 21-22) because they will be candidate hyperedges for the future construction of a bag from X ix . Otherwise, if z has never been reached during the current call (i.e. 0 ≤ status[z] < i), z is added both to the stack and the component X ix and is marked as visited for the current called (lines 24-27). In another case, i.e. if status[z] = num, the processing concerning z has already been carried out and so of course there is nothing else to do. Each descent into the hypergraph continues until the stack is empty. Once the stack is empty, X ix contains a new connected component that will be added to CC, and the process can continue until all the vertices of X i have been reached. Finally the related data structures are adequately updated (lines [START_REF] Hajnal | Uber die Auflosung von Graphen in vollstandige Teilgraphen[END_REF][START_REF] Dirac | On rigid circuit graphs[END_REF][START_REF] Fulkerson | Incidence matrices and interval graphs[END_REF][START_REF] Berge | Graphes et Hypergraphes[END_REF][START_REF] Fagin | Degrees of Acyclicity for Hypergraphs and Relational Database Schemes[END_REF]. Note that, in some particular cases, P ix and S ix are empty at the end of loop of lines 6-27. This occurs when the new connected component X ix cannot be linked to an existing bag (e.g. for the first call to Comp CC). When this phenomenon happens for another call than the first one, it means that H ′ has several connected components. In such a case, we consider for S ix all the hyperedges which are included in X ix (lines 28-29).

Remark that by marking a vertex as visited by setting its status to the value of i, we avoid resetting status at each called of Comp CC.

Algorithm 2: Comp-CC

Input: Rank i of the current call, a hypergraph H ′ = (V, E ′ ), a set of vertices X i , a bag B i , an array of bags Bag list, an array status, a set of sets of hyperedges S, a set of sets of parents bags P Output: A set of connected components CC, a set of sets of hyperedges S, a set of sets of parents bags P

1 CC ← ∅ 2 P i ← ∅ 3 S i ← ∅ 4 for x ∈ B i do 5 status[x] = -1 6 for x ∈ X i do 7 if 0 ≤ status[x] < i then 8 Sta ← {x} 9 P ix ← ∅ 10 S ix ← ∅ 11 status[x] ← i 12 X ix ← {x} 13 while Sta ̸ = ∅ do 14 Select y from Sta and remove it 15 for E j ∈ E ′ | y ∈ E j do 16 if {z ∈ E j |status[z] = -1} ⊆ B i then 17 Bag list[E j ] ← B i 18 for bag ∈ Bag list[E j ] do 19 P ix ← P ix ∪ {bag} 20 for z ∈ E j \ {y} do 21 if status[z] = -1 then 22 S ix ← S ix ∪ {E j } 23 else 24 if status[z] < i then 25 Add z to Sta 26 status[z] = i 27 X ix ← X ix ∪ {z} 28 if P ix = ∅ then 29 S ix ← {E j ∈ E ′ |E j ⊆ X ix } 30 P i ← P i ∪ {P ix } 31 S i ← S i ∪ {S ix } 32 CC ← CC ∪ {X ix } 33 return CC Proposition 1. The time complexity of Comp-CC for a bag B i is in O(|X i | • d • n).
Proof: The initialization phase for the data structures (lines 1 to 3) can be done in constant time while the update of status is achieved in O(|B i |). There will be exactly |X i | passes in the for loop (lines 6-27) and thus, the test of line 7 will be realized |X i | times. However, the number of times the test is true will be exactly equal to the number of connected components, i.e. |CC| times. The initializations of lines 8-12 can be carried out in constant time. Overall, they will be realized |CC| times. As all the vertices of X i will be processed, and at most once, there will be globally less than |X i | passes in the while loop (because of the vertices in B i ). In fact, there will be exactly as many passes globally in this loop as there will be vertices in the new computed connected components, namely precisely | X ix | < |X i |. For a given vertex y, the loop of line 15 is performed at most d(y) times, i.e. the number of hyperedges to which it belongs in H. This number can be bounded by d. For one pass in this loop: • The processing of line 18 is possible in constant time (this is possible by using an array of Booleans for the temporary management of this step with a global cost in Θ(n) for Comp-CC), the cost of lines 18 and 19 is of the order of |Bag list[E j ]|, i.e. less than N .

• For one vertex y, there are exactly |E j |-1 entries through the loop of line 20, which is bounded by r because for all E j ∈ E, we have |E j | ≤ r. For a given vertex z, the processing performed in lines 21-27 can be done in constant time (for S ix as for P ix , this is possible by using an array of Booleans for the temporary management of this step with a global cost in Θ(n) for Comp-CC).

Summarizing, this means that for a given vertex y, the cost of lines 15- We can now assess the complexity of k-P H. For this, we assume that the cost of the considered heuristic H is h. Proof: First of all, it is obvious that the cost of initializing the data structures is lower than the total cost of the algorithm. The while loop is performed at most N times, the number of bags in the resulting tree-decomposition. Each time there is a pass through this loop, a new bag is calculated, and the cost of the calculation of a new bag in exactly Θ(h). Note that the Bag list[] update does not appear in k-P H. This can be done just after the computation of the bag B i and the cost of this update is achievable in O(k • d • N ). We know that the cost of updating To give an illustration of this complexity, we now propose an evaluation of the complexity of the heuristic H α considered for Theorem 3. This one first chooses a bag B ℓ with the largest intersection with N i and then, chooses as the first new hyperedge to be in B i a hyperedge that shares the maximum number of vertices with B ℓ . The other hyperedges to be added to B i are chosen in descending order of the size of their intersection with B ℓ . This processing takes as inputs a connected component X i , the set of candidate hyperedges S i (a list stored in S), and the list of bags P i (a list stored in P ) already calculated and which can connect the new bag to one already obtained. So, we analyze first, the selection of B ℓ , then the computation of B i :

• Selection of B ℓ .
-The first step is to calculate the set N i . This is possible by browsing S i , and inserting in N i , for each hyperedge E j , the vertices that are not in X i . Note that X i is represented by a list, but for efficiency, we can also represent X i by an array of Booleans indexed by the vertices. At the initialization step of k-P H, this array is initialized to zero and when processing a new set X i , just assign its elements to 1. Once the calculation of B i has been performed, all corresponding elements are reset to zero. This will result in a linear cost in the size of X i . We can do the same for N i . Remember that the cost of visiting a hyperedge E j is in Θ(|E j |), and therefore in O(r). Thus, the cost of the calculation of

N i is O(|X i | + |S i | • r).
-The calculation of B ℓ is performed using N i and P i . To do this, we have to consider each element of P i , i.e., all the bags already calculated that are candidates. For each bag, its elements present in N i are counted. As the size of the bags is at most k, the complexity is O(|P i | • k).

To summarize, the time complexity of the calculation of B ℓ is therefore

O(|X i | + |S i | • r + |P i | • k).
• Computation of B i . All the hyperedges in S i must be visited and for each one, the size of its intersection with B ℓ is computed. To do this, we can proceed as above, using an array of Booleans initialized to 1 for all the elements of B ℓ . Then for each hyperedge, we consider the size of its intersection with B ℓ . Moreover, we can order the hyperedges of S i according to the size of this intersection. To carry out this sorting, it is possible to have a data structure which would proceed by addressing in an array of size r and whose each entry would contain a list memorizing the hyperedges of the corresponding size. We just have to visit the set of ordered hyperedges and check which ones can be added to B i . This treatment can be done in O(|S i | • r) since all the hyperedges in S i will be examined and the cost of treatment of a hyperedge is linear in its size, that is to say in O(r). Note that at the end of this treatment, if a vertex v belongs to this new bag B i , the value i is assigned to status[v]. ). This expression can be rephrased if we consider certain upper bounds. Indeed, we know that N ≤ n, we thus obtain the complexity O(n(n

• k + e • r + n • d(n + r))) = O(n • n • k + n • e • r + n • n • d • n + n • n • d • r) = O(n 2 • k + n • e • r + n 3 • d + n 2 • d • r) = O(n 2 • (k + n • d + r • d) + n • e • r)
. On the other hand, if we also consider that the width k -1 is a constant, and therefore that the treatments will only consider hyperedges whose size is less than or equal to k, this complexity can be reduced to O(n 3 • d + n • e).

  an integer M ≤ |E| and an integer k ≤ |V |. QUESTION: Does H have a partial hypergraph with M hyperedges whose treewidth is at most k -1?

  MAXIMAL PARTIAL HYPERGRAPH OF BOUNDED WIDTH INSTANCE:A hypergraph H = (V, E) and an integer k ≤ |V |. QUESTION: Find a maximal partial hypergraph of H whose treewidth is at most k -1.

25

  For each vertex v that does not appear in any bag from B, add the bag {v} hypergraph H ′ , a set of vertices X and another set of vertices Y . Comp-CC returns the set of connected components of the expanded subhypergraph of H ′ induced by X\Y , i.e. H[[X\Y ]]. These components are then inserted into the queue Q (line 5).

Figure 1 :

 1 Figure 1: Beginning of a new bag building stage with the representation of the sets∪ 1≤j≤i-1 B j , N i , X i and N H ′ (N i , X i ). 4 hyperedges

Figure 3 :

 3 Figure 3: Illustration of how k-P H works on two possible instances: a graph with k = 2 (a) and a hypergraph with k = 5 (b).

  [START_REF] Jégou | Hybrid backtracking bounded by tree-decomposition of constraint networks[END_REF] and S 2 = {E 4 } (line 16). It ensues that we have necessarily B l = B 1 . Only the edge E 4 (of class 2) is then considered and we have B 2 = E 4 . No edge is added to B 2 in line 20, nor deleted from H ′ in line 21. At this point, no new connected component is found by Comp-CC and therefore, nothing will be added in Q. In the next step, X 3 = {x 4 , x 5 } is removed from Q. Line 9 computes N 3 = {x 1 }, and then line 14 is executed. We obtain N H ′ (N 3 , X 3 ) = {x 4 , x 5 } (line 15), and then S 3 = {E 2 , E 3 , E 5 } (line 16) where E 2 and E 3 are of class 2 and E 5 of class 3. So, only E 2 or E 3 can be chosen in line 19. Assume that E 2 is chosen and therefore B 3 = {x 1 , x 4 }. No edge is added to B 2 in line 20, nor deleted from H ′ in line 21. The call of Comp-CC on line 23 calculates a new connected component {x 5 } which is then inserted in Q. The while loop therefore continues with X 4 = {x 5 }, then line 9 calculates N 4 = {x 1 , x 4 }. Again line 14 is executed. Line 15 calculates N H ′ (N 4 , X 4 ) = {E 3 , E 5 }, then line 16 obtains S 4 = {E 3 , E 5 }. There are then two possibilities for B ℓ , either

4. 4

 4 Behavior of k-P H Depending on the Value of k

Figure 4 :

 4 Figure 4: Percentage of instances for a given percentage of retained hyperedges when k is defined as a percentage of n for H α (a) and H ∩ (b) (benchmark B CSP ).

Figure 5 :Figure 6 :

 56 Figure 5: Percentage of instances for a given percentage of retained hyperedges when k is defined as a percentage of n for H α (a) and H ∩ (b) (benchmark B W CSP ).

Figure 7 :

 7 Figure 7: Percentage of instances for a given percentage of retained hyperedges when k is defined as a percentage of n for H α (a) and H ∩ (b) (benchmark B M C ).

8 :

 8 Percentage of instances for a given percentage of retained hyperedges when k is defined as a percentage of n for H α (a) and H ∩ (b) (benchmark B M N ).

Figure 9 :

 9 Figure 9: Percentage of instances for a given percentage of retained hyperedges when k is defined as a percentage of n for H α (a) and H ∩ (b) (benchmark B all ).

•

  Lines 16-17 can be achieved in O(|E j | • |B i |), and so in O(r • k) since we have |E j | ≤ r and |B i | ≤ k.

2 A. 4

 24 27 is at most by O(d • (N + r • k)) (N.B.: lines 18-19 can be replaced by a single line like P ix ← P ix ∪ Bag list[E j ]). As globally, we will have less than |X i | vertices y to process, the global cost of lines 13-27 is thus bounded by O(|X i | • d • (N + r • k)). Finally, performing lines 30-32 is feasible in constant time. So, their overall cost is in O(|CC|). Thus we have O(|X i | • d • (N + r • k) + |CC| + |X i |), and as necessarily we have |CC| ≤ |X i |, the complexity of Comp-CC for a B i bag is thus O(|X i | • d • (N + r • k)). We have N ≤ n and r ≤ k. So, as k is a constant, we obtain a complexity in O(|X i | • d • n). Complexity of k-P H

Theorem 2 (

 2 proof ). The time complexity of k-P H is in O(N (h + e • r + n • d(N + r))).

  H ′ is O(|S i | • r) with |S i | ≤ e and that, for a new bag B i , the cost of a Comp-CC call is O(|X i | • d • (N + r)). Since the size of X i is bounded by n, the cost for each Comp-CC is actually O(n • d(N + r)). Such a size for X i may occur if the 2-section of the input hypergraph is a (k+1)-tree, formed by a single path. Thus, at each pass, the new connected component will contain all the vertices not yet included in a bag, and there will be only one vertex less in the next connected component. Finally, the total cost of k-P H is therefore O(N (h + e • r + n • d(N + r))). 2

Thus, the cost

  of executing this heuristic is O(|X i | + |S i | • r + |P i | • k). Knowing that |X i | ≤ n, |S i | ≤ e and |P i | ≤ n, one can thus bound the cost of this heuristic by O(n + e • r + n • k) = O(n • k + e • r).This gives an illustration of the time complexity of k-P H by specifyingO(N (h + e • r + n • d(N + r))) = O(N (n • k + e • r + n • d(N + r))

  that has already been numbered. When y has been numbered, necessarily, it had to form a clique containing both x, but also, all the vertices of Sep not yet numbered, including the last vertex of Sep that has been numbered. This leads to a contradiction because x should then have at least one neighbor in Sep not numbered, or x was not numbered before all the vertices of Sep were numbered.

If this vertex x has a neighbor y in Sep not yet numbered, then this vertex of Sep is linked to all vertices of N i because x is the first vertex of N i numbered, and the vertices of N i with y thus constitute a clique. Otherwise, suppose all the neighbors of x in Sep are already numbered. Consider y ∈ Sep, a neighbor of x

  By construction of X ij , x and y necessarily appear in a separator of X ij , and more precisely, in a minimal separator of X ij because of the existence of the edges {x, u} and {y, v}. But since 2 SEC (H ′ [B ℓ ∪ X i ] + B ℓ ) is chordal, and any minimal separator in a chordal graph is a clique, necessarily, x and y are neighbors in that graph, and the edge {x, y} has not been added by completion of B i , and therefore cannot have created a new cycle without a chord in 2 SEC

  ′ [B i ∪ X ij ] + B i . By reasoning like for the proof of the chordality of 2 SEC (H ′ [B i ∪ X ij ] + B i ), we show that the edge {x, y} was not added by completion of B i (addition of all possible edges), because here again, due to the presence of the edges {x, z} and {y, z}, x and y are necessarily in a minimal separator of X ij and thus are already connected. Thus, as x, y and z already constitute a clique appearing in 2 SEC (H ′ [B ℓ ∪ X i ] + B ℓ ) and that the hypergraph H ′ [B ℓ ∪ X i ] + B ℓ was conformal before completion of B i , there is a hyperedge of H ′ [B i ∪ X ij ] + B i which covers this clique.

was the case before the computation of B i as H ′ [B ℓ ∪ X i ] + B ℓ is by hypothesis α-acyclic and thus conformal, and that no edge has been added in

2 SEC (H ′ [B i ∪ X ij ] + B i ) between vertices of X ij .

The only cliques that may appear when creating the B i hyperedge are therefore overlapping B i and X ij , and must therefore concern at least 3 vertices, two vertices x and y of B i initially non-neighboring, and a vertex z of X ij such that {x, z} and {y, z} appear in 2 SEC (H ′ [B ℓ ∪ X i ] + B ℓ ). It is thus necessary to prove that x, y and z are covered by a hyperedge of H

Table 3 :

 3 Number of hypergraphs depending on the percentage of hyperedges retained by k-P H for H α and H ∩ when k is equal to the treewidth of the considered hypergraph plus one.

		373	373	125	118	841	902	0	0	71	71	1,410 1,464
	≥ 95%	1,512 1,524	329	308	890	975	0	0 215 225	2,946 3,032
	≥ 90%	2,345 2,440	861	736	1,092 1,215	0	0 256 280	4,554 4,671
	≥ 85% 3,513	3,455 1,269 1,122	1,453 1,534	2	0 313 342	6,550	6,453
	≥ 80% 4,715	4,527 1,382 1,330	1,969 2,009	23	6 375 381	8,464	8,253
	≥ 75% 5,249	5,243 1,412 1,389	2,297 2,331 175 142 385 388	9,518	9,493
	≥ 70% 5,450	5,449 1,454 1,413	2,469 2,471 489 499 388 389 10,250 10,221
	≥ 65% 5,606	5,591 1,484 1,426	2,545 2,558 511 511 388 389 10,534 10,475
	≥ 60% 5,820	5,762 1,506 1,431 2,685	2,681 511 511 388 389 10,910 10,774
	≥ 55% 5,889	5,847 1,526 1,451 2,762	2,757 511 511 389 389 11,077 10,955
	≥ 50% 5,962	5,928 1,535 1,486 2,819	2,796 511 511 389 389 11,216 11,110

Table 4 :

 4 Minimum and maximum runtime, average runtime and standard deviation for the runtime of k-P H for H α and H ∩ when k is equal to the treewidth of the considered hypergraph plus one.

Usually, a connected component in a graph is defined as the subgraph induced by the vertices that compose it. Here, for the case of hypergraphs, we assimilate a connected component to the set of vertices that compose it because this simplifies the notations without reducing their precision.

A detailed description of this algorithm is given in Appendix A. Although the calculation of the connected components in a hypergraph is very simple, we prefer to describe this algorithm because Comp-CC also maintains data structures allowing to ensure the efficiency of k-P H.

github.com/TCS-Meiji/PACE2017-TrackA

http://www.CSP.org/series

http://genoweb.toulouse.inra.fr/ ~degivry/evalgm

http://carlit.toulouse.inra.fr/SoftCSP/Files/cflibtars/ergo.tgz

https://miat.inrae.fr/toulbar2/

hyperbench.dbai.tuwien.ac.at

https://www.cs.rochester.edu/u/kautz/Cachet/Model_Counting_Benchmarks/index.htm

https://www.cs.huji.ac.il/project/PASCAL/

Acknowledgement

This work has been funded by the Agence Nationale de la Recherche project ANR-16-CE40-0028.

Appendix A -Complexity of k-P H

The time complexity of k-P H cannot be evaluated without knowing in details the cost of the different internal treatments such as Comp-CC, the computing of a new bag B i , the computing of the sets N i , N H ′ (N i , X i ) and S i , the cost of the heuristic H, and also, the cost of updating H ′ . In order to make these different treatments efficient, several data structures must be implemented and these must be detailed. Thus, after their description and the time evaluation of these treatments, we evaluate the time complexity of k-P H. Before that, we recall some notations:

• n is the number of vertices in V ;

• An array of lists called Bag lists represents the connections between hyperedges and bags: this array is indexed by the hyperedges E i , and for a given E i , the associated list contains all the bags B j such that B j ∩ E i ̸ = ∅. The cost of the initialization of Bag lists is feasible in Θ(e) and its size is in O(e • N ).

A.2 Implementation and Time Complexity Analysis

We can now analyze the complexity of k-P H. To do so, we must analyze each of its different steps, that is computation of a new bag B i , update of H ′ , and the computation of new connected components. In k-P H, the computation of a new bag is realized using a heuristic H. Since different heuristics can be considered, we assume that its time complexity is in O(h). Note however that, whatever the heuristic considered, if a vertex v belongs to a new bag B i , status[v] takes the value -1.

After the evaluation of the complexity of k-P H, we assess the time complexity of the heuristic considered in Theorem 3 as an illustration.

Update of H ′

Once B i is calculated, H ′ has to be updated by removing hyperedges

To find such edges E j , we simply browse S i , and select the hyperedges which satisfy these two conditions:

contain at least one vertex x of X i that belongs both to B i and E j : such a vertex verifies status[x] = -1;

The complexity is thus related to the size of S i , and to the cost to visit each E j . So, the cost is in O(|S i | • r) because the size |E j | of the hyperedges is at most m. Finally, each hyperedge can be removed from H ′ in constant time using the array representing this partial hypergraph.

A.3 Calculation of Connected Components

In this part, we describe the algorithm Comp-CC. This algorithm computes, in a classical way, the connected components X ij deduced from B i in X i . However, at the same time, for efficiency reasons, it also computes the sets S ij of the candidate hyperedges for the construction of the future bags, and the sets P ij of the bags already found and that will be candidates to be bags connecting the future bags to those already obtained (they will then be called parent bags). That is why we give below a detailed description of this algorithm.

The Comp-CC algorithm actually considers as inputs the partial hypergraph H ′ = (V, E ′ ), the set of vertices X i , the newly created bag B i , the array status and the array of bags Bag lists. Note that the version we give here of the Comp-CC algorithm has more arguments than the one used in the k-P H algorithm. This now makes it possible to specify the implementation details needed for complexity analysis, details that had been deliberately omitted before in order to lighten the presentation of the k-P H.

As outputs (and inputs) of the algorithm, we have:

• the set of sets S, where each set S ij ∈ S is associated with the connected component X ij and such that S ij represents the candidate hyperedges for this component;

• the set of sets P , where each set P ij ∈ P is associated with the connected component X ij and such that P ij represents the candidate parent bags for this component.

This algorithm (see Algorithm 2) works in a similar way to the one that calculates the connected components in graphs, with a depth first search, except that it is adapted to the case of hypergraphs, and that it must update data structures used in our framework. Note that in the code of the algorithm, the index j will be noted x, x being the vertex from which a new descent will be made to find a new connected component.

The first step (lines 1-5) is devoted to initialize and update some data structures. Before, recall that the value of i denotes the number of times the algorithm Comp-CC has been called since the beginning of the computation of the partial hypergraph. In this step, we also update status (lines 4-5) in order to take into account the last computed bag (if any). Then a new descent in the hypergraph is performed (line 7) for each vertex x of X i which has not been reached yet during the current call to Comp-CC (i.e. status[x] < i) and which does not belong yet to a built bag (i.e. status[x] ≥ 0). It allows us to build a new connected component X ix for which x constitutes the first vertex (line 12). This vertex is