Antonin Richard
email: antonin.richard@univ-lorraine.fr

Christophe Morlot

Laura Créon

Nicolas Beaudoin

Vladimir S Balistky

Svetlana Pentelei

Vanessa Dyja-Person

Gaston Giuliani

Isabella Pignatelli

Hélène Legros

Jérôme Sterpenich

Jacques Pironon

Advances in 3D imaging and volumetric reconstruction of fluid and melt inclusions by high resolution X-ray computed tomography

Keywords: Fluid inclusions, melt inclusions, high resolution X-ray computed tomography, volume, shape, phase

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Tiny droplets of fluid and melt are trapped within natural and synthetic minerals as fluid and melt inclusions which represent invaluable toolsto understand crystal growth and mass transfer in the Earth's mantle and crust. The 3D distribution of fluid and melt inclusionswithin crystals, their shapeand the volumetric proportions of their different phases are key information for the determination of the relationship between crystal growth, deformation and the nature of the fluids and melts involved (e.g. [START_REF] Roedder | Fluid Inclusions[END_REF][START_REF] Frezzotti | Silicate-melt inclusions in magmatic rocks: applications to petrology[END_REF][START_REF] Bodnar | Melt inclusions in plutonic rocks: Petrography and microthermometry[END_REF][START_REF] Kesler | Role of fluid and melt inclusions studies in geologic research[END_REF]. However, such data aredifficultto acquire with good confidence because optical observation is frequently hampered by perspective and projection issues. For instance, the estimation of the volumetric fraction of the vapor phase to the entire inclusion at room temperature (φ vap ) may be incorrect when deduced from area fractions [START_REF] Bakker | Estimation of volume fractions of liquid and vapor phases in fluid inclusions, and definition of inclusion shapes[END_REF]. This led to the development of a series of tools and methods allowing significant improvement in textural, microstructural, morphological and volumetric reconstruction of fluid and melt inclusions like for instancethe four-axis universal stage [START_REF] Tuttle | Structural petrology of planes of liquid inclusions[END_REF]; relationships between vapor phasediameter, the temperatures of freezing and liquid-vapor homogenization and the volumetric properties of the fluids in the H 2 O-NaCl system [START_REF] Bodnar | A method of calculating FI volumes based on vapor bubble diameters and PVTX properties of inclusion fluids[END_REF], the spindle stage [START_REF] Anderson | An adaptation of the spindle stage for geometric analysis of fluid inclusions[END_REF], confocal scanning laser microscopy [START_REF] Petford | Preliminary confocal scanning laser microscopy study of fluid inclusionsin quartz[END_REF],transmission electron microscopy [START_REF] Viti | Transmission electron microscopy applied to FI investigations[END_REF]; AnIma [START_REF] Lespinasse | Microfissural mapping of natural cracks in rocks: Implications for fluid transfers quantification in the crust[END_REF]; second harmonic generation microscopy [START_REF] Stoller | Femtosecond lasers in FI analysis: Threedimensional imaging and determination of inclusion volume in quartz using second harmonic generation microscopy[END_REF]and synchrotron-based X-ray fluorescence computed tomography [START_REF] Cauzid | 3D imaging of vapor and liquid inclusions from the Mole Granite, Australia, using helical fluorescence tomography[END_REF]and nano X-ray tomography [START_REF] Yao | ×5×0.5 mm 3×4×0.15 mm Inclusion type Silicate MI Aqueous FI Aqueous FI Aqueous FI Aqueous FI Hydrocarbon-bearing FI Hydrocarbon-bearing FI Hydrocarbon[END_REF].

High resolution X-ray computed tomography(HRXCT) is a non-destructive method which uses contrasts of X-ray attenuation in a series of contiguous radiographs with different view angles to reconstruct the 3D distribution of areas of different densities within a large variety of materials. HRXCT has been increasingly used for characterizing Earth materials over the past two decades [START_REF] Ketcham | Acquisition, optimization and interpretation of X-ray computed tomographic imagery: applications to the geosciences[END_REF]Cnuddle and Boone, 2013). Among various examples, HRXCT has been successfully applied to unravel the shape, orientation and 3D distribution of minerals,porosity and cracksin various rocks showing complex textures like sedimentary rocks [START_REF] Noiriel | Resolving time-dependent evolution of pore-scale structure, permeability and reactivity using X-ray microtomography[END_REF], metamorphic rocks [START_REF] Sayab | Highresolution X-ray computed microtomography: A holistic approach to metamorphic fabric analyses[END_REF], magmatic rocks [START_REF] Baker | A fourdimensional X-ray tomographic microscopy study of bubble growth in basaltic foam[END_REF], mantle rocks [START_REF] Créon | Highly CO 2 -supersaturated melts in the Pannonian lithospheric mantle -A transient carbon reservoir?[END_REF], ores (Kyle and Ketcham,2015) and extraterrestrial materials [START_REF] Hanna | X-ray computed tomography of planetary materials: A primer and review of recent studies[END_REF].

Since the pioneering study of [START_REF] Nakashima | Three-dimensional imaging of arrays of fluid inclusionsin fluorite by high-resolution X-ray CT[END_REF],fluid and melt inclusions have been the subject of only a few studies by HRXCT even with more recent and powerful equipment [START_REF] Kyle | Contributions of high resolution X-ray computed tomography to ore studies[END_REF]Kyle and Ketcham, 2007a,b, 2008[START_REF] Noiriel | Resolving time-dependent evolution of pore-scale structure, permeability and reactivity using X-ray microtomography[END_REF][START_REF] Nowecki | Tracing seawater evaporation and its role in the formation of sedimenthosted stratiform copper deposits[END_REF][START_REF] Pamukcu | Quantitative 3D petrography using X-ray tomography 4: Assessing glass inclusion textures with propagation phase-contrast tomography[END_REF][START_REF] Pamukcu | Melt inclusion shapes: Timekeepers of short-lived giant magma bodies[END_REF][START_REF] Gaetani | Reconstructing magma storage depths from olivine-hosted melt inclusions: Do vapor bubbles matter?[END_REF][START_REF] Farley | Olivine barometry based on X-ray computed tomography of fluid inclusions[END_REF].These studies have shown that HRXCT allows imaging isolated fluid and melt inclusions,fluid inclusionclusters and trails, as well as discriminatingand quantifying different phases within fluid inclusionsand silicate melt inclusions in transparent (e.g. quartz, olivine) and opaque (e.g. pyrite, pyrrhotite, sphalerite) minerals.Here, in an attempt to provide an overview of the current capabilities and future perspectives of HRXCT for the study of fluid and melt inclusions,we show the results of a series of experiments using three HRXCT setups at Université de Lorraine (France), University of Strathclyde (UK) and Universidad Nacional Autónoma de México (Mexico).

Nine samples containing eitheraqueous fluid inclusions, hydrocarbon-bearingfluid inclusions or silicate melt inclusionsin transparent(natural and synthetic quartz, "trapiche" emerald, gem "demantoid" garnet, olivine) and opaque (wolframite) minerals were analyzed. Both 3D imaging of fluid inclusions distribution within single crystals and quantitative volumetric reconstruction of the different phases within single fluid and melt inclusions were carried out.

Sample description

The samples were selected to cover some common types of fluid and melt inclusion compositions found in nature orused as synthetic inclusions, as well as various transparent and opaque host minerals. The targeted inclusions have all in common to be relatively large (>25 µm) to event "giant" (~ 5 mm), and display variable shape and infilling. Their characteristics are provided below and in Table 1.

2.1.Silicate melt inclusions(Sample A)

The volcanic material (Sample A)wascollected at Los Humeros volcanic complex located in the easternpart of the Trans-Mexican Volcanic Belt in Mexico (Table 1). Both the Trans-Mexican Volcanic Beltand Los Humeros volcanic complex exhibit a large diversity of alkaline to calk-alkaline volcanism (Gómez-Tuena et al., 2016;[START_REF] Créon | New method for initial composition determination of crystallized silicate melt inclusions[END_REF]. Sample A was collected in porphyritic lavas from the 8.91 ka post-caldera event [START_REF] Créon | New method for initial composition determination of crystallized silicate melt inclusions[END_REF][START_REF] Dávila-Harris | An unusual syn-eruptive bimodal eruption: The Holocene Cuicuiltic Member at Los Humeros caldera, Mexico[END_REF]. Sample A contains plagioclase, olivine, orthopyroxene and clinopyroxene phenocrysts together with large vesicles and a glass matrix.Olivine phenocrysts are 0.5-2.0 mm large and contain isolated, round silicate melt inclusionsup to 230 µm in diameter, with a vapor bubble (Fig. 1). Euhedral crystals of spinel and clinoyroxene (as identified by secondary electron microscopy) are observed inside the silicate melt inclusion (Fig. 1). These crystals nucleated after the trapping of the silicate melt inclusion.The analyzed material consists of a single olivine phenocryst (1.0 mm large) separated from Sample A.

Aqueous fluid inclusions (SamplesB, C, D, E, F)

Sample B consists of water + H 2 fluid inclusionstrapped in synthetic quartz grown by the hydrothermal temperature gradient method using refractory autoclaves, produced at theInstitute of Experimental Mineralogy, Russian Academy of Sciences (Chernogolovka, Moscow oblast, Russia)(Table 1). The full experimental procedures for quartz and fluid inclusion synthesis and characterization are described in [START_REF] Balitsky | Visual in-situ monitoring of the behavior and phase states of water-hydrocarbon inclusions at high temperatures and pressures[END_REF][START_REF] Balitsky | The causes of vertical zonation in the distribution of hydrocarbons over the Earth's interior: Experimental evidence of the cracking of crude oil in high-temperature water-hydrocarbon fluids[END_REF][START_REF] Balitsky | Synthetic aqueous-hydrocarbon inclusions in quartz as a source of information on the oil and gas content in bituminous shale and the phase state of hydrocarbons in a wide range of temperatures and pressures[END_REF].

Sample B is a 3×5×2 cm monocrystal showing arrays of elongated and oriented two-phase (liquid + vapor) aqueous fluid inclusions(Fig. 2). No sectioning was carried out prior to HRXCT scanning and Sample B was scanned both entirely and on a 1.4×1.4×1.4 mm region of interest.

Sample C consists of synthetic two-phase liquid + vapor aqueous fluid inclusions trapped in a natural quartz, produced at the GeoRessources laboratory, Université de Lorraine (Vandoeuvre-lès-Nancy, France) (Table 1). Fluid inclusion synthesis was conducted following the procedure exposed in [START_REF] Jacquemet | In situ Raman spectroscopy identification of the S3ion in S-rich hydrothermal fluids from synthetic fluid inclusions[END_REF], inspired from the one of [START_REF] Sterner | Synthetic fluid inclusionsin natural quartz I. Compositional types synthesized and applications to experimental geochemistry[END_REF]. A pre-fractured quartz lamella (5×5×1 mm)wasused to trap the fluid inclusions at 600°C-2.0 kbars. The experimental H 2 O-NaCl solution hada salinity of 7.7 wt.% NaCl. Considering these pressure, temperature, molar volume and composition (P-T-V-x) conditions for trapping, the expectedφ vap valuewas42% [START_REF] Bakker | Package FLUIDS 1. Computer programs for analysis of FI data and for modelling bulk fluid properties[END_REF]. After fluid inclusion synthesis, the quartz lamella was doubly polished to reach a 0.4 mm thickness for optical microscopy and HRXCT analyses. Examination under optical microscope showedthe presence of numerous two-phase (liquid + vapor) fluid inclusions (1-100 µm) with apparent φ vap value compatible with the theoretical value of 42% (Fig. 3).

Sample D was collected from the Antetezambato gem-quality "demantoid" garnet deposit, near Ambanja, in the Ambato peninsula of northern Madagascar (Table 1). This deposit is classified as a skarn-type deposit related to Upper Mesozoic to Cenozoic magmatism affecting the limestones of the Mesozoic Isalo Group (Giuliani et al., 2015 and references therein). The greenish gem-quality"demantoid" andradite crystal measures 1.5×0.6 cm and hosts a gianttwo-phase (liquid + vapor) aqueous fluid inclusion visible to the naked eye (Fig. 4; [START_REF] Giuliani | Demantoid garnet with giant FI[END_REF][START_REF] Morlot | La tomographie de rayons X et ses applications en géologie: exemples de l'émeraude trapiche et du grenat démantoïde[END_REF]. No sectioning was carried out prior to HRXCT scanning and Sample D was scanned entirely.

Sample E was collected from the Muzo depositon the western side of the Eastern Cordillera Basin, Colombia (sample T12 in [START_REF] Pignatelli | Colombian trapiche emeralds: Recent advances in understanding their formation[END_REF] (Table 1). The emerald deposits are hosted by Lower Cretaceous sedimentary rocks forming two mineralized zones located on the eastern and western border of the basin, respectively. The emeralds are formed by interaction between hydrothermal H 2 O-NaCl-CO 2 fluids and black shales. Trapiche emeralds are very rare and are only found in a few depositsfrom the western emerald zone.

Their occurrence is related to a complex context of fluid pressure variations along faults and thrusts, affecting the growth of the emerald. On a section perpendicular to the c-axis of the emerald, the trapiche texture is typified by a central core, six arms, which are crystallographically equivalent growth sectors, and dendritesbetween the arms and around the core (Fig. 5). The trapiche emeralds host primary multi-phase (liquid + vapor + halite + carbonates ± sylvite) aqueous fluid inclusionsand large secondary monophase (liquid) aqueous fluid inclusionsstudied here, developed parallel to the dislocations in the arms (Fig. 5; [START_REF] Pignatelli | Colombian trapiche emeralds: Recent advances in understanding their formation[END_REF]. No sectioning was carried out prior to HRXCT scanning and Sample E was scanned entirely.

Sample F was collected from the Piaotang W-Sn deposit located in the southern Jiangxi province (SE China) (Table 1).At Piaotang, a buried Jurassic granite shows alteration by hydrothermal fluids in its upper part. The W-Sn mineralsare located within vertical hydrothermal veins that are rooted in the granite and are mostly hosted in the metasedimentary country rocks [START_REF] Legros | The ore-forming magmatic-hydrothermal system of the Piaotang W-Sn deposit (Jiangxi, China) as seen from Li-mica geochemistry[END_REF].Sample F is a three centimeterlongopaque wolframite crystal with an average formula of Fe 0.5 Mn 0.5 WO 4 . The wolframite hosts primary (5-40 µm) two-phase liquid + vapor aqueous fluid inclusionseither isolated or aligned and elongated along the c-axis as well as secondary inclusions with similar infilling to primary inclusions (Legros et al.,submitted,this volume;Fig.6).Sulfide veinlets cut the wolframite crystal parallel and perpendicular to the c-axis. The analyzed material is a chip (3×4×0.2 mm) of a doubly polished thick section prepared from Sample F.

Hydrocarbon-bearingfluid inclusions (Samples G, H, I)

Samples G and H consist of hydrocarbon-bearingfluid inclusionstrapped in synthetic quartz, produced at theInstitute of Experimental Mineralogy, Russian Academy of Sciences (Chernogolovka, Moscow oblast, Russia)(Table 1). Quartz crystals with fluid inclusions were grown by the hydrothermal temperature gradient method using refractory autoclaves. The full experimental procedures for quartz and fluid inclusion synthesis and characterization weredescribed in [START_REF] Balitsky | Visual in-situ monitoring of the behavior and phase states of water-hydrocarbon inclusions at high temperatures and pressures[END_REF][START_REF] Balitsky | The causes of vertical zonation in the distribution of hydrocarbons over the Earth's interior: Experimental evidence of the cracking of crude oil in high-temperature water-hydrocarbon fluids[END_REF][START_REF] Balitsky | Synthetic aqueous-hydrocarbon inclusions in quartz as a source of information on the oil and gas content in bituminous shale and the phase state of hydrocarbons in a wide range of temperatures and pressures[END_REF]. Sample G was synthetized using 7.5 wt. % Na 2 CO 3 aqueous solution and oil. Sample H was synthetized using 7.0 wt. % Na 2 CO 3 aqueous solution and boghead. Temperature gradients between the top and bottom of the autoclave were 290/300 °C and 291/347 °C respectively. Sample Gshows an elongated (200 µm) fluid inclusion containing a vaporphase, an aqueous solution and oil as seen under optical microscope using ultraviolet (UV) illumination (Fig. 7). Sample H shows an elongated (500 µm) fluid inclusion containing a vapor phase, an aqueous solution, oil and solid bitumen as observed under optical microscope using visible light and UV illumination (Fig. 8). The analyzed materialswerechips (5×5×0.5 mm) of doubly polished thick sections prepared from Samples G and H. Sample I was collected from a petroleum field whose location and geological settings are kept confidential (Table 1). Sample I displays authigenic feldspar cements in which an elongated, 25 µm oil-bearing primary fluid inclusion was found (Fig. 9). The inclusion was analyzed by optical microscope using UV illumination showing that the liquid phase contains fluorescentoil. Then the inclusion was analyzed by confocal laser scanning microscopy [START_REF] Pironon | Volumetric reconstruction of individual oil inclusions by confocal scanning laser microscopy[END_REF] which allows 3D reconstruction of the inclusion and visualization of the vapor and liquid oil phases through ImageJ 3D Viewer (Fig. 9), with a spatial resolution lower than 0.5µm. By using this method, the calculated φ vap value of the fluid inclusion is 10 ± 2%.

The analyzed material wasa chip (3×4×0.15 mm) of a doubly polished thick section prepared from Sample I.

Analytical methods

The principles of the method as well as analytical conditions of the three setups used are described below as well as in Table 1.

Principles of HRXCT analysis and data processing

HRXCT is a non-destructive and non-invasive method which uses contrasts of X-ray attenuation (a function of density and atomic number) to reconstruct the 3D distribution of areas of different densities within a large variety of materials with a resolution down to ~ 1 µm/pixel(px) or 1 µm 3 /voxel(vx) (see [START_REF] Ketcham | Acquisition, optimization and interpretation of X-ray computed tomographic imagery: applications to the geosciences[END_REF]Cnuddle and Boone, 2013 for more details about the HRXCT data acquisition and processing and application to Earth materials). The 3D reconstruction is based on a series of contiguous 2D radiographs taken with different view angles, by rotating a sample around a single axis in small steps. In the following experiments, a correction of the ring artifact was done during analysis using specific filters and beam hardening corrections were carried out with the softwares mentioned below.Each phase (mineral, glass, liquid, vapor) wasseparatedmanually using simple greyscale threshold tool, by segmentation of the volumes corresponding to the relative density range of each individual phase. Separation is considered as optimal when the selected range of gray values selects all the voxels belonging to a phase while it does not select voxels that belong to a different phase. Such optimal separation is achieved thanks to a strong contrast between phases (as visible on 2D slicesin Fig. 2,4,7,8) and a reduced noise. Then, the volume of the different phases were calculated by the count of voxelsin the different voxelclusters.

HRXCT at Universidad Nacional Autónoma de México (Sample A)

Sample A was analyzed through X-ray micro-tomography at the Laboratorio Universitario de Microtomografía de Rayos X (Centro de Geociencias, Universidad Nacional Autónoma de México, Querétaro, Mexico) on the ZEISS Xradia 510 Versa instrument (Table 1). The detector was a CCD ANDOR camera, with 1080×1080 px and 32 bits resolution.

Polychromatic tomography with 30 kV radiation was performed on Sample A. The sampledetector source-sample distances were optimized for a spatial resolution of2.06µm/px (8.7 µm 3 /vx) with magnifications of 4.0×. The 3D images obtained were composed of 885×885×999 vx (elementary image volume) with 32-bit grey-scale resolution. Acquisition time was 280min for 1601 projections (8 s per projection) together with around 200 reference images (blanks). Tomographic volume reconstructions were performed using the ZEISS XRM software. Data processing was performed using ImageJ ® and Avizo 9.2 ® softwares.

HRXCT at University of Strathclyde (Sample B)

The HRXCT scans on Sample B were performed at the University of Strathclyde, Glasgow (UK) using an industrial Nikon XTH 320/225 system, equipped with a 225 kV Xray tube, a microfocus multimetal target, and a 2000×2000 px flat panel photodetector (cell size 0.2×0.2 mm), leading to volumes of 2000×2000×2000 vx (Table 1). Two different scan conditions were tested on Sample B.One scan of the complete sample (Fig. 2) was performed using a silver target under an accelerating voltage of 160 kV, 71 µA current corresponding to a power of 11.4W, for a spatial resolution of 25µm/px(15625 µm 3 /vx). The exposure time for each of the 3141 projections was 0.708 s, leading to a scan time of 37 min (1 frame per projection). The second scan focusing on a 1.4×1.4×1.4 mm region of interest of the sample was performed using a silver target under an accelerating voltage of 160 kV, 46 µA current, corresponding to a power of 7.4W, for a spatial resolution of7.7 µm/px(456 µm 3 /vx). The exposure time for each of the 3141 projections was 1.415 s, leading to a scan time of 75 min (1 frame per projection). X-ray tube conditions would not saturate photodetector, consequently no metallic filter was required during the scans. Volume reconstructions were carried out with CT Pro 3D software. Both 3D dataset were treated using Avizo® 9.2.0, noise was corrected by using a median filter that uses morphological operators to set the voxelsvalue to the median for the defined neighborhood (3 px 2D square). After separation of phases, the remaining selected voxelssmaller than 100 connected voxels in 3D were removed from the selection to ensure no noise was left.

HRXCT at Université de Lorraine (Samples C-I)

HRXCT scans of Samples C to I were acquired at the Université de Lorraine, Vandoeuvre-lès-Nancy (France) with a Phoenix Nanotom S scanner (Table 1).Data processing was carried out using Avizo® 9.2.0. The detector used was a CCD Hamamatsu, with 2300×2300 px.For Samples C, D, E, F, G, H and I, the source-sample distance was 12.5, 55, 28, 6, 6, 10 and 10 mm respectively. The accelerating voltage was 100, 115, 100, 90, 90, 110 and 110 kV respectively. The current was 100, 100, 65, 100, 115, 115 and 115 µA respectively. The following number of projections were carried out: 1500 (as averages of 4 projections of 1000 ms each), 2000 (as averages of 3 projections of 1000 ms each), 2000 (as averages of 5 projections of 750 ms each), 2000 (as averages of 3 projections of 1250 ms each), 1500 (as averages of 6 projections of 750 ms each), 1200 (as averages of 6 projections of 750 ms each) and 1200 (as averages of 6 projections of 750 ms each) respectively. This led to a scan time of 100, 100, 125, 125, 125, 105and 105min. respectively. The spatial resolution was 1.25 µm/px (1.95 µm 3 /vx), 1.96 µm/px (7.5µm 3 /vx), 3.5 µm/px (42 µm 3 /vx), 0.77 µm/px (0.45 µm 3 /vx), 0.77 µm/px (0.45 µm 3 /vx), 1 µm/px (1 µm 3 /vx) and 1 µm/px (1 µm 3 /vx) respectively.

Results and discussion

Identification and 3D distribution of fluid and melt inclusions

For Sample A, the density of the various solid components of the silicate melt inclusion(glass: d ~ 2.7 g.cm -3 ; clinopyroxene: d = 3.3 g.cm -3 ; spinel: d = 3.6 g.cm -3 ) contrasts sufficiently with that of the host olivine to allow to proper segmentation of the whole silicate melt inclusion (Fig. 1).Similarly, for Samples B to I, density differences between the liquid phase of aqueous and/or hydrocarbon-bearingfluid inclusions(d ≈ 1g.cm -3 and 0.7-1g.cm -3 respectively), and their host minerals (quartz: d = 2.6 g.cm -3 ; garnet: d = 3.5-4.3 g.cm -3 ; emerald: d = 2.7-2.9 g.cm -3 ; wolframite: d = 7.1-7.5 g.cm -3 and feldspar = 2.6 g.cm -3 ) are high enough to induce detectable contrasts of X-ray attenuation, as visible on 2D slices (Fig. 23456789).HRXCT 3D reconstructions allow to identify isolated inclusions (Fig. 1,4,5,7-9, Samples A,D,E,G-I) and 2D and 3D fluid inclusionclusters (Fig. 2,3,6, Samples B,C,F). Based on the analysis of relatively small fluid inclusions and when a resolution of ~ 1 µm 3 /vx is achieved (Fig. 3,6, Samples C,F) the minimum size of the fluid inclusions that can be clearly identified using HRXCT is about 5 µm in diameter (assuming spherical shape). In Sample E,HRXCT 3D reconstruction shows that monophase liquid aqueous fluid inclusionsare developed parallel to the dislocations in one of the arms of the trapiche emerald (Fig. 5). In Sample F, HRXCT 2D and 3D reconstructions show thatmost fluid inclusions are elongated perpendicular to the main sulfide veinlet and parallel to the c-axis.

Here, fluid inclusions and silicate melt inclusionswere successfully imaged by HRXCT in both transparent (olivine, natural and synthetic quartz, demantoid garnet, "trapiche" emerald, feldspar) and opaque (wolframite) minerals.The present results complement previous studies in which fluidand melt inclusionswere imaged by HRXCT in quartz, olivine, sphalerite, pyrite and pyrrhotite [START_REF] Nakashima | Three-dimensional imaging of arrays of fluid inclusionsin fluorite by high-resolution X-ray CT[END_REF][START_REF] Kyle | Contributions of high resolution X-ray computed tomography to ore studies[END_REF]Kyle and Ketcham, 2007a,b, 2008[START_REF] Noiriel | Resolving time-dependent evolution of pore-scale structure, permeability and reactivity using X-ray microtomography[END_REF][START_REF] Nowecki | Tracing seawater evaporation and its role in the formation of sedimenthosted stratiform copper deposits[END_REF][START_REF] Pamukcu | Quantitative 3D petrography using X-ray tomography 4: Assessing glass inclusion textures with propagation phase-contrast tomography[END_REF][START_REF] Pamukcu | Melt inclusion shapes: Timekeepers of short-lived giant magma bodies[END_REF][START_REF] Gaetani | Reconstructing magma storage depths from olivine-hosted melt inclusions: Do vapor bubbles matter?[END_REF][START_REF] Farley | Olivine barometry based on X-ray computed tomography of fluid inclusions[END_REF]. Common geologic fluids differ in linear X-ray attenuation coefficient from common minerals by several orders of magnitudes, indicating that HRXCT is theoretically suitable for identification of fluid inclusionsin most natural and synthetic crystals [START_REF] Kyle | Application of high resolution X-ray computed tomography to mineral deposit origin, evaluation, and processing[END_REF].HRXCT is therefore a powerful technique for non-destructive reconnaissance study of fluid and melt inclusion study in many types of minerals, including: (i) opaque minerals for which observation of inclusions needs access to an infrared camera and sometimes are not even for suited for infrared cameras [START_REF] Lüders | Contribution of infrared microscopy to studies of fluid inclusionshosted in some opaque ore minerals: possibilities, limitations, and perspectives[END_REF];

(ii) fragile minerals (e.g. carbonate, gypsum) subjected to fluid inclusionstretching during sample preparation [START_REF] Bourdet | Strain response and re-equilibration of CH 4 -rich synthetic aqueous fluid inclusions in calcite during pressure drops[END_REF]) and (iii) gemstones for which the presence of fluid inclusions impacts their commercial value [START_REF] Giuliani | The geology of gems and their geographic origin[END_REF]. HRXCT reconstruction could be a prerequisite before any sectioning of the sample or destructive analysis, for example before laser ablation -inductively coupled plasma -mass spectrometry analysis (to locate fluid inclusions to be ablated in opaque minerals; [START_REF] Kouzmanov | Direct analysis of ore-precipitating fluids: combined IR microscopy and LA-ICP-MS study of fluid inclusionsin opaque ore minerals[END_REF][START_REF] Colin | Mechanisms of magma degassing at mid-oceanic ridges and the local volatile composition ( 4 He-40 Ar-CO 2 ) of the mantle by laser ablation analysis of individual MORB vesicles[END_REF], or crushing (to evaluate the volume of fluid that can be extracted for further elemental of isotopic analysis; [START_REF] Nowecki | Tracing seawater evaporation and its role in the formation of sedimenthosted stratiform copper deposits[END_REF]. HRXCT reconstruction could help defining the relationships between the inclusions and their host crystals and their primary or secondary originif the orientation of the crystal is known [START_REF] Roedder | Fluid Inclusions[END_REF]. Finally,3D mapping of fluid inclusionplanes by HRXCT could be of great help for microtectonic characterization and paleostress analysis [START_REF] Nakashima | Three-dimensional imaging of arrays of fluid inclusionsin fluorite by high-resolution X-ray CT[END_REF][START_REF] Lespinasse | Microfissural mapping of natural cracks in rocks: Implications for fluid transfers quantification in the crust[END_REF].

Identification of the different phases within fluid and melt inclusions

For Sample A,the respective densities of the different phases within the silicate melt inclusion(vapor bubble, glass, clinopyroxene and spinel) are sufficiently contrasted to allow proper thresholding and labelling, and to reconstruct the complex distribution of the vaporbubble and the solidswithin the glass matrix (Fig. 1). The multiple clinopyroxene and spinel crystals are mostly located close to the walls of the inclusion or close to the vaporbubble, as also seen by secondary electron microscopy. Mineral crystallization at the vaporbubble rim implies a fluid saturation event and discards, by the same, a possible free volume vaporbubble (known to be due to the melt-glass transition).Within two-phase aqueous and hydrocarbon-bearingfluid inclusions, the density contrast between the vapor phase (d ≈ 10 -2 -10 -1 g.cm -3 ) and the liquid phase(s) (d ≈ 1 g.cm -3 ) is high enough to allow their proper identification and reconstruction (Fig. 234,6-9, Samples B-D,F-I). For Samples G and H, the two liquid phases (oil and aqueous solution) and the solid bitumen are indistinguishable, probably due to their similar density(Fig. 78). For Samples C and F, no vapor phase could be identified in relatively small inclusions (<10 µm in diameter assuming spherical shape, Fig. 3,6).The minimum diameter of the vapor phase allowing to firmly discriminate the liquid phase from the vapor phase is about 2 µm.

Here, multiphase silicate melt inclusionsand one phase (liquid) and two-phase (liquid + vapor) aqueous and hydrocarbon-bearingfluid inclusionswere successfully imaged.Therefore 3D HRXCT imaging can not only identify the presence and location of fluidand melt inclusionsbut also can provide information about the number, the composition, the shape andthe spatial distribution of their different phases. This has direct implications for the nature of the parental melt and trapping conditions of crystallized silicate melt inclusions(e.g., homogeneous or heterogeneous) and on the origin of the vaporbubble (freevolume or fluid saturation) as well as for the trapping conditions and the nature of the fluids trapped in fluid inclusions.As a complement to previous studies [START_REF] Nakashima | Three-dimensional imaging of arrays of fluid inclusionsin fluorite by high-resolution X-ray CT[END_REF][START_REF] Kyle | Contributions of high resolution X-ray computed tomography to ore studies[END_REF]Kyle and Ketcham, 2007a,b, 2008[START_REF] Noiriel | Resolving time-dependent evolution of pore-scale structure, permeability and reactivity using X-ray microtomography[END_REF][START_REF] Nowecki | Tracing seawater evaporation and its role in the formation of sedimenthosted stratiform copper deposits[END_REF][START_REF] Pamukcu | Quantitative 3D petrography using X-ray tomography 4: Assessing glass inclusion textures with propagation phase-contrast tomography[END_REF][START_REF] Pamukcu | Melt inclusion shapes: Timekeepers of short-lived giant magma bodies[END_REF][START_REF] Gaetani | Reconstructing magma storage depths from olivine-hosted melt inclusions: Do vapor bubbles matter?[END_REF][START_REF] Farley | Olivine barometry based on X-ray computed tomography of fluid inclusions[END_REF], this is the first time that liquid hydrocarbon is identified in fluid inclusionsand that different solids are characterized within a melt inclusionby HRXCT. Further investigation could include the identification of daughter minerals within aqueous fluid inclusionsand the characterization of gas-bearing inclusions like monophase vapor CH 4 -N 2 inclusions and three-phase (aqueous solution, liquid CO 2 and vapor CO 2 ) aquocarbonic inclusions. Further improvements in phase discrimination and identificationcould include more systematic use of propagation phase-contrast tomography [START_REF] Pamukcu | Quantitative 3D petrography using X-ray tomography 4: Assessing glass inclusion textures with propagation phase-contrast tomography[END_REF][START_REF] Sayab | Three-dimensional textural and quantitative analyses of orogenic gold at the nanoscale[END_REF].

Shape and volumetric reconstruction of fluid and melt inclusions

HRXCT reconstruction of the analyzed inclusions revealsa broad range in shape (nearly spherical, elongated, tubular or complex; Fig. 123456789, Samples A-I). For Sample D, the morphology of the fluid inclusioncavity is sufficiently well reconstructed that it is possible to identify a negative crystal shape, with polygonal surfaces parallel to the host crystal faces(Fig. 4). Besides polygonal faces, the wall of the fluid inclusion shows a rough surface.In some cases, the vapor phase of both aqueous and hydrocarbon-bearingfluid inclusions (Samples B,D,G,I, Fig. 2,4,7,9) and the vapor bubble of the silicate melt inclusion(Sample A, Fig. 1) are located in such places that they are slightly flattened at the contact of the inclusion wall. This configuration usually hampers accurate optical estimation of the volume of the vapor phase.

As for secondary electron microscopy imaging, HRXCT 3D reconstruction of the silicate melt inclusionshows that the multiple clinopyroxene and spinel crystals are euhedral (Fig. 1, Sample A).

The 3D reconstruction also allows the calculation of the relative volume of the different phases. For Sample A (Fig. 1) the calculations return the following volume percentages for the different phases within the silicate melt inclusion: glass (67.5 vol.%), clinopyroxene (20.4 vol. %, as the sum of all clinopyroxene crystals), vaporbubble (7.2 vol.%), spinel (4.9 vol.%, as the sum of all spinel crystals). For Sample D (Fig. 4), the demantoid garnet has a calculated total volume of 896.1 mm 3 . The fluid inclusionrepresents 6.2 vol.% of the total volume of the garnet. The liquid phase has a calculated volume of 52.16 mm 3 and the vapor phase has a calculated volume of 3.52 mm 3 . This corresponds to a φ vap value of 6.3%.For Sample G (Fig. 7), the calculated φ vap value is 9.2%.For Sample B (Fig. 2) preliminary tests of the sensitivity of thecalculated phase volume to threshold values and to scanning resolution were carried out (Table 2). The volumetric calculations using a scanning resolution of 25 µm/px (15625 µm 3 /vx) and optimal threshold values return a φ vap value ranging between 13% and 24% (average 20.1%) for the population of imaged inclusions (Table 2). When scanned with a resolution of 7.7 µm/px (456 µm 3 /vx) and using optimal threshold values the calculated φ vap valueis of 24% for fluid inclusion#3 while the 25 µm/px (15625 µm 3 /vx) resolution scan returns a φ vap value of 22.5%. At a resolution of 7.7 µm/px (456 µm 3 /vx), when the threshold value is changed by 5%, the calculations return a φ vap value of 76.2% (Table 2). Therefore, it appears that the volumetric reconstruction is sensitive to the scanning resolution (the higher the better) and most importantly to the choice of the threshold values during the post-processing stage. For Sample C, the calculated φ vap value of relatively large inclusions (>25 µm in diameter assuming spherical shape)is between 40 and 45%, which is compatible with the expectedvalue of 42% (considering known P-T-V-x conditions of trapping).For Sample I, 3D reconstruction of the hydrocarbon-bearingfluid inclusionusing confocal laser scanning microscopy and visualization through ImageJ 3D Viewer returns aφ vap value of 10 ± 2%, while HRXCT 3D reconstruction of the sameinclusion returns a compatibleφ vap valueof 9.8%.For samples B, C, F, H and I, the reconstructed surfaces ofvapor phases are slightly more complex than spherical or flattened shapes observed under optical microscope (Fig. 2,3,6,8,9). Those differences arise from the thresholding and segmentation procedures and would induce more discrepancies between actual and reconstructed shapes and volumes when the resolution and density contrasts are the lowest. However, based on independent analysis of Samples C and I, this does not seem to introduce significant bias on volume estimation.

The present results show that HRXCT reconstruction allows 3D visualization of the fluid and melt inclusions shape which may help correcting for projection bias under the optical microscope [START_REF] Bakker | Estimation of volume fractions of liquid and vapor phases in fluid inclusions, and definition of inclusion shapes[END_REF] and better identify post-trapping deformation (i.e. stretching, necking down). 3D reconstruction may also overcome the frequent limitation in estimation of vapor phase volume when the vaporbubble is flattened or when the shape of the inclusion is complex.Finally, 3D volumetric reconstruction of melt inclusions by HRXCT could be used as a promising alternative approach to post-entrapment modification correction and calculation of the parental melt composition without inducing leakage of volatiles by heating and related diffusion [START_REF] Créon | New method for initial composition determination of crystallized silicate melt inclusions[END_REF]. Further improvement would consist of more in-depth sensitivity tests on various parameters andquantifying the uncertainties in volume calculation [START_REF] Lin | Quantifying and minimising systematic and random errors in X-ray micro-tomography based volume measurements[END_REF]. Also, one could test the volume changes in the fluid inclusion cavities induced by freezing of the liquid phase in the case of inclusions hosted in fragile minerals like carbonates. This tests would require adaptation of a microthermometric stage in the HRXCT setup. It could be also interesting to test if sample heating due to X-ray absorption could induce measurable change in the volume of the vapor phase. Here, the present observations show no visible variation of the vapor phase diameter between radiographs taken before and during the experiments.Similarly, the vapor phase has to remain immobile during the experiments. Consequently and considering that the vapor phase tends to move in the liquid phase in many types of fluid inclusions, the applicability of the HRXCT is inherently limited to fluid inclusions with relatively large vapor phase, or trapped morphologically.

Conclusions

Collectively, the present results complement significantly the sparse previous studies of HRXCT characterization of fluid and melt inclusions. HRXCT can definitely be a useful and versatile tool for non-destructive characterization of the 3D distribution of fluid and melt inclusions, their shape and the volume fractions of their different phases, within both transparent and opaque minerals. Among other applications, HRXCT is a promising powerful method for fluid and melt inclusion petrography, paleostress analysis and P-T-V-x reconstruction.Future developments should focus on: (i) achieving higher spatial resolution and more efficient phase discrimination with more sophisticated data processing and experimental setups and (ii) more quantitative approaches to fluid and melt inclusion distribution and volumetric reconstruction including better estimation of accuracy and precision of the calculated volumes.

Table captions

Table . 1

Figure captions

  : Summary of key parameters for the experiments. "Phases" refer to the different phases identified at room temperature within the inclusions. MI: melt inclusion; FI: fluid inclusion, IEM Institute of Experimental Mineralogy, Cpx: clinopyroxene; Spl: spinel; Vap.: vapor; Aq. sln.: solution; sb.: solid bitumen; px: pixel; vx: voxel. * corresponds to the high resolution scanning in the region of interest shown in Fig. 2 (fluid inclusion#3). Table 2: Preliminary tests of the sensitivity of thecalculated phase volume to threshold values and to scanning resolution, carried out on fluid inclusions (FI) from Sample B.The fluid inclusions are numbered according to Fig. 2. * corresponds to calculated volumes with optimal thresholding value. **corresponds to calculatedvolumes by varying the threshold values by 5% during post-processing stage. The scanning resolution for all fluid inclusions except *** is 25µm/px(15625 µm 3 /vx). *** corresponds to calculatedvolumesusing a scan with a resolution of7.7 µm/px (456 µm 3 /vx). FI tot : total fluid inclusion volume; Vap.: vapor phase; Liq.: liquid phase; φ vap : volumetric fraction of the vapor phase to the entire inclusion; ∆: relative difference between measurements with different threshold values; px: pixel; vx: voxel.

Fig. 1 :

 1 Fig.1:Silicate melt inclusion (SMI)in olivine (Sample A). (A) An olivine phenocryst (1.0 mm

Fig. 2 :

 2 Fig.2:Aqueousfluid inclusions in synthetic quartz (Sample B). (A) Photograph of Sample B

  From (C) to (F) the spatial resolution is7.8 µm/px(456 µm 3 /vx).(D) Equivalent 2Dview after use of threshold and labelling.The darker pixelsbelonging to the vaporphase are gathered as green material, brighter black pixels belonging to liquidphase are gathered as blue material, while brighter grey pixels belonging to quartz host are removed from the dataset. (E) Equivalent surface view in 3D with no perspective enabled.(F) Surface view of the vapor phase.

Fig. 3 :

 3 Fig.3:Synthetic aqueous fluid inclusionstrapped in a natural quartz (Qtz) (Sample C). (A)A

Fig. 4 :

 4 Fig.4: Aqueous fluid inclusion in "demantoid" garnet (Sample D). (A) A demantoid garnet

Fig. 5 :

 5 Fig.5: Aqueous fluid inclusions in "trapiche" emerald (Sample E). (A) Hand specimen. The

Fig. 6 :

 6 Fig.6:Aqueous fluid inclusions in wolframite (Wf)(Sample F). (A) Typical two-phase liquid

Fig. 7 :

 7 Fig.7:Hydrocarbon-bearingfluid inclusion in synthetic quartz (Qtz) (Sample G). (A) The

Fig. 8 :

 8 Fig.8:Hydrocarbon-bearingfluid inclusionin synthetic quartz (Qtz) (Sample H). (A) The

Fig. 9 :

 9 Fig.9: Hydrocarbon-bearingfluid inclusionin feldspar (Fsp) (Sample I). (A) The hydrocarbon-

Acknowledgments

This work was supported by the French National Research Agency through the national program "Investissements d'avenir" with the reference ANR-10-LABX-21-01 / LABEX RESSOURCES21 and by a CNRS-INSU-CESSUR grant.N. Jacquemet (independent researcher in geochemistry and mass transport; nicolas-jacquemet.com) produced and provided Sample C. K. Kouzmanov (Université de Genève) provided access to infrared camera for observation of Sample F. L. Créon thanks the project PO-5 "Innovative application of modern techniques for geothermal exploration by the integration of geological, geochemical and geophysical methods, study case of Los Humeros volcanic field", as part of the CeMie-GEO Consortium No. 2007032 funded by Fondo de Sustentabilidad SENER-CONACYT. N. Beaudoin and the X-ray Computed Tomography scanner at the University of Strathclyde are funded by the Scottish Funding Council's Oil and Gas Innovation Centre and the University of Strathclyde. Mohammad Sayab and an anonymous reviewer provided insightful comments on the manuscript and are greatly thanked as well as Marie-Camille Caumon and Klaus Metzger for their careful editorial handling.

Vap.

Liq


Cristina Bazgan
email: bazgan@lamsade.dauphine.fr

Thomas Pontoizeau
email: thomas.pontoizeau@lamsade.dauphine.fr

Zsolt Tuza
email: tuza@dcs.uni-pannon.hu

Finding a potential community in networks

Keywords: graph, complexity, algorithm, independent set, inapproximability

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Community detection is a well established research field in the area of social networks [START_REF] Buluç | Recent advances in graph partitioning[END_REF][START_REF] Easley | Networks, Crowds, and Markets: Reasoning About a Highly Connected World[END_REF][START_REF] Fortunato | Community detection in graphs[END_REF][START_REF] Newman | Detecting community structure in networks[END_REF][START_REF] Schaeffer | Graph clustering[END_REF]. It can find many applications in this area with the recent development of social networks like Facebook or Linkedin. A social network can be easily modeled by a graph in which vertices represent members and edges represent relationships between those members.

There are several ways to define a community. Intuitively, a community corresponds to a dense subgraph, that is to say a subgraph with a lot of edges. If a community is defined as a group of maximum size such that all members know each other, it corresponds to the well known NP-hard problem of finding a maximum clique. However, such a condition is strong and is not always relevant to describe a community.

Another way to define a community is to relax the strong condition of a clique and focus on the distance between members of a social network. Different measures have been studied to describe it. Luce introduced in [START_REF] Luce | Connectivity and generalized cliques in sociometric group structure[END_REF] the notion of k-cliques while Mokken extended this notion in [START_REF] Mokken | Cliques, clubs and clans[END_REF] by defining k-clubs. A k-clique (resp. a k-club) of G is a subgraph S in which any two vertices are at distance at most k in G (resp. in the subgraph induced by S). The standard term 'clique' means both a 1-clique and a 1-club.

With the recent development of social networks and particularly online dating services, it could be interesting to investigate the detection of some group of people who do not know each other, but are related by their other relationships. Such a group could be considered as a 'potential' community since it does not form a community in the first place, but could become one due to their proximity. This may find various applications in online dating and meet-up services in which members expect not to know the other members.

We propose to define in this paper potential communities as independent k-cliques, for an integer k ≥ 2. An independent k-clique is an independent set in which any two vertices are at distance at most k in the original graph. Contrary to a k-club, the distance between two vertices must be realized via vertices outside of the subgraph. This definition can have some interesting applications, for instance in automated referee/reviewer seeking. The task would be to identify potential referees/reviewers in an academic community: any two referees should not be directly linked, and at the same time they should not be far away in the network to guarantee the closeness to the content and quality of the reviews. In this paper, we study the problem of finding an independent 2-clique of maximum size.

We investigate the complexity of this problem in several graph classes. Since this problem is close to finding an independent set of maximum size, we also compare the hardness of the two problems. Figure 1 summarizes the results we prove in the paper.

The paper is structured as follows. In Section 2 we introduce formally some notation and definitions. In Section 3 we show that the complexity of Max Independent 2-Clique jumps from polynomial-time solvable to NP-hard when the input class is extended from planar graphs to apex graphs. In Section 4 we present polynomial algorithms to solve Max Independent 2-Clique in some graph classes. In Section 5 we show NPhardness and inapproximability of Max Independent 2-Clique in some other graph classes. Conclusions are given in Section 6.

Preliminaries

In this paper, all considered graphs are undirected. The complement G = (V, E) of a graph G = (V, E) is the graph in which uv ∈ E if and only if uv / ∈ E, for all vertex pairs u, v ∈ V . A k-cycle is a cycle of length k. A block is a maximal biconnected subgraph. The maximum degree of a vertex in a graph G will be denoted by the usual notation ∆(G).

We recall that a clique in a graph is a set of mutually adjacent vertices. A set of vertices is called a 2-clique if any two vertices of the set are at distance at most 2 in G. An independent set in a graph is a set of vertices such that no two of them are joined by an edge. An independent 2-clique is a subset of vertices which is an independent set and a 2-clique at the same time.

In this paper we are interested in the following optimization problem:

Max Independent 2-Clique Input: A graph G = (V, E). Output: A subset S ⊂ V which is an independent 2-clique of maximum size.
The Max Independent 2-Clique problem is closely related to the well known problem of finding an independent set of maximum size, named Max Independent Set. We sometimes make reductions from the problem Max Clique which refers to the problem of finding a clique of maximum size.

Given a graph G, the standard notation for the maximum size of an independent set in G is α(G). The maximum number of vertices in an independent 2-clique of G will be denoted by α =2 (G). The subscript '=2' intends to express that the distance between any two vertices of the independent set is exactly 2. Remark that, by definition, α(G) ≥ α =2 (G).

Note that α =2 (G) ≥ 2 whenever at least one connected component of G is not a complete graph. Indeed, any such component contains two vertices at distance exactly two, hence forming an independent 2-clique of size 2. Moreover, if G is disconnected and has components G 1 , . . . , G p then

α =2 (G) = max 1≤i≤p α =2 (G i )
For these reasons we assume throughout that G is a non-complete, connected graph (although some of the algorithms also need to handle disconnected graphs temporarily).

We define the problem Independent 2-Clique as the decision version associated to Max Independent 2-Clique. Its input is a graph G = (V, E) and an integer k, and the question is whether there exists an independent 2-clique of size at least k in G.

Some classes of graphs

We study Max Independent 2-Clique in several graph classes. Some definitions are given next. A cactus is a graph in which each edge occurs in at most one cycle. A (C 3 , C 6 )-free graph is a graph containing no triangle C 3 and no induced cycle of length 6. A d-regular graph is a graph in which all vertices are of degree d. An interval graph is a graph for which there exists a family of intervals on the real line and a bijection between the vertices of the graph and the intervals of the family in such a way that two vertices are joined by an edge if and only if the intersection of the two corresponding intervals is non-empty. A graph is a threshold graph1 if it can be constructed from the empty graph by a sequence of two operations: insertion of an isolated vertex, and insertion of a dominating vertex (i.e., a vertex adjacent to all the other vertices). A cograph is a graph that can be generated from the single-vertex graph by (repeated applications of) complementation and vertex-disjoint union. A split graph is a graph whose vertex set can be partitioned into two subsets, one inducing an independent set S and the other one inducing a clique K. A bipartite graph is a graph in which the set of vertices can be partitioned into two independent sets. We denote by K p,m the complete bipartite graph with p and m vertices in its vertex parts. The line graph of a graph G is the graph L(G) whose vertices represent the edges of G, and two vertices of L(G) are adjacent if and only if the corresponding two edges of G share a vertex. A connected graph is a tree if it does not contain any cycle. A graph is planar if it can be embedded in the plane (drawn with points for vertices and continuous curves for edges) without crossing edges. A graph is outerplanar if it has a crossing-free embedding in the plane such that all vertices are on the same face. A graph is k-outerplanar if for k = 1, G is outerplanar and for k > 1 the graph has a planar embedding such that if all vertices on the exterior face are deleted, the connected components of the remaining graph are all (k -1)-outerplanar. A graph G is apex if it contains a vertex v such that Gv is planar. A family of graphs on n vertices is δ-dense if it has at least δn 2 2 edges. It is everywhere-δ-dense if the minimum degree is at least δn. A family of graphs is dense (resp. everywhere-dense) if there is a constant δ > 0 such that all members of this family are δ-dense (resp. everywhere-δ-dense).

Parametrized complexity

A parameterized problem is a subset Q ⊂ Σ × N where the first component is a decision problem and the second component is called the parameter of the problem. The class FPT contains every parameterized problem Q ⊂ Σ×N for which the question 'Does (x, k) belong to Q?' can be decided by an algorithm that runs in f (k) • |x| O(1) time where (x, k) ∈ Σ × N and f is a computable function.

Let Q 1 , Q 2 ⊂ Σ × N be two parameterized problems. We say that Q 1 FPT-reduces to Q 2 if there exists two computable functions f and g and an algorithm that takes as input an instance (

x 1 , k 1 ) ∈ Σ × N and outputs a new instance (x 2 , k 2 ) ∈ Σ × N in f (k 1 ) • |x 1 | O(1)
time such that:

• (x 1 , k 1 ) ∈ Q 1 ⇔ (x 2 , k 2 ) ∈ Q 2 • k 2 ≤ g(k 1 )
Downey and Fellows [START_REF] Downey | Fixed-parameter tractability and completeness II: On completeness for W[1[END_REF] introduced the W -hierarchy as different classes of complexity for parameterized problems. A way to prove that a parameterized problem belongs to W [t] is to construct an FPT-reduction from this problem to a problem known to be in

W [t]. A parameterized problem is W [t]-hard if every problem of W [t] FPT-reduces to it.

Approximation, L-reduction, and E-reduction

Given an optimization problem in NPO and an instance I of this problem, we denote by |I| the size of I, by opt(I) the optimum value of I, and by val(I, S) the value of a feasible solution S of instance I. The performance ratio of S (or approximation factor) is r(I, S) = max val(I,S) opt(I) , opt(I) val(I,S) . The error of S, denoted by ǫ(I, S), is defined as ǫ(I, S) = r(I, S) -1.

For a function f , an algorithm is an f (|I|)-approximation, if for every instance I of the problem, it returns a solution S such that r(I, S) ≤ f (|I|).

For proofs concerning APX-hardness, we shall use an approximation-preserving reduction, called L-reduction, which was introduced by Papadimitriou and Yannakakis in [START_REF] Papadimitriou | Optimization, approximation, and complexity classes[END_REF]. Let A and B be two optimization problems. Then A is said to be L-reducible to B if there are two constants a, b > 0 such that:

1. there exists a function, computable in polynomial time, which transforms each instance I of A to an instance

I ′ of B such that opt B (I ′ ) ≤ a • opt A (I),
2. there exists a function, computable in polynomial time, which transforms each solution S ′ of I ′ to a solution S of I such that |val(I, S)

-opt A (I)| ≤ b • |val(I ′ , S ′ ) - opt B (I ′ )|.
We recall that a problem is in APX if there exists a polynomial-time approximation algorithm for the problem with an approximation ratio bounded by a constant. A problem is APX-hard if every problem of APX L-reduces to that problem.

The notion of an E-reduction (error-preserving reduction) was introduced by Khanna et al. [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF]. A problem A is called E-reducible to a problem B, if there exist polynomial-time computable functions f and g, and a constant β such that • f maps an instance I of A to an instance I ′ of B such that opt(I) and opt(I ′ ) are related by a polynomial factor, i.e. there exists a polynomial p such that opt(I ′ ) ≤ p(|I|) • opt(I),

• g maps any solution S ′ of I ′ to a solution S of I such that ǫ(I, S)

≤ β • ǫ(I ′ , S ′ ).
An important property of an E-reduction is that it can be applied uniformly to all levels of approximability; that is, if A is E-reducible to B and B belongs to C then A belongs to C as well, where C is a class of optimization problems with any kind of approximation guarantee (see [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF]).

Independent 2-Clique belongs to W[1]

From the parametrized complexity point of view, it is interesting to notice the following fact.

Theorem 1 Independent 2-Clique belongs to W [1] on general graphs.

Proof. We construct an FPT-reduction from Independent 2-Clique to Clique. Let G = (V, E) be an instance of Independent 2-Clique. We construct an instance of Clique by considering the graph G ′ = (V, E ′ ) in which xy ∈ E ′ if and only if x and y are exactly at distance 2 in G. It is easy to see that there is an independent 2-clique of size k in G if and only if there is a clique of size k in G ′ . Since Clique belongs to W [START_REF] Alekseev | On the local restrictions effect on the complexity of finding the graph independence number[END_REF] (see [START_REF] Downey | Fixed-parameter tractability and completeness II: On completeness for W[1[END_REF]), Independent 2-Clique also belongs to W [START_REF] Alekseev | On the local restrictions effect on the complexity of finding the graph independence number[END_REF]. ✷

Complexity jump from planar graphs to apex graphs

According to [START_REF] Garey | Some simplified NP-complete problems[END_REF], Max Independent Set is known to be NP-hard in planar graphs, and thus also in apex graphs. On the other hand, we prove that Max Independent 2-Clique is polynomial-time solvable on planar graphs but NP-hard on apex graphs. This shows that inserting or removing a single vertex in a graph may dramatically change the complexity of Max Independent 2-Clique.

Theorem 2 Max Independent 2-Clique is NP-hard on apex graphs.

Proof. We establish a polynomial reduction from Max Independent Set on cubic planar graphs, which is proved to be NP-hard in [START_REF] Garey | Some simplified NP-complete problems[END_REF], to Max Independent 2-Clique on apex graphs. Let G = (V, E) be a cubic planar graph, an instance of Max Independent Set.

The instance G ′ = (V ′ , E ′ ) of Max Independent 2-Clique is defined by inserting an additional vertex z that is adjacent to every vertex of V . It is easy to see that {z} itself is a one-element non-extendable independent 2-clique, while the independent 2-cliques of G ′ not containing z are precisely the independent sets of G. ✷ Theorem 2 implies another interesting result: Corollary 3 Max Independent 2-Clique is NP-hard on the class of graphs of average degree at most 5.

Proof. Cubic graphs on n vertices have 3n/2 edges, thus the graph constructed in the proof of Theorem 2 is of order n + 1 and has 5n/2 edges, yielding average degree less than 5. ✷ In order to prove that Max Independent 2-Clique is polynomial-time solvable on planar graphs, we use a famous theorem introduced by Courcelle in [START_REF] Courcelle | The monadic second-order logic of graphs III: tree-decompositions, minors and complexity issues[END_REF] which states that any problem expressible in Monadic Second-Order Logic is linear-time solvable for graphs of bounded treewidth. This allows to show first the following: Theorem 4 Max Independent 2-Clique is linear-time solvable on graphs with bounded treewidth.

Proof. We observe that Max Independent 2-Clique is expressible in Monadic Second-Order Logic:

maxI2C(S) := max S {|S| : ∀x∀y(Sx ∧ Sy) → (¬edg(x, y) ∧ (∃z, edg(x, z) ∧ edg(y, z)))}
Since any problem expressible in Monadic Second-Order Logic is linear-time solvable for graphs of bounded treewidth (see [START_REF] Courcelle | The monadic second-order logic of graphs III: tree-decompositions, minors and complexity issues[END_REF]), α =2 can be determined in linear time in graphs of bounded treewidth. ✷

Based on this result, we prove the following.

Theorem 5 Max Independent 2-Clique is polynomial-time solvable on planar graphs.

Proof. Let G = (V, E) be a planar graph and v ∈ V any vertex. Then all the other vertices in an independent 2-clique S containing v are at distance exactly 2 apart from v. Further, the 2-clique property for S \ {v} is ensured by vertices within distance at most 3 from v. Thus, the vertices relevant for S to be an independent 2-clique induce a subgraph G ′ in G such that G ′ belongs to the class of '4-outerplanar' graphs. Graphs which are 4-outerplanar have treewidth at most 11 (more generally, all k-outerplanar graphs have treewidth at most 3k -1, due to [START_REF] Bodlaender | A partial k-arboretum of graphs with bounded treewidth[END_REF]). Then, using Theorem 4, a polynomial-time algorithm for Max Independent 2-Clique in planar graphs consists in solving the problem for all subgraphs G ′ (which have treewidth at most 11) defined from each vertex v of G and choosing a solution of maximum size. ✷

In order to get the following result we can use the elementary Five Color Theorem for planar graphs, and even Euler's formula without any further topological considerations, but we prefer to cite in our proof the Four Color Theorem because it leads to a better kernel.

Theorem 6

The parameterized problem associated with Max Independent 2-Clique with the natural parameter is in FPT on apex graphs.

Proof. Let G = (V, E) be an apex graph and x ∈ V a vertex such that Gx is planar. Since any planar graph is 4-colorable [START_REF] Appel | Every planar map is four colorable: Part I[END_REF], the size of an independent set in G

[N(x)] is at least |N (x)|
4 , and so is the size of an independent 2-clique in G. Thus, considering the parameter k, if |N(x)| ≥ 4k, then the answer is yes.

If now |N(x)| < 4k, let S be any independent 2-clique and v ∈ S any vertex. As discussed in the previous proof, the 2-clique property for S \ {v} is ensured by vertices within distance at most 3 from v in Gx, and by vertices in the closed neighborhod N[x] of x. For this reason, for each vertex v ∈ V , we consider the subgraph induced by the set of all vertices at distance at most 3 from v and include {x} ∪ N(x). This subgraph has treewidth at most 12+|N(x)| < 12+4k. Since any problem parameterized by q expressible in Monadic Second-Order Logic is in FPT with respect to q on graphs of treewidth bounded by q [10], a polynomial-time algorithm can be designed by solving the problem for all such subgraphs defined from each vertex v of G, and answering yes if at least one such problem answers yes and answer no otherwise. ✷

Graph classes with polynomial-time algorithms

In the following we identify some graph classes on which Max Independent 2-Clique is computable in polynomial time, while Max Independent Set is not always polynomialtime solvable. First, it is interesting to notice that, according to the next propositions, Max Independent 2-Clique is polynomial-time solvable on graphs of bounded degree and also on complements of graphs of bounded degree, while Max Independent Set is NP-hard on graphs of bounded degree [START_REF] Garey | Some simplified NP-complete problems[END_REF] but polynomial-time solvable on their complements (using exhaustive search in the non-neighborhood of each vertex, which can be done in linear time).

Proposition 7 Max Independent 2-Clique is linear-time solvable on graphs with bounded maximum degree.

Proof. The proof consists in computing, for each vertex v of a graph G = (V, E), the largest size of an independent 2-clique v can belong to. Since the maximum degree is bounded, also the number of vertices at distance 2 from v is bounded, thus the largest independent 2-clique among them can be determined in constant time. Performing this for all vertices of the graph can be done in O(|V |) steps. ✷ Proposition 8 Max Independent 2-Clique is linear-time solvable on graphs of minimum degree at least (nd), where d is constant.

Proof. Since every vertex is non-adjacent with fewer than d vertices, the size of a solution cannot exceed d. Then using an exhaustive search in the non-neighborhood of each vertex, we can find an optimal solution in linear time. ✷ Now, notice that a natural way to find an independent 2-clique is to take an independent set included in the neighborhood of one vertex. First, this principle can be applied easily on trees.

Proposition 9 Every tree T satisfies α =2 (T ) = ∆(T ). Thus, Max Independent 2-Clique is linear-time solvable on trees without using Monadic Logic.

Proof. Any two vertices v, w of an independent 2-clique S share a neighbor, say u, which is unique in any tree. Non-neighbors of u cannot belong to S because they are at distance at least 3 from v or w (or both). On the other hand, all neighbors of u have mutual distance 2, so that |S| is largest if S is the neighborhood of a vertex of maximum degree. ✷

In this way, it is interesting to investigate the properties of a graph in which an independent 2-clique is not included in the neighborhood of one vertex. We show in Lemma 10 that such a graph necessarily contains a cycle of length 3 or 6, and cannot be a cactus if such an independent 2-clique has a certain size. Such properties allow us to get an easy polynomial-time algorithm for Max Independent 2-Clique on (C 3 , C 6 )-free graphs, while Max Independent Set is NP-hard1 on this class of graphs (see [START_REF] Alekseev | On the local restrictions effect on the complexity of finding the graph independence number[END_REF]). From Theorem 4 we already know that Max Independent 2-Clique is linear-time solvable on cactus graphs, but the property of Lemma 10 allows us to give a simpler algorithm for this class of graphs.

Lemma 10 Let G = (V, E) be a graph. Suppose that there exists an independent 2-clique S not contained in the neighborhood of a single vertex. Then G contains an induced cycle of length 3 or 6. Moreover, if |S| ≥ 4, then G is not a cactus.

Proof. Let S be an independent 2-clique in G such that not all vertices of S have a common neighbor. Let u be a vertex in V \ S which has the maximum number of neighbors in S, and N u be the neighborhood of u in S. Then there exists a vertex z in S which is not a neighbor of u. Let v be any vertex of N u , and w be a common neighbor of z and v. Let v ′ be a vertex in N u non-adjacent to w (it exists by the choice of u). Since S is a 2-clique, v ′ and z have a common neighbor, say w ′ (notice that w ′ can be neither u nor w). Thus, C := (u, v, w, z, w ′ , v ′ , u) is a cycle in G (see Figure 2).

If C has no chord, then it is an induced 6-cycle of G; and otherwise any chord of C lies inside {u, w, w ′ } and thus it creates a 3-cycle in G. This proves the first assertion.

Suppose now that |S| ≥ 4. Then there are three options:

• u has only two neighbors in S. Then any two vertices of S must have a different common neighbor in V \ S (by the choice of u), moreover there exists z ′ in S \ {N u , z}.

In this situation v, z, z ′ with their three pairwise neighbors create a 6-cycle sharing the edge wz with C and thus G is not a cactus.

S u w w

′ v ′ v z
Figure 2: The independent 2-clique S and its (partial) neighborhood selected in the proof of Lemma 10. Dotted lines are possible edges, so z can be at distance 2 from other vertices in S but those are unimportant for the proof.

• u has at least 3 neighbors and w has only v as a neighbor in N u . Let z ′ be a vertex of N u \ {v ′ , v}. Then z and z ′ must have a common neighbor x (which cannot be u or w but could be w ′ ). Then wz is a common edge of C and the 6-cycle (u, z ′ , x, z, w, v, u) and thus G is not a cactus.

• u has at least 3 neighbors and w has at least 2 neighbors in N u , say v and z ′ . Then vw is a common edge of C and the 4-cycle (u, v, w, z ′ , u) and thus G is not a cactus.

✷ This lemma implies the following theorem:

Theorem 11 Any (C 3 , C 6 )-free graph G satisfies α =2 (G) = ∆(G) and Max Independent 2-Clique is linear-time solvable on it.

Proof. By Lemma 10, in (C 3 , C 6 )-free graphs any independent 2-clique is the neighborhood of some vertex. Then, an independent 2-clique of maximum size is given in linear time by taking the neighborhood of a vertex of maximum degree since vertices in the neighborhood of any vertex are not adjacent in C 3 -free graphs. ✷ Finally, Lemma 10 allows us to give a polynomial-time algorithm for Max Independent 2-Clique on cactus graphs.

Proposition 12 Max Independent 2-Clique is linear-time solvable on cactus graphs.

Proof. Since all cycles of a cactus can be triangulated without creating a K 4 , cactus graphs have treewidth at most 2, hence an implicit algorithm running in linear time follows from the proof of Theorem 4.

Being more constructive, Lemma 10 implies that an independent 2-clique S in a cactus of order at least two either is a single vertex of a C 3 , or consists of at most three (independent) vertices of a C 6 , or lies entirely in the neighborhood of a vertex v. In the latter case, if B 1 , . . . , B k are the blocks incident with v, then if B i is an edge or a triangle then it can have just one vertex in S; and if B i is a longer cycle then both neighbors of v in B i can belong to S. Since every set obtained in this way is an independent 2-clique, the maximum size can be determined in linear time. ✷

We focus in the following part of this section on classes of graphs on which both Max Independent 2-Clique and Max Independent Set are polynomial-time solvable. We first investigate a subclass of split graphs, namely threshold graphs. It follows from the definitions that a threshold graph G = (V, E) is a split graph with the following property: the vertices of the independent set S can be ordered as v 1 , . . . , v p such that N G (v 1 ) ⊆ N G (v 2 ) ⊆ . . . ⊆ N G (v p ). We denote by u 1 , . . . , u q the vertices of the clique K, and we suppose that d G (u 1 ) ≤ d G (u 2 ) ≤ . . . ≤ d G (u q ). Without loss of generality, we assume that there is no isolated vertex in G. Note that a threshold graph can be recognized in linear time (see [START_REF] Heggernes | Linear-time certifying recognition algorithms and forbidden induced subgraphs[END_REF]).

Proposition 13 Max Independent 2-Clique is linear-time solvable on threshold graphs. Moreover, in every threshold graph G without isolated vertices we have α =2 (G) = α(G).

Proof. Let G = (V, E) be a threshold graph with the previous decomposition into S and K. Let N G (v p ) = {u r , u r+1 , . . . , u q }, for some r ≥ 1. Then a maximum independent 2-clique in G is S if K \ N G (v p ) = ∅, and otherwise it is S ∪ {z} with any z ∈ K \ N G (v p ), since in both cases the common neighbor of all these vertices is u q . Since Max Independent Set can be solved in linear time in threshold graphs [START_REF] Frank | Some polynomial algorithms for certain graphs and hypergraphs[END_REF], Max Independent 2-Clique can also be solved in linear time. ✷

The previous result can be extended in two directions, for interval graphs and for cographs.

Using the results of Booth and Lueker [START_REF] Booth | Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms[END_REF] it can be tested in linear time whether a graph G is an interval graph; and if it is, then an interval representation I 1 , . . . , I n of G can also be generated.

Proposition 14 Max Independent 2-Clique is polynomial-time solvable on interval graphs.

Proof. Consider any G = (V, E) and let I 1 , . . . , I n be an interval representation of G. In order to determine α =2 (G), first notice that all vertices of an independent 2-clique S of G must have a common neighbor. Indeed, if I and I ′ are the leftmost and the rightmost intervals of S then any of their common neighbors intersects all intervals located between them, and therefore is a common neighbor of all members of S. Then, for every vertex I, we compute a maximum independent set in the subgraph induced by the neighborhood of I. An optimal solution is such an independent set with maximum size. Since Max Independent Set is polynomial-time solvable on interval graphs [START_REF] Gupta | Efficient algorithms for interval graphs and circular-arc graphs[END_REF], the result follows. ✷

We consider now the class of cographs, that contains all threshold graphs, and we show that Max Independent 2-Clique is also polynomial-time solvable on this class. To each cograph G with n vertices, we can associate a rooted tree T , called the cotree of G.

Leaves of T correspond to vertices of the graph G, and internal nodes of T are labeled with either '∪' (union-node) or '×' (join-node). A subtree rooted at node '∪' corresponds to the vertex-disjoint union of the subgraphs defined by the children of that node, and a subtree rooted at node '×' corresponds to the complete join of the subgraphs defined by the children of that node; that is, we add an edge between every two vertices corresponding to leaves in different subtrees under the join-node in question. Cographs can be recognized in linear time and the cotree representation can be obtained efficiently [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF][START_REF] Habib | A simple linear time algorithm for cograph recognition[END_REF]. Moreover, any cotree can easily be transformed in linear time to a binary cotree with O(n) nodes.

Proposition 15 Max Independent 2-Clique is polynomial-time solvable on cographs.

Proof. Consider a cograph G with n vertices v 1 , . . . , v n . Given a binary cotree representation T of G with O(n) nodes, we show in the following how to solve Max Independent 2-Clique recursively.

Let x 1 , . . . , x t be the nodes of T where t is in O(n). For i = 1, . . . , t, denote by T i the subtree rooted at x i , G i the subgraph induced by the vertices corresponding to the leaves of T i , and V i the set of these vertices.

For each i, we compute α =2 (G i ) 'bottom-up' in the cotree. We start by computing values of leaves, and after that the value of an internal node if the values of its two children are already computed. Together with α =2 (G i ) we also determine the independence number α(G i ), which is well known to admit an easy recursion (which follows immediately by the constructive definition of cographs).

Given a node x i of the cotree, the corresponding values are obtained as follows:

• If x i is a leaf then α =2 (G i ) = |V i | = 1. Also, α(G i ) = 1.
• If x i is a union-node with two children x ℓ and x r , we have no edges between G ℓ and G r . Then any maximum independent 2-clique of G i is entirely contained either in

G ℓ or in G r . So, α =2 (G i ) = max{α =2 (G ℓ ), α =2 (G r )}. On the other hand, clearly, α(G i ) = α(G ℓ ) + α(G r ).
• If x i is a join-node with two children x ℓ and x r , every vertex in V ℓ is adjacent to every vertex in V r . Then a maximum independent 2-clique in G i is a maximum independent set entirely contained either in

G ℓ or in G r . So, α =2 (G i ) = α(G i ) = max{α(G ℓ ), α(G r )}.
Since each step can be performed in constant time, moreover postorder traversal requires linear time, the algorithm runs proportionally to the size of the cotree, which is O(n). ✷ Notice that since Max Independent Set is linear-time solvable on chordal graphs [START_REF] Frank | Some polynomial algorithms for certain graphs and hypergraphs[END_REF], it is also polynomial-time solvable on interval graphs and threshold graphs. Moreover, Max Independent Set is also polynomial-time solvable on cographs by bottom-up tree computation [START_REF] Corneil | Complement reducible graphs[END_REF].

NP-hardness and inapproximability

We investigate graph classes in which Max Independent 2-Clique is NP-hard and, in some cases, inapproximable. Using first the reduction from the proof of Theorem 2, we can conclude:

• Max Independent 2-Clique is NP-hard on dense (resp. everywhere dense) graphs, since Max Independent Set is NP-hard on dense (resp. everywhere dense) graphs. Moreover, Max Independent 2-Clique is not n 1-ε -approximable for any ε > 0, if P = NP, on everywhere dense graphs (and respectively dense graphs) since the same result holds for Max Independent Set on everywhere dense graphs (and respectively dense graphs). In order to get this last result, we use the same inapproximability result for Max Independent Set on general graphs [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF] and a reduction preserving approximation from general graphs to everywhere dense graphs (that consists of adding a clique of the same size as the size of the graph and joining every vertex from the original graph to all vertices in this clique).

• Max Independent 2-Clique is NP-hard on K 4 -free graphs, since Max Independent Set is NP-hard on K 3 -free graphs [START_REF] Alekseev | On the local restrictions effect on the complexity of finding the graph independence number[END_REF].

We now investigate graph classes in which Max Independent 2-Clique is NP-hard while Max Independent Set is polynomial-time solvable. We first consider a graph class containing threshold graphs, namely the class of split graphs, for which Max Independent 2-Clique becomes NP-hard (and even not n 1-ε -approximable, unless P=NP). Since Max Independent Set is polynomial-time solvable on chordal graphs [START_REF] Frank | Some polynomial algorithms for certain graphs and hypergraphs[END_REF], it is also polynomial-time solvable on split graphs.

Proposition 16 Max Independent 2-Clique is NP-hard on split graphs.

Proof. We reduce Max Clique on general graphs to Max Independent 2-Clique on split graphs. Let G = (V, E) be an instance of Max Clique. We define an instance G ′ = (V ′ , E ′ ) of Max Independent 2-Clique on split graphs as follows: for every vertex v i ∈ V we consider a vertex v ′ i ∈ V ′ and for every edge e ∈ E we consider a vertex e ′ in V ′ . We also add an additional vertex z in V ′ . Moreover, for any edge e = v 1 v 2 ∈ E we associate two edges in E ′ , the edges v ′ 1 e ′ and v ′ 2 e ′ . Finally, the subgraph induced by vertices e ′ ∈ V ′ and z is defined to be a clique. Now it is easy to see that C is a clique of size at least k in G if and only if C ′ = {v ′ : v ∈ C} ∪ {z} is an independent 2-clique of size at least k + 1 in G ′ . On the other hand, given an independent 2-clique S, if z / ∈ S and e ′ ∈ S holds for some (only one) e ∈ E, then we can modify S to an independent 2-clique of the same size by replacing e ′ with z. Hence, the maximum can always be attained by involving z. ✷ Theorem 17 Independent 2-Clique is W [START_REF] Alekseev | On the local restrictions effect on the complexity of finding the graph independence number[END_REF]-complete on split graphs.

Proof. From Theorem 1, we know that Independent 2-Clique belongs to W [START_REF] Alekseev | On the local restrictions effect on the complexity of finding the graph independence number[END_REF]. On the other hand, the reduction in Proposition 16 is an FPT-reduction. Since Clique is W[1]hard on general graphs [START_REF] Downey | Fixed-parameter tractability and completeness II: On completeness for W[1[END_REF], it follows that Independent 2-Clique is also W [START_REF] Alekseev | On the local restrictions effect on the complexity of finding the graph independence number[END_REF]-hard on split graphs. ✷ Theorem 18 Max Independent 2-Clique is not n 1-ε -approximable in polynomial time on split graphs unless P = NP .

Proof. We construct an E-reduction from Max Clique. Let I = (V, E) be an instance of Max Clique and let I ′ = (V ′ , E ′ ) be the corresponding instance of Max Independent 2-Clique, considering the same reduction as in Proposition 16. First, notice that opt(I) = opt(I ′ ) -1, thus we have opt(I ′ ) ≤ 2 opt(I). Now let S ′ be an independent 2-clique of I ′ of size at least 2 and let S be the set of all copies of vertices from V in S ′ . Since

opt(I) = opt(I ′ ) -1 and |S| = |S ′ | -1, we obtain opt(I) -|S| = opt(I ′ ) -|S ′ |.
Since it has been proved in [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF] that Max Clique is not n 1-ε -approximable in polynomial time unless P=NP, Max Independent 2-Clique is not n 1-ε -approximable in polynomial time on split graphs unless P=NP. ✷

We prove now that Max Independent 2-Clique is NP-hard (and even not n 1/2-ǫapproximable, unless P=NP) on bipartite graphs while Max Independent Set is polynomialtime solvable since the number of vertices in a maximum independent set equals the number of edges in a minimum edge covering.

Proposition 19 Max Independent 2-Clique is NP-hard on bipartite graphs.

Proof. Max Independent Set is known to be NP-hard on 3-regular graphs [START_REF] Garey | Some simplified NP-complete problems[END_REF], so Max Clique is also NP-hard on (n -4)-regular graphs (where n is the number of vertices), by considering its complement. We reduce Max Clique on (n -4)-regular graphs to Max Independent 2-Clique on bipartite graphs. Let G = (V, E) be an (n -4)-regular graph. We construct an instance G ′ = (V ′ , E ′ ) of Max Independent 2-Clique on bipartite graphs as follows (see Figure 3).

Let V 1 , V 2 , V 3 , V 4 be four copies of V . Let E 1 be a set of |E| vertices corresponding to the edges in E, and define

V ′ := V 1 ∪V 2 ∪V 3 ∪V 4 ∪E 1 .
Let there exist an edge in E ′ between a vertex v in V i , i ∈ {1, 2, 3, 4} and a vertex e in E 1 if and only if the corresponding vertex v in V is incident with the corresponding edge e in E.

Now we show that G contains a clique of size at least k if and only if G ′ contains an independent 2-clique of size at least 4k.

Given a clique C ⊆ V of size at least k in G, the union of the four copies of C in G ′ is an independent 2-clique of size at least 4k.

For the other direction, notice first that the value of a maximum independent set in a 3-regular graph is at least ⌈ n 4 ⌉. Then, the value of a maximum clique in an (n -4)-regular graph is also at least ⌈ n 4 ⌉. Thus the size of a maximum independent 2-clique in We consider now a solution C ′ of Max Independent 2-Clique in G ′ with at least 4k ≥ n vertices (this restriction is always possible because of the previous comment). Notice that C ′ cannot contain both a vertex from E 1 and a vertex from V ′ \ E 1 since the distance between any two vertices of C ′ must be 2. A solution which is a subset of E 1 would mean pairwise intersecting edges in G, hence would have size at most max(3, n -4) < n. Therefore C ′ must be a subset of V ′ \ E 1 . Notice that for any i ∈ {1, 2, 3, 4}, C ′ ∩ V i must be a copy of a clique in G. Then C ′ is a union of copies of four cliques in G, and |C ′ | ≥ 4k. Let C 0 be the copy of largest size, which thus has |C 0 | ≥ k. Then C 0 is the copy of a clique C of G of size at least k. ✷ Theorem 20 Max Independent 2-Clique is not n 1/2-ε -approximable in polynomial time on bipartite graphs, unless P = NP .

G ′ is at least n. V 1 E 1 V 2 V 3 V 4
Proof. We construct an E-reduction from Max Clique. Let I = (V, E) be an instance of Max Clique. Consider a reduction similar to the one in the proof of Proposition 19, except that we now consider ℓ = |V | copies V 1 , . . . , V ℓ instead of four copies of V ; adjacencies are defined in the same way as before. We denote by I ′ = (V ′ , E ′ ) the corresponding instance of Max Independent 2-Clique from the reduction. As in Proposition 19, starting with a clique of size opt(I), we can construct an independent 2-clique of size ℓ • opt(I) in G ′ and thus opt(I ′ ) ≥ ℓ • opt(I). Let S ′ be any independent 2-clique in I ′ of size at least ℓ (it always exists, take e.g. the ℓ copies of the same vertex, one copy in each V i ). As before, S ′ cannot contain both a vertex of E 1 and a vertex from V \ E 1 since two vertices of S ′ must have distance 2 in G ′ , and S ′ cannot contain only vertices from E 1 since any

independent 2-clique included in E 1 is of size at most max(3, ∆(G)) ≤ ℓ -1. Moreover, each subset V i ∩ S ′ corresponds to a clique in G. Let S be the subset V i ∩ S ′ of largest size. We have |S| ≥ |S ′ | ℓ and then opt(I) ≥ |S| ≥ |S ′ | ℓ = opt(I ′ )
ℓ when S ′ is an optimal solution. Using that opt(I ′ ) ≥ ℓ • opt(I) we get opt(I ′ ) = ℓ • opt(I) and we obtain:

ǫ(I, S) = opt(I) |S| -1 ≤ ℓ • opt(I ′ ) ℓ • |S ′ | -1 = ǫ(I ′ , S ′ )
Since we clearly have opt(I ′ ) ≤ p(|I|) • opt(I) with a polynomial p, the reduction is an E-reduction. Then, since Max Clique is not ℓ 1-ε -approximable, unless P=NP [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF], the same property holds for Max Independent 2-Clique. Thus Max Independent 2-Clique is not n 1/2-ε approximable where n = |V ′ | since n = ℓ 2 + |E|. ✷

Finally we prove that Max Independent 2-Clique is NP-hard (and even APX-hard) on line graphs, while Max Independent Set is polynomial-time solvable since it consists in a maximum matching in the original graph.

Proposition 21 Max Independent 2-Clique is NP-hard on line graphs.

Proof. We establish a reduction from the Max Clique problem on general graphs. Consider an instance G = (V, E) of Max Clique with |V | = n. We construct a graph G ′ = (V ′ , E ′ ) (see Figure 4) as follows. Let G 0 = (V 0 , E 0 ) be a copy of G. Let V ′ be V 0 ∪A∪B∪C where A, B, C are three sets of n vertices. Then, let

E ′ = E 0 ∪E 1 ∪E 2 ∪E 3 ∪E 4
such that E 1 is a perfect matching between V 0 and A, E 2 is the set of all possible edges (i.e., a complete bipartite graph) between the vertices of A and the vertices of B, E 3 is a perfect matching between B and C, and E 4 is the set of all possible edges between any two vertices of C (a complete subgraph). The line graph of G ′ , denoted by L(G ′ ), is an instance of Max Independent 2-Clique. Notice that an independent 2-clique in L(G ′ ) corresponds to a set of edges in G ′ such that, for each pair of edges {e 1 , e 2 } in the set, e 1 and e 2 are not adjacent but are joined by an edge. We show that G contains a clique of size at least k if and only if L(G ′ ) contains an independent 2-clique of size at least k + n. Consider a clique S of size k in G, and let S 0 be its copy in G ′ . We define a set of edges S ′ of size at least k + n in G ′ as follows. For any vertex v ∈ S 0 , add in S ′ its adjacent edge in E 1 . Moreover add the entire E 3 to S ′ . We show now that any pair of edges in S ′ have an adjacent edge in common. Two edges of S ′ ∩ E 1 have a common adjacent edge in E 0 since the subgraph induced by S 0 is a clique. Similarly, two edges of E 3 have a common adjacent edge in E 4 . Moreover, an edge of S ′ ∩ E 1 and an edge of E 3 have a common adjacent edge in E 2 since the subgraph induced by A ∪ B is K n,n . Then, the corresponding set of vertices in L(G ′ ) is an independent 2-clique of size k + n.

In the other direction, consider an independent 2-clique in L(G ′ ) of size k + n. Notice that it is always possible to take the set of vertices in L(G ′ ) corresponding to E 3 in G ′ and two edges in E 1 whose vertices in V 0 are neighbors in G ′ , hence we can suppose that k ≥ 2.

Let S ′ be the set of all corresponding edges in G ′ . Suppose first that there is exactly one edge from E 0 in S ′ . Then, there are at most n -2 edges from E 1 in S ′ , and there are at most 2 edges from E 2 in S ′ , due to the constraints of an independent 2-clique. There cannot be edges from E 3 ∪ E 4 in S ′ since they would not be joined to the edge of E 0 ∩ S ′ by any edge. Then, S ′ contains at most n + 1 edges in S ′ , which contradicts k ≥ 2. Suppose now that there are g ≥ 2 edges from E 0 in S ′ . Those edges of E 1 which meet them, are excluded from S ′ , hence there are at most n -2g edges from E 1 in S ′ ; and there is no edge from E 2 in S ′ because the distance-2 neighbors of each e ∈ E 2 form a star in E 0 , while the current S ′ ∩ E 0 is a matching of g edges. Then the size of S ′ is at most ng, which contradicts k ≥ 2.

Thus, we can assume that there is no edge from E 0 in S ′ . Similarly, there is no edge from E 4 in S ′ . Now, notice that |S ′ ∩ (E 2 ∪ E 3 )| ≤ n since if S ′ ∩ (E 2 ∪ E 3 ) contained n + 1 edges then at least two of these edges would have a common endpoint. Consequently, |S ′ ∩ E 1 | ≥ k. Moreover, any two edges from S ′ ∩ E 1 must have a common adjacent edge in E 0 since they cannot have a common adjacent edge in E 2 . Then, the subgraph of G induced by the set of vertices in V 0 which are the endpoints of the edges in S ′ ∩ E 1 must be a clique whose size is at least k. ✷ Theorem 22 Max Independent 2-Clique is APX-hard on line graphs.

Proof. We construct now an L-reduction from a restricted version of Max Clique to Max Independent 2-Clique on line graphs. Let I be an instance of Max Clique on graphs of degree at least n -4 and I ′ the corresponding instance of Max Independent 2-Clique on line graphs from the previous reduction. We prove that this reduction is an L-reduction. We proved in Proposition 21 that any independent 2-clique in I ′ has a size at most 2n. Then opt(I ′ ) ≤ 2n = 8 • n 4 ≤ 8 • opt(I) follows since opt(I) ≥ n 4 in graphs of degree at least n -4. Moreover, starting with a clique of size opt(I), we can construct an independent 2-clique of size opt(I) + n and therefore opt(I ′ ) ≥ n + opt(I). Let S ′ be an independent 2-clique in I ′ of size at least n + 2 (we proved in Proposition 21 that it always exists and that such a set must be included in E 1 ∪ E 2 ∪ E 3 ). Let S be the set of vertices in V 0 which are incident with edges in E 1 ∩ S ′ . We have |S ′ | -|S| ≤ n, i.e. n + |S| ≥ |S ′ |. Then we obtain opt(I) -|S| ≤ opt(I ′ )n -|S| = opt(I ′ ) -(n + |S|) ≤ opt(I ′ ) -|S ′ |. Since Max Independent Set is APX-hard on the class of graphs of maximum degree 3 [START_REF] Alimonti | Some APX-completeness results for cubic graphs[END_REF], Max Clique is also APX-hard on the class of graphs of minimum degree at least n -4. Thus, Max Independent 2-Clique is APX-hard on line graphs. ✷

Conclusion

Despite that Max Independent 2-Clique and Max Independent Set are similar problems, their complexity can be very different depending on the graph class we try to solve the problem in. We showed that Max Independent 2-Clique is NP-hard on apex, dense and everywhere dense, K 4 -free, split, bipartite and line graphs while it is polynomialtime solvable on bounded treewidth, planar, bounded degree (and complement of bounded degree), (C 3 , C 6 )-free, interval graphs and cographs. Many further types of graphs may be of interest, concerning separation of graph classes in which the problem is NP-hard from the ones where the problem is solvable in polynomial time.

From the parameterized complexity point of view, we showed that Independent 2-Clique is in FPT on apex graphs. On the other hand, some problems related to the parameterized complexity are open. Independent Set is in FPT on K 3 -free graphs [START_REF] Raman | Triangles, 4-cycles and parameterized (in-)tractability[END_REF] but Independent 2-Clique remains open for this class of graphs. From Proposition 19, Clique on (n -4)-regular graphs FPT reduces to Independent 2-Clique in bipartite graphs but Clique is in FPT on (n -4)-regular graphs (since Independent Set is in FPT on 3-regular graphs). Then the parameterized complexity of Independent 2-Clique remains open on bipartite graphs.

Figure 1 :

 1 Figure1: Relationship among some classes of (connected) graphs, where each child is a subset of its parent. We compare the hardness of Max Independent 2-Clique and Max Independent Set in studied graph classes. Max Independent 2-Clique is NP-hard on graph classes at the top of the figure (hatched area) and is polynomial-time solvable on graph classes at the bottom (non-hatched area). Max Independent Set is NP-hard on graph classes on the left of the figure (dotted area) and is polynomial-time solvable on graph classes on the right (non-dotted area).

Figure 3 :

 3 Figure 3: The bipartite graph G ′ , an instance of Max Independent 2-Clique

Figure 4 :

 4 Figure 4: The graph G ′ for which the corresponding line graph L(G ′ ) is an instance of Max Independent 2-Clique

The original definition is that the graph admits a vertex labeling with positive real numbers, such that two vertices are adjacent if and only if the sum of their labels is at least (or, at most) a given 'threshold' t.

It is proved in[START_REF] Alekseev | On the local restrictions effect on the complexity of finding the graph independence number[END_REF] that for a finite set H of connected graphs, Max Independent Set is NP-hard on the class of H-free graphs if no member of H is either a path or a tree with one vertex of degree 3 and the other vertices of degree at most

Acknowledgments

Research of Zsolt Tuza was supported in part by the National Research, Development and Innovation Office -NKFIH under the grant SNN 116095.