domain: info phys

text:
E Delage

Q T Pham

M Karamitros

H Payno

V Stepan

S Incerti

L Maigne

Yann Perrot
email: perrot@clermont.in2p3.fr

PDB4DNA: implementation of DNA geometry from the Protein Data Bank (PDB) description for Geant4-DNA Monte-Carlo simulations

This paper describes PDB4DNA, a new Geant4 user application, based on an independent, crossplatform, free and open source C++ library, so-called PDBlib, which enables use of atomic level description of DNA molecule in Geant4 Monte Carlo particle transport simulations. For the evaluation of direct damage induced on the DNA molecule by ionizing particles, the application makes use of an algorithm able to determine the closest atom in the DNA molecule to energy depositions. Both the PDB4DNA application and the PDBlib library are available as free and open source under the Geant4 license.

Introduction

The simulation of radiation-induced effects in living tissues requires the modeling of different action mechanisms [START_REF] Friedland | Track structures, DNA targets and radiation effects in the biophysical Monte Carlo simulation code PARTRAC[END_REF]: the physical stage describing the elementary physical interactions causing ionization and excitation of water molecules; the physico-chemical and chemical stages describing the production, the diffusion and the reaction of chemical species and the biological stage predicting radiation effects in living tissues. The modeling of physical, physico-chemical and chemical actions has to be coupled with a geometrical model describing correctly the targets at the origin of the biological endpoints. It has been demonstrated that damage to nuclear DNA are responsible for biological effects such as chromosome aberrations, mutations and cell inactivation [START_REF] Kuzin | On the role of DNA in the radiation damage of the cell[END_REF][START_REF] Goodhead | Effects of radiations of different qualities on cells: molecular mechanisms of damage and repair[END_REF].

Consequently, the correct modeling of cell nucleus content is required in order to estimate the detailed clustering of energy deposition at this scale. Modeling the three dimensional structure of the DNA molecules is a way to describe the cell nucleus. Indeed, the precise implementation of DNA geometry is of key importance in order to take into account the spatial structure of energy depositions along the particle track generated by Monte Carlo Track Structure (MCTS) codes. However, the modeling of DNA geometries is not trivial if we keep in mind that DNA molecule for a normal human cell represents about 3.1x10 9 base pairs [START_REF] Little | Structure and function of the human genome[END_REF] geometrically arranged in many structural levels that evolve with time and may vary between cells of a same line. Among the variety of MCTS codes [START_REF] Nikjoo | Track-structure codes in radiation research[END_REF], the strategy consists in replicating and arranging an elementary piece of DNA to form structural levels.

Usually, each elementary piece of DNA is represented either by a simple geometrical shape [START_REF] Charlton | A method of calculating initial DNA strand breakage following the decay of incorporated 125I[END_REF][START_REF] Nikjoo | Energy deposition in small cylindrical targets by ultrasoft X-rays[END_REF][START_REF] Nikjoo | Energy deposition in small cylindrical targets by monoenergetic electrons[END_REF][START_REF] Bernal | An investigation on the capabilities of the PENELOPE MC code in nanodosimtery[END_REF][START_REF] Incerti | Energy deposition in small-scale targets of liquid water using the very low energy electromagnetic physics processes of the Geant4 toolkit[END_REF][START_REF] Santos | Influence of the DNA density on the number of clustered damages created by protons of different energies[END_REF] or by a piece of DNA double helix in atomic resolution [START_REF] Friedland | Track structures, DNA targets and radiation effects in the biophysical Monte Carlo simulation code PARTRAC[END_REF][START_REF] Michalik | Target model of nucleosome particle for track structure calculations and DNA damage modelling[END_REF][START_REF] Nikjoo | A model of the cell nucleus for DNA damage calculations[END_REF][START_REF] Friedland | Monte Carlo simulation of the production of short DNA fragments by low linear energy transfer radiation using higher order DNA models[END_REF][START_REF] Stepan | RADAMOL tool: Role of radiation quality and charge transfer in damage distribution along DNA oligomer[END_REF]. Historically, geometrical DNA targets were treated as small cylinders in order to compute energy depositions comparable with microdosimetry or nanodosimetry experiments [START_REF] Nikjoo | Energy deposition in small cylindrical targets by ultrasoft X-rays[END_REF][START_REF] Nikjoo | Energy deposition in small cylindrical targets by monoenergetic electrons[END_REF][START_REF] Grosswendt | The track structure of alpha particles from the point of view of ionization cluster formation in "nanometric" volumes of nitrogen particles[END_REF]. To allow the computation of DNA strand breaks, small cylinders were divided to reach the definition of DNA bases and sugar phosphate backbones [START_REF] Charlton | A method of calculating initial DNA strand breakage following the decay of incorporated 125I[END_REF]. Bernal and Liendo proposed a more structured geometrical model for DNA molecules [START_REF] Bernal | An investigation on the capabilities of the PENELOPE MC code in nanodosimtery[END_REF]. Assuming that energy depositions in sugar-phosphate groups cause DNA damage, they were represented as prisms and arranged using parametric equations to enable computations up to 1.2x10 8 base pairs. This method guaranteed the packing ratio of the B-DNA structure taken from literature [START_REF] Dickerson | The anatomy of a-, b-, and z-DNA[END_REF]. This geometrical model, first implemented to explore the capacities of the PENELOPE code to calculate DNA strand breaks [START_REF] Bernal | An investigation on the capabilities of the PENELOPE MC code in nanodosimtery[END_REF], was adapted to Geant4 to study the production of DNA strand breaks [START_REF] Incerti | Energy deposition in small-scale targets of liquid water using the very low energy electromagnetic physics processes of the Geant4 toolkit[END_REF][START_REF] Bernal | The invariance of the total direct DNA strand break yield[END_REF]. More recently, Dos Santos et al. implemented a geometrical model using Geant4 for which spheres representing bases and sugar phosphate backbone were replicated using parameterized geometrical transformations [START_REF] Santos | Influence of the DNA density on the number of clustered damages created by protons of different energies[END_REF]. Compared to the work of Bernal and Liendo, the model of Dos Santos et al. was able to describe the whole DNA content of specific human cell nuclei (endothelium and fibroblast in the G0/G1 phase) and was proposed as the so-called "dnageometry" Geant4 advanced example.

More sophisticated geometrical models where DNA is represented by detailed atomic structure can be found in the literature but are not available publicly. Michalik and Begusova defined a geometrical non-homogeneous target model of a nucleosome to be used with the TRION MCTS code [START_REF] Michalik | Target model of nucleosome particle for track structure calculations and DNA damage modelling[END_REF]. To perform this geometrical model, a linear piece of DNA was wrapped around the histone core represented by a cylinder. Nikjoo and Girard proposed geometrical models [START_REF] Nikjoo | A model of the cell nucleus for DNA damage calculations[END_REF], implemented in PHITS and KURBUC MCTS codes, for which 30 nm solenoid describing chromatin fibers are derived from a canonical B-DNA structure and are then used to fill chromosome domains to construct the complete cell genome. In a similar way, the PARTRAC (PARticle TRACks) code is able to describe the whole genome of specific human cells (fibroblast or lymphocyte in the G0/G1 phase) [START_REF] Friedland | Track structures, DNA targets and radiation effects in the biophysical Monte Carlo simulation code PARTRAC[END_REF][START_REF] Friedland | Monte Carlo simulation of the production of short DNA fragments by low linear energy transfer radiation using higher order DNA models[END_REF]. In this case, the cell genome is defined as a DNA double helix target detailed up to the atomic scale. Five straight fiber elements and four bent elements build up a random-walk fiber model on a grid of 50 nm x 50 nm. Thus, the main advantage is that chromatin fiber is defined by a flexible arrangement of nucleosomes allowing an unbroken DNA segment.

It has to be noticed that these sophisticated geometrical models are implemented in specific purpose MCTS codes that are not publicly available. Therefore, in order to provide to a large community of users advanced geometry of DNA molecules, we used in this study the general purpose Monte Carlo toolkit Geant4 [START_REF] Agostinelli | Geant4-a simulation toolkit[END_REF]. This toolkit is being extended to handle microdosimetry and radiobiology applications in the framework of the Geant4-DNA project [20] by the inclusion of detailed physics models [START_REF] Incerti | Comparison of Geant4 very low energy cross section models with experimental data in liquid water[END_REF], radiochemistry simulation [START_REF] Karamitros | Modeling Radiation Chemistry in the Geant4 Toolkit[END_REF][START_REF] Karamitros | Diffusion-controlled reactions modeling in Geant4-DNA[END_REF] and DNA geometrical models [START_REF] Santos | Influence of the DNA density on the number of clustered damages created by protons of different energies[END_REF].

Geant4 advanced features to describe, place and replicate basic geometries can be used to describe directly DNA structure.

Bernal et al. [START_REF] Bernal | An atomistic geometrical model of the B-DNA configuration for DNA-radiation interaction simulations[END_REF] proposed a formalism, based on an atomic-resolution geometrical model of the B-DNA configuration, that was tested with Geant4 but unfortunately no user example was released.

The authors suggested that "for DNA-radiation interaction simulations, a formalism and an associated code to determine the closest atom to an arbitrary point in space is needed".

The need to model, store and exchange polyatomic structures has driven the emergence of file formats enabling the publication, exchange and reuse of data. The Protein Data Bank (PDB) file format [START_REF] Bernstein | The Protein Data Bank: A Computer-based Archival File For Macromolecular Structures[END_REF] represents the molecular geometry by defining the relative position of the constituting atoms. In the PDB file format, no information relative to electronic occupancy are included. The structure can be either obtained experimentally by crystallography techniques or computed with geometry optimization codes which are often able to directly generate PDB files.

The aim of this paper is to describe a Geant4 user application called PDB4DNA that simulates energy deposition in a target volume generated from a PDB file representing the geometry of DNA molecule and estimates energy depositions in such a geometry. PDB4DNA is the first initiative, written in C++, free and open source, integrating the description of molecular geometry from PDB in Geant4 simulations in order to give an estimation of the strand breaks occurring in DNA geometry. Geometry extracted from PDB allows the implementation of the most realistic geometrical description of macromolecules in Geant4 ever performed for DNA damage.

In a first part, for clarity purpose, we present the UML diagram of the application and a description of a PDB file structure. Then, we provide details about functionalities on which the application is based. Then, we present the implementation of the molecular geometry under Geant4 and the resulting visualization by reproducing the exact position, as stored in a PDB file, of each atom represented by a sphere of Van der Waals radius. Finally, we propose an algorithm for assigning the energy deposition locations to DNA geometry at the atomic scale. This feature is used by the PDB4DNA user application to give an estimation of direct DNA damage such as single strand and double strand breaks.

PDB4DNA user application

PDB4DNA is a Geant4 application that reads any PDB file. It parses the data and uses them to create corresponding Geant4 description of the geometry, assigns energy depositions to atoms constituting DNA molecule in order to estimate direct damage such as strand breaks. Even though PDB files describe geometry for large molecules (protein, nucleic acids), we focus on DNA geometrical information for the simulation. In this work, simulations based on other types of molecules are not handled. Users can also visualize any molecule and particle tracks thanks to Geant4 visualization drivers.

Fig. 1 presents the UML diagram of the PDB4DNA Geant4 example. The group of classes in white 115 corresponds to the standard virtual classes that Geant4 users may implement. The core of the PDB4DNA application is represented by the group of classes in green. For easy distribution, all the features independent of Geant4 have been grouped into a C++ library called PDBlib, represented by the group of classes in blue. In the following sub-parts we discuss the different functionalities of this library. 120

PDB reader

The PDB reader functionality (called by the function PDBlib::load, Fig. 1) reads the molecular structure from a PDB file into Geant4. Note that the PDB reader is able to read and convert any other macro molecules into Geant4 geometry, such as proteins. In order to propose a lightweight toolkit fully integrated to a Geant4 user application, our PDB reader has been fully implemented while existing C++ libraries such as "A simple C++ PDB reader" [26], "Easy Structural Biology Template

Library" [START_REF] Loriot | ESBTL: efficient PDB parser and data structure for the structural and geometric analysis of biological macromolecules[END_REF], "OpenBabel" [START_REF] O'boyle | Open Babel: An open chemical toolbox[END_REF], were considered feature creep for a Geant4 user application. As a consequence, our Geant4 user application is ready to use without any third-party library. As shown in Fig. 2, a PDB file is an ASCII file in which each line is describing the structural information of the molecule. Each line is 80 columns wide and is terminated by an end-of-line indicator. The first six columns of every line contain a "record name". The first line holds the "HEADER" record which informs about the molecule type: either DNA or protein. Then, each polymer is described by a list of "ATOM" records; the list is terminated by a "TER" record. Every "ATOM" record holds atom symbol, chain identifier, residue number, atom coordinates and additional information. For DNA structure, chain and residue are respectively equivalent to strand and nucleotide. The activity diagram of the PDB reader is described in Fig. 3. The function is in charge of parsing the PDB file in order to collect the following information: element, chain ID, residue number and atom coordinates. This information is used to construct nested lists of geometry. The first list describes a molecule (for example a DNA strand). Each molecule is composed with a list of residues and each residue contains a list of atoms.

Geant4 geometry and visualization

In this part, we present the rendering of the PDB4DNA application applied to the "1ZBB PDB" file

[29]. This file describes a tetranucleosome [START_REF] Schalch | X-ray structure of a tetranucleosome and its implications for the chromatine fibre[END_REF], a short complex of four nucleosomes. It has been selected for our application because it describes the largest DNA structure available in PDB format.

The PDB4DNA application translates into Geant4 geometry the structure of the molecule only for visualization purposes by considering shapes, spatial transformations, materials and visualization attributes for each atom composing the molecule. We propose three different renderings using basic shapes like spheres and cylinders to model three different atomistic levels:

-The first rendering represents spheres centered on nucleotide barycenters (Fig. 4-a). The calculation of nucleotide barycenters (PDBlib::computeNucleotideBarycenters, Fig. 1) is also used to find the atoms nearest to each energy deposition (see Section 3.2).

-The second rendering proposes an atomistic view (Fig. 4-b). Spheres with Van der Waals radii are used to draw each atom. Corey-Pauling-Koltun (CPK) coloring convention is used to distinguish the different chemical elements.

-The third rendering provides a representation of nucleotides (group of atoms composed of sugar, phosphate and base) using spheres centered on barycenters of nucleotides. Each nucleotide is linked 165 with a cylinder (Fig. 4-c).

Simulation

Physics and geometry 170

PDB4DNA makes use of the Geant4-DNA physics list adapted to micro and nanodosimetry simulations [START_REF] Incerti | Comparison of Geant4 very low energy cross section models with experimental data in liquid water[END_REF]. Geant4-DNA processes extend the Geant4 electromagnetic physics for electrons, hydrogen and helium atoms (including charge states) and few ions, in liquid water down to very low energies. All interactions are explicitly simulated and energy deposition patterns are described down to the nanometer scale. Since the Geant4-DNA toolkit does not yet propose cross sections for DNA compounds, simulations of particle tracks are performed in liquid water. The resulting energy depositions are then allocated to groups of atoms constituting the DNA molecule (section 3.2). To that purpose Geant4-DNA simulations are run inside a bounding box of liquid water having dimensions corresponding to the DNA molecule dimensions (PDBlib::computeBoundingVolumeParams, Fig. 1).

Particles are generated from the box edges and randomly directed towards the box. Taking into account the effects of water radiolysis will be possible thanks to the integration of a specific module for radiation chemistry of Geant4-DNA integrated into the Geant4 10.1 release [START_REF] Karamitros | Modeling Radiation Chemistry in the Geant4 Toolkit[END_REF][START_REF] Karamitros | Diffusion-controlled reactions modeling in Geant4-DNA[END_REF]. Our tracking approach is fully compatible since the production, diffusion and reaction of chemical species will be performed in a continuous medium made of liquid water.

Algorithm for finding the closest atom to energy depositions

Fig. 5 presents the activity diagram of the algorithm in charge of finding the closest atom to each energy deposition (PDBlib::computeMatchEdepDNA, Fig. 1). This algorithm has been optimized for DNA molecule and is not proposed for other stereochemistry conformation. First, the algorithm tries to allocate the energy deposition to a sphere bounding a nucleotide. The center of a bounding sphere is computed as the geometrical barycenter of a nucleotide. The radius is the maximum distance between the barycenter and atom coordinates constituting the nucleotide including the maximum Van der Waals radius (1.8 Angstrom for phosphor element). If an energy deposition is allocated to a bounding sphere, a second process checks Van der Waals radii to find the atom constituting the corresponding nucleotide nearest to the energy deposition. As nucleotide bounding spheres overlap, the two closest nucleotides are included in the algorithm. When a match is found, the algorithm returns the energy deposition, the DNA strand, the nucleotide identifier and the group identifier (base, phosphate or sugar group).

Conclusion

The present paper highlights the functionalities of PDB4DNA, a new Geant4 user application dedicated to the estimation of direct DNA damage. PDB4DNA, based on the independent, crossplatform, free and open source C++ library PDBlib, is able to translate any PDB description of molecules into a Geant4 geometry down to the atomic level. In addition of visualization features, the originality of PDB4DNA application comes from its ability to allocate very accurately each energy deposition to individual atom in the molecule during particle tracks. Then, results are automatically stored in a ROOT output file for further analysis by users. For the moment, calculations of energy depositions in DNA geometry are available for liquid water medium as cross sections for DNA material are not yet available in Geant4-DNA. In a near future, it is expected to enrich this application with the simulation of indirect effects through the developments proposed by the radiochemistry working-group of the Geant4-DNA collaboration. Effectively, one can assume that the algorithm proposed to search the nearest atom from particle energy deposition will be compliant with the evaluation of indirect effects produced by the diffusion of radiolysis products and their mutual interactions in a continuous water medium. Even though we demonstrate in this work our ability to easily model a simple DNA geometry (a dinucleosome) in order to calculate resultant energy depositions, we expect to propose in a future paper the modeling of a complete chromatin fiber using combinations of nucleosome geometries. In addition to SSB and DSB computation, the estimation of DNA fragment spectra is planned.

Fig. 1 :

 1 Fig.1: UML diagram of the PDB4DNA Geant4 user application: Geant4 virtual classes (white), Geant4 implemented classes (green), PDB library (purple) and interface to ROOT analysis software (red).

Fig. 2 :

 2 Fig. 2 : PDB file format description. This format provides atom coordinates for each nucleotide number (dark blue, light blue, purple, yellow) constituting each DNA strand (red and green).

Fig. 3 :

 3 Fig. 3 : Activity diagram of the PDB reader. It reads any PDB file and converts it into Geant4 geometry.

Fig. 4 :

 4 Fig. 4 : Rendering of a dinucleosome using the PDB4DNA application: a) spheres centered on nucleotide barycenters b) atomistic view and c) spheres centered on barycenters of nucleotides.

Fig. 5 :

 5 Fig. 5 : Activity diagram of the algorithm for searching the closest atom to energy deposition. This algorithm is optimized for DNA molecules and is not adapted for any other type of molecules.

3. 3 .Fig. 6 :Fig. 7 :

 367 Fig. 6 : Activity diagram of the algorithm converting energy depositions into DNA strand breaks.

FiguresFig. 1 :

 1 Figures

Fig. 2 :

 2 Fig. 2 : PDB file format description. This format provides atom coordinates for each nucleotide

Fig. 3 :Fig. 4 :

 34 Fig. 3 : Activity diagram of the PDB reader. It reads any PDB file and converts it into Geant4

Fig. 5 :

 5 Fig. 5 : Activity diagram of the algorithm for searching the closest atom to energy deposition. This

Fig. 6 :

 6 Fig. 6 : Activity diagram of the algorithm converting energy depositions into DNA strand breaks.

Fig. 7 :

 7 Fig. 7 : a) Simulation of the irradiation of a dinucleosome (1ZBB PDB file) with monoenergetic

Acknowledgements

This work was partially supported by grants from Plan Cancer 2009-2013 French national initiative through the call for proposals "Domaine de la physique, des mathématiques ou des sciences de l'ingénieur appliqués au Cancer" managed by INSERM (Institut National de la Santé et de la Recherche Médicale) under contract PC201320.

Authors wish to thank the Geant4-DNA collaboration for its technical support, Michel Maire (Geant4 Associates International) for his advice concerning geometry transformations in Geant4, and Jean Orloff (Laboratoire de Physique Corpusculaire, Clermont-Ferrand) for his help concerning 3D rotation implementation.


Maël Minot
email: mael.minot@liris.cnrs.fr

Samba Ndojh Ndiaye
email: samba-ndojh.ndiaye@liris.cnrs.fr

Christine Solnon
email: christine.solnon@liris.cnrs.fr

A Comparison of Decomposition Methods for the Maximum Common Subgraph Problem

Keywords: Maximum Common Subgraph, Constraint Programming, Decomposition, Graph Triangulation

The maximum common subgraph problem is an N P-hard problem which is very difficult to solve with exact approaches. To speed up the solution process, we may decompose it into independent subproblems which are solved in parallel. We describe a new decomposition method which exploits the structure of the problem to decompose it. We compare this structural decomposition with domain-based decompositions, which basically split variable domains. Experimental results show us that the structural decomposition leads to better speedups on two classes of instances, and to worse speedups on one class of instances.

I. INTRODUCTION

Searching for a maximum common subgraph has many applications, for example, in chemoinformatics, bioinformatics, or image processing where it gives a measure of the similarity between objects represented by graphs. However, this problem is N P-hard and very challenging. To speed up the solution process, we may decompose the problem into independent subproblems which are solved in parallel, as proposed, for example, in [START_REF] Mccreesh | The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound[END_REF], [START_REF] Depolli | Exact parallel maximum clique algorithm for general and protein graphs[END_REF], [START_REF] Mccreesh | Multi-threading a state-of-theart maximum clique algorithm[END_REF] for the maximum clique problem, or in [START_REF] Régin | Embarrassingly parallel search[END_REF], [START_REF] Régin | Improvement of the embarrassingly parallel search for data centers[END_REF] for constraint satisfaction problems. In most cases, the decomposition is done by splitting variable domains. In order to balance the workload on the workers, EPS ( [START_REF] Régin | Embarrassingly parallel search[END_REF], [START_REF] Régin | Improvement of the embarrassingly parallel search for data centers[END_REF]) splits the initial problem in a very large number of subproblems whose resolution time can be shared by workers: all subproblems are put in a queue and workers take subproblems when they need work. Experiments in [START_REF] Régin | Embarrassingly parallel search[END_REF], [START_REF] Régin | Improvement of the embarrassingly parallel search for data centers[END_REF] show us that a good decomposition is generally obtained, with EPS, by generating about 30 subproblems per worker. In [START_REF] Régin | Improvement of the embarrassingly parallel search for data centers[END_REF], the average speedup reported with EPS is close to 0.5k, where k is the number of workers, on a large benchmark of instances. This is much better than the speedup obtained with a work stealing approach, where subproblems are dynamically generated by splitting the subproblem currently solved by a worker, whenever another worker has finished its own work. However, even when decomposing the initial problem into 30 subproblems per worker, it may happen that one subproblem is much more difficult than the others and becomes a bottleneck for the speedup. Let t max be the time needed to solve the hardest subproblem, and t 0 be the time needed to solve the initial problem; the speedup cannot be higher than t 0 /t max .

A first goal of this paper is to study subproblem balance for the maximum common subgraph problem, and to show that the decomposition proposed in [START_REF] Régin | Embarrassingly parallel search[END_REF], [START_REF] Régin | Improvement of the embarrassingly parallel search for data centers[END_REF] leads to very unbalanced subproblems: on our benchmark, t 0 /t max is equal to 4 when decomposing problems into 400 subproblems or so. As a consequence, the speedup cannot be higher than these bounds. Actually, with 30 subproblems per worker, we observe an average speedup of 3. This motivates us to introduce and experimentally evaluate two new decomposition methods for the maximum common subgraph problem. The first one is a straightforward modification of EPS: instead of creating a subproblem for every possible value in a variable domain (while removing inconsistent subproblems), we introduce a binary decomposition where domains are split in two parts. The second one is fundamentally different and borrows features from the structural decomposition proposed in [START_REF] Jégou | Decomposition of domains based on the microstructure of finite constraint-satisfaction problems[END_REF] and extended in [START_REF] Chmeiss | On a generalization of triangulated graphs for domains decomposition of csps[END_REF], where a constraint satisfaction problem is decomposed into independent subproblems by exploiting the structure of its microstructure. Experimental evaluations show us that these two new decompositions lead to more balanced subproblems, and that structural decomposition allows us to increase the speedup with a reasonable number of workers for two classes of instances, whereas it slightly decreases it for one class.

The next section of this paper presents the background of this work: the maximum common subgraph problem, the domain decomposition method of [START_REF] Régin | Embarrassingly parallel search[END_REF], [START_REF] Régin | Improvement of the embarrassingly parallel search for data centers[END_REF], and the structural decomposition method of [START_REF] Jégou | Decomposition of domains based on the microstructure of finite constraint-satisfaction problems[END_REF]. Sections III and IV introduce two new decompositions for the maximum common subgraph problem. Section V presents an experimental comparison of these two new decompositions with the original decomposition of [START_REF] Régin | Embarrassingly parallel search[END_REF] on a classical benchmark.

II. BACKGROUND

A. Maximum common subgraph

An undirected graph G is defined by a finite set of nodes N G and a set of edges E G ⊆ N G × N G . Each edge is an undirected couple of nodes. In a directed graph, E G is a set of arcs, which are directed couples of nodes. In the following definitions, we will only be considering undirected graphs. However, these notions may be applied to directed graphs as well.

Definition 1: Let G and G be graphs. G is isomorphic to G if there exists a bijective function f :

N G → N G which preserves edges, i.e. ∀(u, v) ∈ N G × N G , {u, v} ∈ E G ⇔ {f (u), f (v)} ∈ E G Definition 2: G is an induced subgraph of G if N G ⊆ N G and E G = E G ∩ (N G × N G ). We say that G is the subgraph of G induced by N G , denoted G ↓N G .
In other words, G is obtained from G by removing all nodes of G which are not in N G and keeping only edges whose extremities are both in N G . Definition 3: A common subgraph of two graphs G and G is a graph isomorphic to subgraphs of G and G .

Definition 4: A Maximum Common Induced Subgraph (MCIS) is a common induced subgraph which has a maximum number of nodes. Figure 1 displays an example of MCIS.

In this article, we restrict ourselves to the MCIS, but the results can easily be extended to the maximum common partial subgraph problem as shown in [START_REF] Ndiaye | Cp models for maximum common subgraph problems[END_REF].

There exist two main approaches for solving MCIS: the first approach (described in II-B) explores the search space by branch and bound, and this may be achieved by using constraint programming (CP); the second approach (described in II-C) is based on a reformulation of MCIS into a maximum clique problem.

B. CP model for the MCIS

CP solves problems modelled as Constraint Satisfaction Problems (CSPs): a CSP is defined by a triple (X, D, C) such that X is a finite set of variables, D associates a domain D(x i ) with every variable x i ∈ X, and C is a set of constraints such that each constraint is defined over a subset of variables and gives lists of values these variables can be assigned simultaneously. A solution is an assignment of all variables satisfying every constraint. CP solves CSPs by building a search tree and propagating constraints at each node of the search tree in order to prune branches.

[8] introduces a CSP model for solving MCIS with CP. Given two graphs G and G , this CSP associates a variable x u with every node u of G, and the domain of this variable contains all nodes of G , plus an additional value ⊥: variable x u is assigned to ⊥ if node u is not matched to any node of G ; otherwise x u is assigned to the node of G it is matched with. A set of edge constraints is introduced in order to ensure that variable assignments preserve edges between matched nodes, i.e., ∀{u, v}

⊆ N G , (x u = ⊥) ∨ (x v = ⊥) ∨ ({u, v} ∈ E G ⇔ {x u , x v } ∈ E G ).
MCIS is an optimization problem, the goal of which is to maximize the number of matched nodes. To ensure that, the CSP also contains:

• a variable cost which corresponds to the number of nodes of G which are not matched; • a variable x ⊥ whose domain is D(x ⊥ ) = {⊥} so that it is forced to be assigned to ⊥;

• a soft constraint softAllDiff ({x u , u ∈ N G } ∪ {x ⊥ }, cost)
which ensures that all x u variables are assigned to values different from ⊥ whenever it is possible, and that the cost variable is equal to the number of x u variables that should change their value so that they all have different values. A solution is an assignment of all variables which satisfies all edge constraints while minimizing the value of cost.

[8] experimentally evaluates different constraint propagation techniques for this CSP modelling of the MCIS. The combination "MAC+Bound" generally obtains very good results and outperforms the state-of-the-art branch and bound approach of [START_REF] Mcgregor | Backtrack search algorithms and the maximal common subgraph problem[END_REF]: Maintaining Arc Consistency (MAC) [START_REF] Sabin | Contradicting conventional wisdom in constraint satisfaction[END_REF] is used to propagate hard constraints; "Bound" checks whether it is possible to assign distinct values to enough x u variables to surpass the best cost found so far (it is a weaker version of GAC(softAllDiff ) [START_REF] Petit | Specific filtering algorithms for over-constrained problems[END_REF] which computes the maximum number of variables that can be assigned distinct values).

C. Reformulation of MCIS as a maximum clique problem

We may solve MCIS by introducing a compatibility graph and searching for cliques in it [START_REF] Balas | Finding a maximum clique in an arbitrary graph[END_REF], [START_REF] Durand | An efficient algorithm for similarity analysis of molecules[END_REF], [START_REF] Raymond | Rascal: calculation of graph similarity using maximum common edge subgraphs[END_REF].

Definition 5: A compatibility graph of two graphs G and G is an undirected graph G C whose set of nodes is

N G C = N G × N G and whose set of edges is N G E = {(u, u ), (v, v )} ⊆ N G C , (u, u ) and (v, v ) are compatible , where two nodes (u, u ) and (v, v ) of N G C are compatible if u = v and u = v , and if they preserve edges (i.e. {u, v} ∈ E G ⇔ {u , v } ∈ E G ).
A clique is a subgraph whose nodes are all linked pairwise. A clique is maximal if it is not strictly included in any other clique, and it is maximum if it is the biggest clique of a given graph, with respect to the number of nodes.

As illustrated in Figure 2, a clique in G C corresponds to a set of compatible matchings of nodes in G and G . Therefore, such a clique corresponds to a common induced subgraph, and a maximum clique of G C is a MCIS of G and G . It follows that any method able to find a maximum clique in a graph can be used to solve the MCIS problem. This yields similar results than a branch and bound approach [START_REF] Conte | Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs[END_REF].

D. Domain decomposition for CP

To speedup the solution process of CP, we may parallelize it as proposed in [START_REF] Régin | Embarrassingly parallel search[END_REF], [START_REF] Régin | Improvement of the embarrassingly parallel search for data centers[END_REF]. The idea is to split the initial CSP into a large number of independent subproblems which are solved in parallel by workers. A key point to balance the workload is to generate more subproblems than workers (typically, 30 subproblems by worker). The decomposition into subproblems is computed by selecting a subset of variables and by enumerating the combinations of values of these variables that are not detected inconsistent by the propagation mechanism of a CP Solver. More precisely, a Depth-Bounded Depth-First Search (DBDFS) is used to compute subproblems. A DBDFS is a Depth-First Search that never visits nodes located at a depth greater than a given value. First, we consider a static ordering of the variable (usually, by non decreasingly domain sizes). Then, the main step of the algorithm is applied: define a depth p and perform a DBDFS with p as limit. This search triggers the constraint propagation mechanism each time a modification occurs. For each leaf of this search which is not a failure, the first p variables are assigned and so the subproblem defined by this assignment is consistent with the propagation. Thus the set of leaves defines a set S of subproblems. Next, if S is large enough, then the decomposition is finished. Otherwise, the main step is applied again until the expected number of subproblems is reached. From here onward, we will designate this method with "domain decomposition" (DOM) for clearer comparisons with other methods.

E. Structural decomposition for CSPs

A dual approach to decompose a CSP is to exploit its structure. A first way to do that is to compute a tree decomposition of the constraint hypergraph (which associates a node with each variable, and an hyperedge with each a b c constraint) in order to identify independent subproblems, as proposed in [START_REF] Dechter | Tree-Clustering for Constraint Networks[END_REF]. However, this kind of approach is useless for solving MCIS because the scope of the softAllDiff constraint is the whole set of variables, so that the tree decomposition contains only one node (i.e. one subproblem). Another structural approach for decomposing a CSP into independent subproblems has been proposed by [START_REF] Jégou | Decomposition of domains based on the microstructure of finite constraint-satisfaction problems[END_REF] and is called TR-decomposition. The idea is to reformulate the CSP as the problem of finding a clique of size n (with n the number of variables in the CSP) in its microstructure. The microstructure of a CSP is a graph similar to the compatibility graph described in II-C. Each node is associated with a (variable, value) couple. There is an edge between two nodes if and only if the corresponding assignments are compatible, i.e. if every constraint of the problem is satisfied when those two assignments are made simultaneously. Thereby, a clique of size n in the microstructure is a solution of the CSP.

The main idea behind TR-decomposition is to triangulate the microstructure to generate subproblems more easily. Indeed, a triangulated graph G cannot contain more than |N G | maximal cliques, whereas non triangulated graphs may contain an exponential number of maximal cliques.

Definition 6: A graph G is triangulated if and only if every cycle whose length is 4 or more has a chord. A chord is an edge whose extremities are two non-consecutive nodes of a same cycle.

The process of turning a given graph into a triangulated graph only by adding edges is called triangulation. Since triangulation adds edges without removing any, the maximal cliques of the original graph can still be found, included in the maximal cliques of the triangulated graph. To proceed with TR-decomposition, one must recover these cliques within the newly formed ones.

To sum up, TR-decomposition consists in building the microstructure of the problem, triangulating it, computing the maximal cliques of the triangulated microstructure and solving separately the subproblems induced by those cliques.

III. BINARY DOMAIN DECOMPOSITION FOR MCIS

The DOM decomposition introduced in [START_REF] Régin | Embarrassingly parallel search[END_REF] basically creates subproblems by assigning some variables while removing inconsistent subproblems. When applying this decomposition method to the CP model of the MCIS recalled in II-B, we obtain subproblems by assigning a subset of variables X a ⊆ {x u , u ∈ N G } to nodes of G or to ⊥. First experiments (reported in Section V) have shown us that this decomposition leads to very unbalanced subproblems, and therefore very low speedups. Actually, assigning a variable x u to a node v ∈ N G often strongly reduces variable domains, as the propagation of edge constraints removes from the domains of the variables associated with neighbours of u all nodes of N G which are not neighbours of v. However, assigning a variable x u to ⊥ (i.e., deciding that u will not be matched) never reduces the domains of the other variables (except when the number of variables assigned to ⊥ becomes equal to the cost bound so that ⊥ is removed from all other domains). This explains why some subproblems are very easy to solve whereas others are much harder, even though they all have the same search space size.

In order to try to generate more balanced subproblems, we introduce another way of decomposing domains, called BIN hereafter. It is a straightforward adaptation of the decomposition of [START_REF] Régin | Embarrassingly parallel search[END_REF]. We perform a DBDFS, but instead of creating |N G | + 1 branches at each node (one for each possible value in the domain of the variable), we only create two branches: one where the variable is assigned to ⊥, and one where ⊥ is removed from the variable domain.

IV. STRUCTURAL DECOMPOSITION FOR MCIS

We introduce a new way to decompose MCIS into independent subproblems, guided by the structure of the problem. This method, called STR, is an adaptation of the TR-decomposition of [START_REF] Jégou | Decomposition of domains based on the microstructure of finite constraint-satisfaction problems[END_REF] to the CP model of [START_REF] Ndiaye | Cp models for maximum common subgraph problems[END_REF]. While TR-decomposition was initially defined for binary CSP instances, the CP model of [START_REF] Ndiaye | Cp models for maximum common subgraph problems[END_REF] is a soft CSP. Nevertheless, MCIS may be solved by finding a maximum clique in the compatibility graph. Likewise [START_REF] Jégou | Decomposition of domains based on the microstructure of finite constraint-satisfaction problems[END_REF], we propose to use the class of triangulated graphs to take advantage of their property to have a few maximal cliques.

More precisely, we triangulate the compatibility graph with the MinFill algorithm [START_REF] Kjaerulff | Triangulation of graphs -algorithms giving small total state space[END_REF]. This algorithm adds edges, called fill edges. The fill edges add erroneous compatibilities so that a maximum clique in the triangulated graph is not invariably the best solution anymore, but simply is a subproblem in which we might find solutions. Actually, a maximum clique of the original compatibility graph is still a clique (not necessarily maximum or maximal) in the triangulated graph. Moreover, it is bound to appear in at least one maximal clique of the triangulated compatibility graph. Therefore, each maximal clique of the triangulated graph defines a subproblem (actually an induced subgraph of the compatibility graph) in which we may find a maximum clique of the initial compatibility graph. Such a subproblem can be seen as MCIS instances, with smaller graphs, that can be solved using the CP model of [START_REF] Ndiaye | Cp models for maximum common subgraph problems[END_REF]. More precisely, given a maximal clique K of the triangulation of the compatibility graph associated with G and G , we define a subproblem which has the same variables and constraints as the initial problem (described in II-B). However, the domain of every variable x u is restricted to

D(x u ) = {v ∈ N G | (u, v) ∈ K} ∪ {⊥}
The domains of x ⊥ and cost remain unchanged. For example, in Figure 3, the subset of nodes {(b, 1), (b, 3), (c, 2)} is a maximal clique of the triangulated graph. In the associated subproblem, D(x b ) = {1, 3, ⊥}, D(x c ) = {2, ⊥}, and D(x a ) = {⊥}. Every solution of every subproblem corresponds to a maximal clique of the compatibility graph, and therefore to a common induced subgraph. In our example, the subproblem has two solutions of cost 1 (i.e., {x a = ⊥, x b = 1, x c = 2} and {x a = ⊥, x b = 3, x c = 2}) which are optimal and correspond to two maximal cliques of the compatibility graph (i.e., {(b, 1), (c, 2)} and {(b, 3), (c, 2)}) as edge {(b, 1), (b, 3)} is a fill edge which has been added by the triangulation.

STR may generate subproblems with very unbalanced sizes. In order to generate better balanced subproblems, and also to control the number of subproblems that are generated, we propose to recursively decompose the largest subproblems by running TR-decomposition on them again. This is described in Algorithm 1. We first triangulate the compatibility graph G C and store all its maximal cliques in a set S (lines 1-3). Then, while |S| is lower than the required number of subproblems, we remove from it its largest clique K, triangulate the subgraph of G C induced by K and compute the set S K of all its maximal cliques (lines 6-9). If there is only one maximal clique in the triangulation of the subgraph of G C induced by K, it means that K cannot be decomposed any more (line 10). Some cliques in S K may be subsets of cliques in S. These non maximal cliques are not added to S; all other cliques of S K are added to S (lines 12-13). Finally, once S contains enough cliques (or no more clique is decomposable), we build a subproblem for each clique, and return this set of subproblems (line 14).

Some maximal cliques may have large intersections. In such a case, the corresponding subproblems also have large intersections, meaning that we might solve a same part of subproblems several times. In order to reduce redundancies, some subproblems are merged, i.e. they are replaced by a new subproblem obtained by merging their variables' domains. Note that any solution will still be present in the resulting subproblem, since domains can only get bigger during this process. To prevent subproblems from growing back to the size of the initial problem, we introduce the notion of gain, which expresses the evolution of the size during an hypothetical fusion.

Definition 7: Let S 1 and S 2 be two distinct subproblems. The gain offered by the fusion of S 1 and S 2 is given by the following quotient: gain(S 1 , S 2 ) = size(S1)+size(S2) size(S1∪S2)

, where size(S i ) is the product of the sizes of variable domains of S i , and S 1 ∪ S 2 represents the subproblem that would be created if S 1 and S 2 were to be merged.

We merge two subproblems if the gain is greater than 1, giving priority to pairs offering the largest gains.

V. EXPERIMENTAL EVALUATION

A. Experimental setup

Our algorithms are developed in C and compiled with GCC's -O3 optimization option. Programs are executed with a time limit of three hours on an Intel R Xeon R CPU E5-2670 0 at 2.60 GHz processor, with 20, 480 KB of cache memory and 4 GB of RAM.

Instances are taken from the benchmark presented in [START_REF] Conte | Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs[END_REF] and are used in their labeled and directed versions. The number of different labels equals 15 % of the number of nodes in each graph. We take these labels into account like it is done in [START_REF] Ndiaye | Cp models for maximum common subgraph problems[END_REF], by ensuring matched nodes have the same label. By similar rules, edges between pairs of matched nodes must also have the same label. Each domain is therefore reduced to values associated to nodes having the exact same label than the node associated to the variable.

The benchmark contains three classes of instances (see [START_REF] Conte | Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs[END_REF] for details):

bvg Bounded Valence Graphs, where degrees cannot be higher than a given value for each graph. rand Random graphs, in which edges are set at random. mnD Meshes with two (m2D), three (m3D) or four (m4D) dimensions. We consider instances such that graphs have a number of nodes n ranging from 10 up to 100, and maximum common subgraphs have a number of nodes ranging from 0.1n to 0.3n.

The MCIS is an optimization problem. As pointed out in [START_REF] Mccreesh | The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound[END_REF], when solving an optimization problem with a parallel approach, a key point is to solve first the most promising subproblems (which contain better solutions) in order to allow more pruning when solving the remaining subproblems. In this experimental study, our goal is to evaluate the capability of DOM, BIN and STR to generate balanced independent subproblems, and we don't want to introduce a bias with ordering heuristics for choosing the most promising subproblems. Furthermore, heuristic algorithms are able to very quickly find near-optimal solutions to MCIS. For example, the AntClique algorithm of [START_REF] Solnon | A study of aco capabilities for solving the maximum clique problem[END_REF] is able to find a maximum clique (corresponding to a MCIS) for 90 % of our instances in a few seconds. However, proving the optimality of these optimal solutions with our baseline sequential approach (MAC+Bound [START_REF] Ndiaye | Cp models for maximum common subgraph problems[END_REF]) is still very challenging. Therefore, in this experimental study, we consider the problem of proving the optimality of a common subgraph. We selected instances which are solved within our time limit of three hours by our baseline sequential method. Since decomposition approaches are specifically designed for instances that are hard to solve, we reduced the scope to instances that are not solved in 100 seconds by the standard method. These constraints brought us to the final number of 109 instances.

For each instance, we began by testing STR. STR aims to generate a number of subproblems close to a parameter k by successive clique decompositions. In these experiments, k has been set to 1, 500. This number is then brought down to k by subproblem fusions, as explained in Section IV. To keep our study as fair as possible, BIN and DOM are then asked to generate k subproblems, thus solving as many subproblems as STR. Once the number of subproblems is fixed in this way (with a possibly different number for each instance), we try to solve those instances with different numbers of subproblems per workers (hence with different numbers of workers).

B. Notations

For an initial instance i defined by two graphs G and G , we introduce the following notations:

• s 0 is the size of i, i.e., the product of the sizes of its domains; • t 0 is the time to solve i;

• k is the number of subproblems remaining after STR's fusions for i (at most 1, 500); • t dec is the time to decompose i into k subproblems; • s all is the sum of sizes of all subproblems of i; • t all is the sum of times to solve all subproblems of i; • t max is the time to solve the hardest subproblem of i; • t min is the time to solve the easiest subproblem of i.

C. Search space size and decomposition time

When decomposing the initial instance into subproblems, some inconsistent values are filtered out, either by propagating constraints during DBDFS (for DOM and BIN), or when reconstructing domains from cliques (for STR). For each decomposition method, Table I displays s 0 /s all , followed by t dec /t 0 , on average for all instances of each class. It shows us that BIN does not filter domains at all so that the search space is not reduced (as pointed out in Section III). DOM (resp. STR) reduces the search space by a factor of 600 (resp. 200 millions), on average for all instances in all classes. This factor depends on instance classes and decomposition methods. In particular, for DOM (resp. STR), the search space reduction is lower than the average reduction on bvg and mesh (resp. mesh and rand) instances, whereas it is higher on rand (resp. bvg) instances.

Search space reduction should be considered together with the time spent for the decomposition (t dec ). Decomposition times of DOM and BIN are similar, and represent less than 0.04 % of t 0 (on average for all instances) for DOM and 0.007 % for BIN. Decomposition times of STR tend to be higher, and are close to 5 % of t 0 .

D. Speedup bounds

The time needed to solve the initial problem divided by the time needed to solve the hardest subproblem (i.e., t 0 /t max ) provides a first upper bound on the speedup. For each decomposition method, Table II bvg mesh rand all min avg max min avg max min avg max avg DOM 1.6 4.9 45.0 1.4 4.9 15.2 1.3 2.9 15. Again, we observe differences depending on the classes. In particular, for DOM and STR, the speedup bound is higher than the average on bvg and mesh instances, whereas it is lower on rand instances. Figure 4(a) compares DOM with STR for each instance separately. It shows us that if for a majority of instances the speedup bound is larger with STR than with DOM, there are some instances (mainly of the bvg and mesh types) for which the bound is larger with DOM than with STR. Figure 4(b) and (c) compare DOM with BIN, and BIN with STR, and the same remark holds for these plots.

However, if the time spent by the decomposition step (t dec ) is rather small for DOM and BIN, it is larger for STR. Hence, a tighter upper bound on the speedup may be obtained by dividing t 0 by t dec + t max . These speedups are displayed in Table III. It can be noticed that STR still obtains the largest average speedup bounds, though DOM obtains rather close bounds.

E. Time needed to solve subproblems

If the time needed to solve the hardest subproblem is a bottleneck, the speedup also depends on the hardness of all subproblems. To give an insight into this hardness, Table IV displays the time ratio between the easiest subproblem and the initial instance (t min /t 0 ), the average time ratio between a subproblem and the initial instance (t all /(k × t 0 )), and the time ratio between the hardest subproblem and the initial instance (t max /t 0 ), on average for all instances of each class.

On average, STR generates harder subproblems than DOM: 4 times as hard for bvg, twice as hard for mesh and 10 times as hard for rand. On the other hand, the hardest subproblem for each instance is easier when decomposing with STR than when decomposing with DOM.

F. Correlation between time and search space size

Table IV shows us that the subproblems obtained when decomposing an initial instance are of very fluctuating difficulty. Actually, in most cases, there are a lot of very easy subproblems, and only very few hard subproblems. To obtain a speedup as close as possible to the bounds displayed in Table III, a key point is to be able to identify these hard instances so that we can solve them first and better balance the workload. Therefore, we plot in Figure 5 the relation between the size of the search space of a subproblem, and the time needed to solve it. It demonstrates that two subproblems with a same size may be of very different difficulty. However, we note that, for STR, the rightmost points (corresponding to the largest subproblems) tend to have large y values (corresponding to the hardest subproblems). This remark still holds for DOM, to a lesser extent. This is no longer true for BIN, for which there is no satisfying correlation between size and time. Note that for all decomposition methods, there are subproblems which have rather small sizes but which are hard to solve.

G. Speedup with 30 subproblems per worker

Table V displays the speedup observed with 30 subproblems per worker, for each decomposition method, and each class of instances (minimum, average and maximum speedups). This number of subproblems per worker was described as generally efficient by [START_REF] Régin | Improvement of the embarrassingly parallel search for data centers[END_REF]. Let t real be the total time spent by the last worker which has completed its work. The speedup is t 0 /(t dec + t real ).

We note that BIN has very low speedups. STR has better speedups than DOM on bvg and mesh instances, whereas it has a lower speedup on rand instances. These rankings basically correspond to rankings observed on speedup bounds for DOM and STR.

Let us finally note that these speedups are quite low, even for the best decomposition method STR. As a comparison, [START_REF] Régin | Embarrassingly parallel search[END_REF] reports results on 20 CSPs (and many instances for each CSP). With 40 workers and 40×30 = 1, 200 subproblems by instance, the average speedup is 21.3, and the worst speedup is 8.6.

H. Speedup with different numbers of workers

Experiments in [START_REF] Régin | Embarrassingly parallel search[END_REF], [START_REF] Régin | Improvement of the embarrassingly parallel search for data centers[END_REF] show us that a good EPS decomposition is generally obtained by generating about 30 subproblems per worker. In this study, we generated approximately as many subproblems with each method and tried solving them with different numbers of workers, thus varying the number of subproblems per worker.

Figure 7 compares speedups obtained with STR and DOM when varying the number of subproblems per worker from 1 to 50. When the number of subproblems per worker is higher than 35, speedups with DOM are higher than speedups with STR. However, when the number of subproblems per worker is lower than 35, STR obtains better speedups than DOM. This may come from the fact that even though STR generates harder subproblems, on average, than DOM (see Table IV), its hardest subproblems are easier.

VI. CONCLUSION

We have introduced a structural decomposition method for the MCIS problem derived from the TR-decomposition method defined in [START_REF] Jégou | Decomposition of domains based on the microstructure of finite constraint-satisfaction problems[END_REF]. It relies on a triangulation of the compatibility graph of the problem and allows to decompose the problem into several independent subproblems. We have experimentally compared this structural decomposition with the domain decomposition method proposed by [START_REF] Régin | Embarrassingly parallel search[END_REF], showing that it leads to higher speedups for two classes of instances, and to weaker speedups for one class.

The decomposition of the initial instance into subproblems is time-consuming. In this paper, this decomposition step has not been parallelized. [START_REF] Régin | Improvement of the embarrassingly parallel search for data centers[END_REF] proposes to parallelize this decomposition step, and this allows them to obtain better speedups. Our structural decomposition method could be parallelized. In particular, instead of treating each clique K separately (in the loop lines 5-13 of Algorithm 1), we could treat several cliques in parallel.

Figure 1 .

 1 Figure 1. Example of MCIS. A bijection between MCIS nodes can be defined as follows: 2 ↔ d, 3 ↔ e, 4 ↔ b, 5 ↔ c, 6 ↔ a.

3 Figure 3 .

 33 Figure 3. A triangulated version of the compatibility graph of Figure 2. The edges that were added (fill edges) are shown with dashed lines.

Algorithm 1 :

 1 STR decompositionInput: 2 graphs G and G , a number k of subproblems Output: A set of subproblems 1 Build the compatibility graph GC associated with G and G 2 Triangulate GC (with MinFill [17]) to obtain GT 3 Compute the set S of all maximal cliques of GT 4 Mark all cliques of S as decomposable 5 while |S| < k and S contains decomposable cliques do 6 Remove from S its largest decomposable clique K 7 Let G C↓K be the subgraph of GC induced by K 8 Triangulate G C↓K (with MinFill [17]) to obtain G T ↓K 9 Compute the set SK of all maximal cliques of G T ↓K 10 if SK = {K} then mark K as non decomposable; 11 else mark all cliques of SK as decomposable; 12 for each clique K ∈ SK do 13 if ∀K ∈ S, K ⊆ K then add K to S; 14 return the set of all subproblems associated with cliques of S

Figure 4 .

 4 Figure 4. Speedup bounds without t dec : Each point (x, y) in (a) (resp. (b) and (c)) corresponds to an instance such that x = t 0 /tmax for DOM (resp. DOM and BIN) and y = t 0 /tmax for STR (resp. BIN and STR).

  5 4.1 BIN 1.1 4.0 8.0 0.7 4.6 10.5 0.5 3.7 11.6 4.0 STR 1.5 11.1 54.3 1.5 9.1 25.1 2.4 5.5 30.2 8.4

Figure 5 .

 5 Figure 5.Size w.r.t. time: for each decomposition method d ∈ {DOM, BIN, STR}, and each instance class c ∈ {bvg, mesh, rand}, the subfigure d/c plots a point (x, y) for each subproblem obtained when decomposing an instance of c with d, where x is the size of the search space of this subproblem, and y is the time needed to solve it.

Figure 6 .

 6 Figure 6. Speedups with 30 subproblems per worker: Each point (x, y) in (a) (resp. (b) and (c)) corresponds to an instance such that x is the speedup for DOM (resp. DOM and BIN) and y for STR (resp. BIN and STR).

Figure 7 .

 7 Figure 7. Observed speedups with different numbers of workers, for DOM and STR.

Table I REDUCTION

 I OF SIZE AND DECOMPOSITION TIME.DOM 3 e 2 2 e -4 1 e 2 1 e -4 1 e 3 6 e-4

		s 0	bvg t dec	mesh s 0 t dec	rand s 0 t dec	all instances s 0 t dec
		s all	t 0	s all	t 0	s all	t 0	s all	t 0
									6 e 2	4 e -4
	BIN		1 3 e -5	1 3 e -5	1 1 e -4	1	7 e -5
	STR	5 e 8 2 e -2 6 e 5 3 e -2 1 e 6 8 e -2	2 e 8	5 e -2

  displays this bound (minimum, average and maximum values for each class Table II SPEEDUP BOUND WHEN IGNORING t dec (i.e., t 0 /tmax).

Table III SPEEDUP

 III BOUND WHEN INTEGRATING t dec (i.e., t 0 /(t dec + tmax)).

	bvg	mesh	rand	all
	min avg max min avg max min avg max avg
	DOM 1.6 4.8 44.6 1.4 4.9 15.2 1.3 2.9 15.

Table IV SUBPROBLEM

 IV SOLVING TIME: MIN (t min /t 0 ), AVG (t all /(k × t 0 )) AND MAX (tmax/t 0 ). e -3 4 e -3 320 e -3 0.1 e -3 7 e -3 293 e -3 0.1 e -3 4 e -3 491 e -3 BIN 6 e -3 48 e -3 273 e -3 2 e -3 44 e -3 317 e -3 14 e -3 78 e -3 306 e -3 STR 0.1 e -3 15 e -3 175 e -3 0.1 e -3 12 e -3 179 e -3 0.3 e -3 38 e -3 265 e -3 of instances). On average for all instances of all classes, the largest speedup bound is obtained with STR (8.4), the second largest by DOM (4.1), and the smallest by BIN (4.0). However, all these speedup bounds are rather low when considering the fact that each instance has been decomposed into 470 subproblems in average (min. 192, max. 1053).

		bvg		mesh		rand
	min	avg	max	min avg	max	min avg	max
	DOM 0.05

Table V SPEEDUP

 V WITH 30 SUBPROBLEMS PER WORKER.

a, 1 a, 2 a, 3 b, 1 b, 2 b, 3 c, 1 c, 2 c, 3Figure2. Two graphs and their compatibility graph G C . For example, since {a, c} is not an edge while {1, 3} is an edge, the edge {(a, 1), (c, 3)} does not belong to G C . One of the many maximum cliques in G C is {{a, 3}, {b, 2}} and it corresponds to a MCIS.

ACKNOWLEDGMENT

This work has been supported by the ANR project SoL-StiCe (ANR-13-BS02-0002-01).