Kien Lam Ung

Husam M A B Alsarraf

Laurent Kremer

Mickael Blaise
email: mickael.blaise@irim.cnrs.fr

Mickaël Blaise

The crystal structure of the mycobacterial

Keywords: mycobacteria, mycolic acids, MmpL3, TtfA, cell wall

come   L'archive ouverte pluridisciplinaire

Introduction

With 10 million new cases and 1.6 million deaths in 2017, tuberculosis (TB) remains a major global threat worldwide. Mycobacterium tuberculosis, the etiologic agent of TB , is a resilient microorganism which can persist through long courses of antibiotics. The emergence of drugresistant bacteria largely contributes to the difficulty in curing TB patients. This involves acquired resistance mechanisms occurring during lengthy antibiotherapy and intrinsic resistance mechanisms that are linked to the atypical mycomembrane, which is impermeable to small hydrophilic molecules, such as antibiotics.

The thick and waxy mycobacterial cell envelope consists of an outermost layer named capsule and composed of (glyco)lipids and polysaccharides [START_REF] Kaur | Chapter 2: Biogenesis of the cell wall and other glycoconjugates of Mycobacterium tuberculosis[END_REF] . The mycomembrane comprises essentially mycolic acids, which are very long-chain fatty acids (C80-C90) as well as free and extractable (glyco)lipids, such as dimycolyltrehaloses [START_REF] Briken | Mycobacterial lipoarabinomannan and related lipoglycans: from biogenesis to modulation of the immune response[END_REF] , that are interspersed between mycolic acids and play a key role in the host-pathogen interactions. An arabinogalactan layer is bridging together the mycolic acids and the peptidoglycan [START_REF] Crick | Biosynthesis of the arabinogalactan-peptidoglycan complex of Mycobacterium tuberculosis[END_REF] .The arabinogalactan-mycolyl-peptidoglycan skeleton represents the core structure of the cell wall, beneath of which is found the plasma membrane.

Many enzymes involved in cell wall biosynthesis are unique to the Mycobacterium genus and absent in mammals and are thereby, recognized as valuable chemotherapeutic targets [START_REF] Kaur | Chapter 2: Biogenesis of the cell wall and other glycoconjugates of Mycobacterium tuberculosis[END_REF] . Mycolic acids for instance are essential cell wall components and contribute also to this high cell wall hydrophobicity [START_REF] Bhatt | The Mycobacterium tuberculosis FAS-II condensing enzymes: their role in mycolic acid biosynthesis, acid-fastness, pathogenesis and in future drug development[END_REF] . First, synthesized in the cytoplasm in the form of trehalose monomycolates (TMM), which are subsequently acetylated, mycolic acids are then transported across the plasma membrane by a specific and atypical lipid transporter, MmpL3 [START_REF] Grzegorzewicz | Inhibition of mycolic acid transport across the Mycobacterium tuberculosis plasma membrane[END_REF] . The Ag85ABC complex catalyses the conversion of TMM into trehalose dimycolate (TDM) as well as the transfer of mycolic acids to the arabinogalactan of the mAGP complex, thereby contributing to the elaboration of the mycobacterial membrane.

During the last few years, several independent studies demonstrated that MmpL3 is an essential transporter belonging to the superfamily of the Resistance Nodulation Division (RND) permeases and represents also an attractive drug target [START_REF] Quémard | New Insights into the Mycolate-Containing Compound Biosynthesis and Transport in Mycobacteria[END_REF] Two recent studies reported the crystal structure of Mycobacterium smegmatis MmpL3 revealing the mode of action of some of these inhibitors and providing a first glance on our understanding of TMM transport [START_REF] Zhang | Crystal Structures of Membrane Transporter MmpL3, an Anti-TB Drug Target[END_REF][START_REF] Su | MmpL3 is a lipid transporter that binds trehalose monomycolate and phosphatidylethanolamine[END_REF] . A contrario to other well studied RND pumps, such as AcrB from Escherichia coli that is part of a tripartite complex, the existence of MmpL3 accessory proteins was questioned. This has been partly delineated through the establishment of the MmpL3 interactome that comprises many proteins, thus supporting the occurrence of a very complex crosstalk between the cell envelope biosynthesis and cell division [START_REF] Belardinelli | The MmpL3 interactome reveals a complex crosstalk between cell envelope biosynthesis and cell elongation and division in mycobacteria[END_REF] . Additionally, the LpqN lipoprotein was demonstrated to bind to a lipid mimicking TMM and capable to interact with the periplasmic domains of MmpL3 and MmpL11 on the one hand as well as with members of Ag85 complex on the other hand [START_REF] Melly | Structural and functional evidence that lipoprotein LpqN supports cell envelope biogenesis in M. tuberculosis[END_REF] . Importantly, in an elegant study [START_REF] Fay | Two Accessory Proteins Govern MmpL3 Mycolic Acid Transport in Mycobacteria[END_REF] , an essential protein MSMEG_0736 interacting with MmpL3 both in M. smegmatis and M. tuberculosis was discovered. The MSMEG_0736 protein co-eluted in pull-down experiments using MmpL3 as a bait and its essential character for mycobacterial viability was demonstrated. The protein is associated with the plasma membrane where it participates in TMM transport as evidence by genetic studies based on a knock-down MSMEG_0736 mutant that accumulates TMM while the synthesis of TDM decreases, mirrorring the phenotypes observed in either mmpL3 conditional mutants [START_REF] Degiacomi | Essentiality of mmpL3 and impact of its silencing on Mycobacterium tuberculosis gene expression[END_REF] or when using specific MmpL3 inhibitors [START_REF] Dupont | A new piperidinol derivative targeting mycolic acid transport in Mycobacterium abscessus[END_REF] . Additionally, albeit non-essential for bacterial viability the MSMEG_5308 protein was also found in the MSMEG_0736/MmpL3 complex [START_REF] Fay | Two Accessory Proteins Govern MmpL3 Mycolic Acid Transport in Mycobacteria[END_REF] . Collectively, these results indicate that MSMEG_0736/Rv0383c is a key player in TMM transport, hence was named TMM transport factor A, TtfA.

As the exact role and function of TtfA in the TMM transport is not clearly understood and as TtfA does not share any homology to any other known protein, we decided to investigate its structural characterization. Herein, we describe the high-resolution crystal structure of the core domain of TtfA from M. smegmatis.

Materials and Methods

Cloning, expression and purification of MSMEG_0736 (TtfA)

The coding sequence for TtfA residues 24-205 was amplified by PCR using Mycobacterium smegmatis mc 2 155 genomic DNA as a template and the following forward and reverse primers: fw: The same E. coli strain was also used for labelling the protein with selenomethionine. Cells were first grown in 2 L of LB broth containing 50 μg/mL KAN at 37°C under agitation at 180 r.p.m.

for 24 h. This starter culture was then pelleted, washed thrice with 1x PBS buffer and resuspended with pre-warmed medium A containing M9 medium, trace elements, 20% glucose, 1 M MgSO 4 , 1 M CaCl 2 , 1mg/L biotin, 1mg/L thiamine, and 50 μg/mL KAN to a final OD 600 = ~ 0.8. The culture was incubated at 37°C for 1.5 h prior to addition of a mix D/L SeMet at a final concentration of 50 μg/mL (Sigma-Aldrich) and further incubated for 30 min. Finally, protein induction was done by adding 1 mM of IPTG and incubation for 2 days at 16°C. The purification procedure was identical to the one used for native TtfA, as described above, with the exception that the NaCl concentration of buffer B and C was increased to 0.6 M. Protein concentration was determined using a Nanodrop 2000c spectrophotometer (Thermo Fisher Scientific).

Determination of molecular weight by size-exclusion chromatography

The oligomeric state of TtfA core domain (24-205) in solution was assessed using a Superdex 200 10/300 GL column (GE Healthcare) and elution performed with buffer D. The molecular weight was calculated based on a calibration curve obtained by the elution profile of proteins standard with molecular weight ranging from 12, 400 to 200, 000 Da (Gel Filtration Markers Kit, Sigma-Aldrich). Dextran blue was used to determine the void volume of the column.

The apparent mass was determined by plotting the partition coefficient K av against the logarithm of the molecular weight of the standard proteins.

Crystallization

The MSMEG_0736 native crystals were grown in sitting drops in the Swissci 48-well MRC Maxi Optimization plates (Molecular Dimension) at 18°C by mixing 2 µL of protein solution concentrated to 8 mg/mL with 2 µL of reservoir solution consisting of 28% PEG 4000 and 0.2 M (NH 4 ) 2 SO 4. The MSMEG_0736 protein labelled with selenomethionine was crystallized using the microseeding technique and the crystals of the native protein as seeds. The selenomethionine substituted protein was crystallized at 18°C by mixing 2 µL of protein solution concentrated to 8 mg/mL with 2 µL of a reservoir solution made of 0.1 M Bis-Tris pH 5.5, 27% PEG 3350 and 0.2 M Li 2 SO 4. All the crystals were cryo-cooled in liquid nitrogen without any cryoprotection.

Data processing, structure solution and refinement

Data collection was performed at the Swiss-Light Source, Villigen, Switzerland on the PXIII-X06DA beamline. Data were processed with XDS and scaled and merged with XSCALE [START_REF] Kabsch | Integration, scaling, space-group assignment and post-refinement[END_REF] .

Phasing was done by the single anomalous dispersion (SAD) method using the AutoSol module from the Phenix package [START_REF] Adams | PHENIX: a comprehensive Python-based system for macromolecular structure solution[END_REF] . Five out of the six potential selenium sites in the asymmetric unit were found using a resolution cut-off of 2 Å for the search of the Se atoms. After density modification, the electron density map was of high quality allowing almost automatic complete model building with autobuild. The resulting model was then used to performed molecular replacement with the 1.4

Å native dataset using Phaser 17 from the Phenix package [START_REF] Adams | PHENIX: a comprehensive Python-based system for macromolecular structure solution[END_REF] . Coot 18 was used for manual rebuilding while structure refinement and validation were performed with the Phenix package [START_REF] Adams | PHENIX: a comprehensive Python-based system for macromolecular structure solution[END_REF] . The statistics for data collection and structure refinement are displayed in Table 1. Figures were prepared with

PyMOL (www.pymol.org).

Results and discussion

Protein expression and purification

Our cloning strategy was based on bioinformatic analysis, secondary structure prediction as well as on previous biological data whereby residues 1-205 were shown to be essential for the function of the protein [START_REF] Fay | Two Accessory Proteins Govern MmpL3 Mycolic Acid Transport in Mycobacteria[END_REF] . The secondary structure prediction also attests that the C-terminal part of the protein that is not well conserved among other species is predicted to be highly disordered (Figure 1A). Furthermore, the TtfA residues 206-278 are dispensable for TMM transport in mycobacteria and for the interaction with MmpL3 12 . We attempted to express several constructs carrying the N-terminal transmembrane helix residues 1-23 but all these proteins were not soluble and found in inclusion bodies. However, discarding residues 1 to 23 allowed us to produce a truncated TtfA containing residues 24 to 205 in a soluble form. Of note, the introduction of a TEV cleavage site and our cloning strategy added three extra residues (GHM) at the N-terminus after TEV cleavage and two extra residues (AS) at the C-terminus . However, due to the propensity of this protein to aggregate, high concentration of NaCl (0.6 M) and 5% glycerol were added in all buffers to maintain its solubility. Overall, this allowed to purify large amounts of pure and homogeneous TtfA (Figure 2A) following a three-step purification procedure as described in the Materials and Methods section.

Structural analysis

TftA was crystallized and high-resolution datasets were collected for both the native and the seleno-methionine-substituted protein. The structure was solved by SAD using a dataset collected at the Se peak. Further, the structure of the native protein was solved by molecular replacement and refined to 1.4Å (Table 1). The asymmetric unit contains one protein monomer and two sulfate ions.

Most of the residues are well ordered and could be modelled, excepted the first 6 residues GHMIDR with R corresponding to residue 26 of the M. smegmatis TtfA protein and GHM corresponding to the additional residues added by our cloning strategy. In the C-terminal of the protein, we could not build N205.

Analysis of the crystal packing with the PISA server (https://www.ebi.ac.uk/pdbe/pisa/) fails to predict the existence of stable oligomers. To confirm or infirm this hypothesis, the molecular weight of the protein in solution was assessed by size-exclusion chromatography. While the theoretical mass of TtfA (25-205) is 21.3 kDa, we estimated to 14.4 kDa the apparent molecular weight of the protein (Figure 2A). Overall, these results strongly suggest that the truncated TtfA protein is a monomer in solution.

The overall structure of TtfA is made of a central antiparallel β-sheet flanked by α-helices.

The β-sheet is made of nine β-strands formed by the following residues : β1 (residues: 44-47), β2

(71-77), β3 (80-87), β4 (90-97), β5 (106-110), β6 (120-125), β7 (130-134), β8 (161-165) and, β9

(168-173). The central core of the structure is surrounded by four α-helices: α1 (30-41), α2 (137-143), α3 (146-1154) and α4 (179-197). The fold is finally completed by three 3 10 helices: η1 (52-56), η2 (60-63), η3 (157-160) (Figure 1A and2B).

We next searched for structures similar to TtfA using the DALI server [START_REF] Holm | Dali server: conservation mapping in 3D[END_REF] but failed to retrieve significant hits. Only structures displaying a central antiparallel β-sheet but sharing a very low primary sequence identity matched the TtfA structure. The best Z-score obtained corresponds to the structure of tAvrPphF, the chaperone for the Type III Effector AvrPphF from Pseudomonas syringae (PDB entry1s28), which shares only 4% of primary sequence identity and an r.m.s.d. of 3.3 Å. This analysis attests for a hitherto unseen and atypical fold that characterizes TtfA.

We next searched for the presence of a potential cavity which could eventually host TMM but we could neither identify any obvious pocket able to accommodate this glycolipid nor a particular hydrophobic area that could bind the long mycolic acid chains of TMM. In the absence of biochemical experiment we cannot totally exclude that TtfA binds lipids ; but the structural analysis suggesting that TtfA does not bind lipids is supported by the observation of the protein surface that is mainly positively charged on one side, especially towards the N-terminus region and negatively charged on the opposite side (Figure 2C). However this prompted us to investigate the surface charge on the MmpL3 crystal structure which appears to be highly negative and more particularly its periplasmic domains (not shown) [START_REF] Zhang | Crystal Structures of Membrane Transporter MmpL3, an Anti-TB Drug Target[END_REF] . It is tempting to speculate that the TtfA positively-charged area may interact with these MmpL3 extracellular domains. However, it was reported that the Cterminal domain of TtfA (25-205) is cytoplasmic [START_REF] Fay | Two Accessory Proteins Govern MmpL3 Mycolic Acid Transport in Mycobacteria[END_REF] , therefore excluding the possibility that TtfA interacts with the MmpL3 periplasmic domains. This suggests that TtfA may not be necessarily a direct binding partner of MmpL3. Another possibility would be that TtfA interacts with the flexible C-terminal part of MmpL3 but we could not explore this hypothesis since the MmpL3 crystal structures available do not comprise the C-terminal domain. However, in other TtfA-containing bacteria such as corynebacteria, MmpL3 homologues do not possess this C-terminal extension. It remains also possible that TtfA interacts via its N-terminal transmembrane helix with the transmembrane domains of MmpL3, but this could not be experimentally assayed as we failed to purify a soluble TtfA protein with its complete N-terminal helix.

Distribution of TtfA among Actinobacteria

The search for homologues of TtfA was performed using the HMMER server. TtfA was only found in bacteria belonging to the Actinobacteria phylum as seen on the simplified phylogenetic tree in Figure 1B. As expected, the highest sequence identity was found with homologues from the mycobacterial genus (Figure 1A). Additionally, TtfA homologues were found as reported earlier [START_REF] Fay | Two Accessory Proteins Govern MmpL3 Mycolic Acid Transport in Mycobacteria[END_REF] in other mycolic acid-producing bacteria such as corynebacteria, nocardia or rhodococcus.

Unexpectidely, although less conserved, TtfA homologues were also identified in non-producing mycolic acid bacteria, such as pseudonocardia or streptomyces. Primary sequence alignments show for example that in the Amycolatopsis methanolica a homologue (UniProtKB -A0A076MZQ3) of TtfA shares 21%/36% of primary sequence identity/similarity with TtfA from M. smegmatis (Figure 1A). Noteworthingly, in silico predictions attest for the presence of a transmembrane helix in the N-terminus of this protein. The genome of Amycolatopsis methanolica was next analysed for the presence of genes encoding the two binding partners reported so far for TtfA, i.e. homologues of MmpL3 and MSMEG_5308 [START_REF] Fay | Two Accessory Proteins Govern MmpL3 Mycolic Acid Transport in Mycobacteria[END_REF] . This revealed the presence of a homologue of MmpL3 sharing 29%/48% identity/similarity but no homologue for MSMEG_5308 was found. A similar observation was made in Streptomyces regensis. Conversely, other genomes such as the one of Pseudonocardia dioxanivorans encode for TtfA homologues but are lacking MmpL3-encoding genes. This strongly suggests that TtfA might not be solely dedicated to TMM transport and/or that TtfA orthologues may exert additional biological functions notably in bacteria that neither produce mycolic acids nor possess MmpL3 homologues.

Figures legends

  . Currently, MmpL3 represents one of the most promising antimycobacterial pharmacological target and a wide panel of chemical scaffolds have been shown to inhibit MmpL3 7 not only in M. tuberculosis but also in non-tuberculous mycobacteria, such as Mycobacterium abscessus, thus opening a new field in the inhibition of mycolic acid transport.

  . The PCR product was cloned into pET-30a between the KpnI and XhoI restriction sites, to generate an in-frame fusion with the N-terminal 6xHis-tag and S-tag and designed so that it contains also a Tobacco Etch Virus (TEV) protease cleavage site. The pET30:MSMEG_0736_(24-205) was transformed into the E. coli B834 (DE3) methionine auxotroph strain (Merck-Millipore), used for the production of both the native and the seleno-methionine proteins.For the native protein expression, cells were grown under agitation at 180 r.p.m in LB media (6 L) at 37 o C supplemented with 50 μg/mL kanamycin (KAN) until OD 600 reached ~0.8. The cultures were cooled down on ice for 30 min and induced with 1 mM of isopropyl-β-Dthiogalactoside (IPTG) (Euromedex) for 16 h at 16 °C. Bacteria were collected by centrifugation at 6,000 g for 20 min, resuspended in buffer A (50 mM Tris-HCl pH 8, 0.4 M NaCl, 0.5 mM βmercaptoethanol, and 1 mM benzamidine) and disrupted by sonication prior to removal of the cell debris by centrifugation at 28,000 g at 4 o C for 1 h. The clarified supernatant was then supplemented with 10 mM of imidazole pH8, incubated with Ni-Nitrilotriacetic acid sepharose beads for 15 min and loaded onto a gravity column. Extensive washes with sixteen column volumes of buffer B (50 mM Tris-HCl pH 8, 0.4 M NaCl, 20 mM imidazole and 0.5 mM β-mercaptoethanol) were performed prior to protein elution with buffer C (50 mM Tris-HCl pH 8, 0.4 M NaCl, 300 mM imidazole and 0.5 mM β-mercaptoethanol). The eluate was then incubated with TEV protease (1 mg of TEV protease per 40 mg of TtfA) and dialyzed overnight at 4 o C against buffer D (50 mM Tris-HCl pH 8, 0.6 M NaCl, 0.5 mM β-mercaptoethanol and 5% (v/v) glycerol). A Ni-Nitrilotriacetic acid sepharose column was used to remove the uncleaved-tagged protein as well as the His-tagged TEV protease. The tag-free protein was collected in the flow-through fractions and concentrated by ultrafiltration using a 10 kDa cut-off (Centricon; Sartorius). The protein was further purified by size-exclusion chromatography on a Superdex 200 Increase 10/300 GL column (GE Healthcare) and eluted with buffer D. The purity of the protein was estimated by Coomassie Blue-stained SDS/PAGE.

Figure 2 :

 2 Figure 2: Biochemical and structural characterization of TtfA. (A) Determination of the oligomeric state of TtfA in solution. The elution profile of the proteins used for calibration is displayed as a black line and the elution profile of TtfA is in red. Calibration was established using β-amylase (1) (200 kDa), bovine serum albumin (2) (66 kDa), carbonic anhydrase (3) (29 kDa), and cytochrome C (4) (12.4 kDa) as standards and eluted with estimated volumes of 10.9, 13.1, 15.7 and 17.1 mL, respectively. The void volume was estimated at 8.2 mL. TtfA elutes at 16.9 mL which corresponds to an apparent molecular weight of 14.4 kDa. The purity of TtfA after a three-step purification procedure is shown on the Coomassie Blue-stained SDS polyacrylamide gel electrophoresis, 10 μg of protein were loaded. (B) Overall cartoon representation of the TtfA crystal structure. Beta-strands colored in magenta are indicated with the β sign followed by a number, alpha and 3 10 helices are in slate color and are labeled with the α and η signs respectively. Nt and Ct stand for N-terminal and C-terminal. (C) Surface representation of TtfA. The electrostatic potential of the protein was calculated with the PDB2PQR Server, and displayed with the APBS module from Pymol. Red and blue color indicate negative and positive charges respectively.

Table 1 : Data collection and Refinement statistics

 1

	Data collection statistics	TtfA_native	TtfA_SeMet
	Beamline	X06DA-PXIII	X06DA-PXIII
	Wavelength (Å)	0.979	0.979
	Resolution range (Å)	46.54-1.4 (1.45-1.4) 46.59-1.45 (1.5-1.45)
	Space group	I 2 2 2	I 2 2 2
	Unit cell (Å,°)	62.24 70.09 86.01	62.15 70.39 85.69
		90 90 90	90 90 90
	Total reflections	168405 (15945)	440624 (42702)
	Multiplicity	4.5 (4.3)	13.3 (13.3)
	Completeness (%)	99.7 (99.4)	98.3 (96.7)
	Mean I/sigma(I)	14.7 (1.3)	22.9 (1.9)
	Wilson B-factor (Å 2 )	17.93	20.1
	R-meas	0.057 (1.1)	0.087 (1.4)
	CC1/2	0.99 (0.59)	0.99 (0.69)
	Data refinement statistics
	Reflections used in refinement	37303 (3670)
	R-work	0.1739 (0.2885)
	R-free	0.1984 (0.3149)
	Number of non-H atoms	1734
	macromolecules	1541
	ligands	10
	solvent	183
	Protein residues	178
	RMS bonds (Å)	0.013
	RMS angles (°)	1.23
	Ramachandran favored (%)	97.73
	Ramachandran allowed (%)	2.27
	Ramachandran outliers(%)	0.00
	Rotamer outliers (%)	0.00
	Average B-factor (Å 2 )	28.14
	macromolecules	27.37
	ligands	33.71
	solvent	34.29
	Clashscore	4.15
	PDB accession number	6T84

Acknowledgements

We thank Dr V. Olieric and the staff at SLS beamlines for support during data collection.

Funding body KLU for his Ph.D. fellowship and MB are supported by the National Research Agency [ANR-17-CE11-0008-01 -MyTraM]. HMABA is supported by a fellowship from the Lundbeck Foundation. This work was supported by the Fondation pour la Recherche Médicale (FRM) [grant number DEQ20150331719] to LK.

Data accessibility

The coordinates and structure factors have been deposited to the Protein Data Bank under the accession number: 6T84

Conflicts of interest

The authors declare no potential conflict of interest.

Authors Contribution

KLU and MB designed research, performed the experiments and data analysis. HMABA and MB collected x-ray data. LK and MB supervised research. MB wrote the first draft and all the authors contributed to the proofreading of the manuscript.


Ignasi Sau
email: ignasi.sau@lirmm.fr

Uéverton Dos
email: ueverton@ic.uff.br

Santos Souza

Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs

Keywords: 2012 ACM Subject Classification Theory of computation → parameterized complexity, induced subgraphs, treewidth, hitting subgraphs, dynamic programming, lower bound, Exponential Time Hypothesis Digital Object Identifier 10.4230/LIPIcs.MFCS.2020.82

For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, for the minimum size of a set S ⊆ V (G) such that G \ S does not contain H as an induced subgraph. Motivated by previous work about hitting (topological) minors and subgraphs on bounded treewidth graphs, we are interested in determining, for a fixed graph H, the smallest function fH (t) such that H-IS-Deletion can be solved in time fH (t) • n O(1) assuming the Exponential Time Hypothesis (ETH), where t and n denote the treewidth and the number of vertices of the input graph, respectively.

We show that fH (t) = 2 O(t h-2 ) for every graph H on h ≥ 3 vertices, and that fH (t) = 2 O(t) if H is a clique or an independent set. We present a number of lower bounds by generalizing a reduction of Cygan et al. [MFCS 2014] for the subgraph version. In particular, we show that when H deviates slightly from a clique, the function fH (t) suffers a sharp jump: if H is obtained from a clique of size h by removing one edge, then fH (t) = 2 Θ(t h-2 ) . We also show that fH (t) = 2 Ω(t h ) when H = K h,h , and this reduction answers an open question of Mi. Pilipczuk [MFCS 2011] about the function fC 4 (t) for the subgraph version.

Motivated by Cygan et al. [MFCS 2014], we also consider the colorful variant of the problem, where each vertex of G is colored with some color from V (H) and we require to hit only induced copies of H with matching colors. In this case, we determine, under the ETH, the function fH (t) for every connected graph H on h vertices: if h ≤ 2 the problem can be solved in polynomial time; if h ≥ 3, fH (t) = 2 Θ(t) if H is a clique, and fH (t) = 2 Θ(t h-2 ) otherwise.

Introduction

Graph modification problems play a central role in modern algorithmic graph theory. The most general form of such a problem is determined by a target graph class G and some prespecified set M of allowed local modifications, and the question is, given an input graph G and an integer k, whether it is possible to transform G to a graph in G by applying k time, we need to use a slightly non-trivial encoding in the tables that generalizes an idea of Bonomo-Braberman et al. [START_REF] Bonomo-Braberman | Linear-time algorithms for eliminating claws in graphs[END_REF], by introducing an object that we call rooted H-folio, inspired by similar encodings in the context of graph minors [START_REF] Adler | Faster parameterized algorithms for minor containment[END_REF][START_REF] Baste | Hitting minors on bounded treewidth graphs. I. General upper bounds[END_REF].

It turns out that when H is a clique or an independent set (in particular, when |V (H)| ≤ 2), the problem can be solved in single-exponential time, that is, f H (t) = 2 O(t) . The case of cliques (Theorem 5), which coincides with the subgraph version, had been already observed by Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF], using essentially the folklore fact that every clique is contained in some bag of a tree decomposition. The case of independent sets (Theorem 8) is more interesting, as we exploit tree decompositions in a novel way, by showing (Lemma 6) that a chordal completion of the complement of a solution can be covered by a constant number of cliques, which implies (Lemma 7) that the complement of a solution is contained in a constant number of bags of the given tree decomposition.

Our main technical contribution consists of lower bounds. Somehow surprisingly, we show (Theorem 10) that when H deviates slightly from a clique, the function f H (t) suffers a sharp jump: if H is obtained from a clique of size h by removing one edge, then f H (t) = 2 Ω(t h-2 ) , and this bound is tight by Theorem 2. We also provide lower bounds for other graphs H that are "close" to cliques (Theorem 10; see also the full version), some of them being tight. In particular, we show (Theorem 12) that when H = K h,h , we have that f H (t) = 2 Ω(t h ) . By observing that the proof of the latter lower bound also applies to occurrences of K h,h as a subgraph, the particular case h = 2 (Corollary 13) answers the open question of Mi. Pilipczuk [START_REF] Pilipczuk | Problems parameterized by treewidth tractable in single exponential time: A logical approach[END_REF] about the function f C4 (t). All these reductions are inspired by a reduction of Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF] for the subgraph version. We first present the general frame of the reduction together with some properties that the eventual instances constructed for each of the graphs H have to satisfy, yielding in a unified way (Lemma 9) lower bounds for the corresponding problems.

Motivated by the work of Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF], we also consider the colorful variant of the problem, where the input graph G comes equipped with a coloring σ : V (G) → V (H) and we are only interested in hitting induced subgraphs of G isomorphic to H such that their colors match. In this case, we first observe that essentially the same dynamic programming algorithm of the non-colored version (Theorem 3) yields the upper bound f

H (t) = 2 O(t h-2 )
for every graph H on h ≥ 3 vertices. Again, our main contribution concerns lower bounds: we show (Theorem 14), by modifying appropriately the frame introduced for the non-colored version, that f H (t) = 2 Ω(t h-2 ) for every graph H having a connected component on h vertices that is not a clique. Since the case where H is a clique can also be easily solved in single-exponential time (Theorem 5), which can be shown (Theorem 15) to be optimal, it follows that if

H is a connected graph on h ≥ 3 vertices, f H (t) = 2 Θ(t) if H is a clique, and f H (t) = 2 Θ(t h-2 )
otherwise. It is easy to see that the cases where |V (H)| ≤ 2 can be solved in polynomial time by computing a minimum vertex cover in a bipartite graph.

Organization.

In Section 2 we provide some basic preliminaries and formally define the problems. In Section 3 we present the algorithms for both problems, and in Section 4 (resp. Section 5) we provide the lower bounds for the non-colored (resp. colored) version. Finally, we conclude the article in Section 6 with some open questions. Due to space limitations, the proofs of the results marked with "( )" can be found in the full version of this article, available at https://arxiv.org/abs/2004.08324.

M F C S 2 0 2 0

82:4

Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs

Preliminaries

Graphs and functions. We use standard graph-theoretic notation, and we refer the reader to [START_REF] Diestel | Graph Theory[END_REF] for any undefined notation. We will only consider undirected graphs without loops nor multiple edges, and we denote an edge between two vertices u and v by {u, v}. A subgraph H of a graph G is induced if H can be obtained from G by deleting vertices. A graph G is H-free if it does not contain any induced subgraph isomorphic to H. For a graph G and a set S ⊆ V (G), we use the notation

G \ S := G[V (G) \ S]. A vertex v is complete (resp. anticomplete) to a set S ⊆ V (G) if v is
(f ) the image of f , that is, im(f ) = {b ∈ B | ∃a ∈ A : f (a) = b}.
For an integer k ≥ 1, we let [k] be the set containing all integers i with 1 ≤ i ≤ k.

Tree decompositions.

A tree decomposition of a graph G is a pair D = (T, X ), where T is a tree and X = {X w | w ∈ V (T )} is a collection of subsets of V (G), called bags, such that: w∈V (T ) X w = V (G), for every edge {u, v} ∈ E, there is a w ∈ V (T ) such that {u, v} ⊆ X w , and for each {x, y, z} ⊆ V (T ) such that z lies on the unique path between x and y in T , X x ∩ X y ⊆ X z . We call the vertices of T nodes of D and the sets in X bags of D. The width of a tree decomposition D = (T, X ) is max w∈V (T ) |X w | -1. The treewidth of a graph G, denoted by tw(G), is the smallest integer t such that there exists a tree decomposition of G of width at most t. We need to introduce nice tree decompositions, which will make the presentation of the algorithms much simpler.

Nice tree decompositions. Let D = (T, X ) be a tree decomposition of G, r be a vertex of T , and G = {G w | w ∈ V (T )} be a collection of subgraphs of G, indexed by the vertices of T . A triple (D, r, G) is a nice tree decomposition of G if the following conditions hold:

X r = ∅ and G r = G, each node of D has at most two children in T , for each leaf ∈ V (T ), X = ∅ and G = (∅, ∅). Such an is called a leaf node, if w ∈ V (T ) has exactly one child w , then either

X w = X w ∪ {v in } for some v in ∈ X w and G w = G[V (G w ) ∪ {v in }].
The node w is called an introduce node and the vertex v in is the introduced vertex of X w , X w = X w \ {v out } for some v out ∈ X w and G w = G w . The node w is called a forget node node and v out is the forget vertex of X w .

if w ∈ V (T ) has exactly two children w 1 and w 2 , then

X w = X w1 = X w2 , E(G w1 ) ∩ E(G w2 ) = E(G[X w ]), and G w = (V (G w1 ) ∪ V (G w2 ), E(G w1 ) ∪ E(G w2 ))
. The node w is called a join node.

For each w ∈ V (T ), we denote by V w the set V (G w ). Given a tree decomposition, it is possible to transform it in polynomial time to a nice one of the same width [START_REF] Kloks | Computations and Approximations[END_REF]. Moreover, by Bodlaender et al. [START_REF] Hans | A c k n 5-Approximation Algorithm for Treewidth[END_REF] we can find in time 2 O(tw) • n a tree decomposition of width O(tw) of any graph G. Hence, since the running time of our algorithms dominates this function, we may assume that a nice tree decomposition of width t = O(tw) is given along with the input.

Definition of the problems. Before formally defining the problems considered in this article, we introduce some terminology, mostly taken from [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF]. Given a graph H, an

H-coloring of a graph G is a function σ : V (G) → V (H). A homomorphism (resp. induced homomorphism from a graph H to a graph G is a function π : V (H) → V (G) such that {u, v} ∈ E(H) implies (resp. if and only if) {π(u), π(v)} ∈ E(G). When G is H-colored by a function σ, an (induced) σ-homomorphism from H to G is an (induced) homomorphism π from H to G with the additional property that every vertex is mapped to the appropriate color, that is, σ(π(a)) = a for every vertex a ∈ V (H). An (induced) H-subgraph of G is an (induced) injective homomorphism from H to G and, if G is H-colored by a function σ, an (induced) σ-H-subgraph of G is an (induced) injective σ-homomorphism from H to G. We say that a vertex set X ⊆ V (G) hits an (induced) σ-H-subgraph π if X ∩ π(V (H)) = ∅.
For a fixed graph H, the problems we consider in this article are defined as follows.

H-IS-Deletion

Input: A graph G.

Output:

The minimum size of a set X ⊆ V (G) that hits all induced H-subgraphs of G.

Colorful H-IS-Deletion

Input: A graph G and an H-coloring σ of G.

Output:

The minimum size of a set X ⊆ V (G) that hits all induced σ-H-subgraphs of G.

The H-S-Deletion and Colorful H-S-Deletion problems are defined similarly, just by removing the word "induced" from the above definitions. In the decision version of these problems, we are given a target budget k, and the objective is to decide whether there exists a hitting set of size at most k. Unless stated otherwise, we let n denote the number of vertices of the input graph of problem under consideration. When expressing the running time of an algorithm, we will sometimes use the O * (•) notation, which suppresses polynomial factors in the input size. [START_REF] Impagliazzo | On the Complexity of k-SAT[END_REF] implies that the 3-Sat problem on n variables cannot be solved in time 2 o(n) . The Sparsification Lemma of Impagliazzo et al. [START_REF] Impagliazzo | Which Problems Have Strongly Exponential Complexity[END_REF] implies that if the ETH holds, then there is no algorithm solving a 3-Sat formula with n variables and m clauses in time 2 o(n+m) . Using the terminology from Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF], a 3-Sat formula ϕ, in conjunctive normal form, is said to be clean if each variable of ϕ appears exactly three times, at least once positively and at least once negatively, and each clause of ϕ contains two or three literals and does not contain twice the same variable. Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF] observed the following useful lemma.

Exponential Time Hypothesis. The Exponential Time Hypothesis (ETH) of Impagliazzo and Paturi

Lemma 1 (Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF]). The existence of an algorithm in time 2 o(n) deciding whether a clean 3-Sat formula with n variables is satisfiable would violate the ETH.

Algorithms

In this section we present algorithms for H-IS-Deletion and Colorful H-IS-Deletion. We start in Subsection 3.1 with a general dynamic programming algorithm that solves

H-IS-Deletion and Colorful H-IS-Deletion in time O * (2 O(t h-2 )
) for any graph H on at least h ≥ 3 vertices. In Subsection 3.2 we focus on hitting cliques and independent sets.

A general dynamic programming algorithm

We present the algorithm for H-IS-Deletion, and then we discuss that essentially the same algorithm applies to Colorful H-IS-Deletion as well. Our algorithm to solve

H-IS-Deletion in time O * (2 O(t h-2 )
) uses standard dynamic programming over a nice tree decomposition of the input graph; we refer the reader to [START_REF] Cygan | Parameterized Algorithms[END_REF] for a nice exposition. However, in order to achieve the claimed running time, we need to use a slightly non-trivial encoding in the tables, which we proceed to explain.

Let |V (H)| = h and assume that we are given a nice tree decomposition of the input graph G such that its bags contain at most t vertices (in a tree decomposition of width t, the bags have size at most t + 1, but to simplify the exposition we assume that they have size at most t, which does not change the asymptotic complexity of the algorithm).

Intuitively, our algorithm proceeds as follows. At each bag X w of the nice tree decomposition of G, a state is indexed by the intersection of the desired hitting set constructed so far with the bag, and the collection of proper subgraphs of H that occur as induced subgraphs in the graph obtained from G w after removing the current solution. In order to be able to proceed with the dynamic programming routine while keeping the complement of the hitting set H-free, we need to remember how these proper subgraphs of H intersect with X w , and this is the most expensive part of the algorithm in terms of running time. We encode this collection of rooted subgraphs of H (where the "roots" correspond to the vertices in X w ) with an object H w that we call a rooted H-folio, inspired by similar encodings in the context of graph minors [START_REF] Adler | Faster parameterized algorithms for minor containment[END_REF][START_REF] Baste | Hitting minors on bounded treewidth graphs. I. General upper bounds[END_REF]. Since we need to remember proper subgraphs of H on at most h -1 vertices, and we have up to t choices to root each of their vertices in the bag X w , the number of rooted proper subgraphs of H is at most t h-1 . Therefore, the number of rooted H-folios, each corresponding to a collection of rooted proper subgraphs of H, is bounded above by 2 t h-1 . This encoding naturally leads to a dynamic programming algorithm to solve

H-IS-Deletion in time O * (2 O(t h-1 )
), where the hidden constants may depend on H.

In order to further reduce the exponent to h -2, we use the following trick inspired by the dynamic programming algorithm of Bonomo-Braberman et al. [START_REF] Bonomo-Braberman | Linear-time algorithms for eliminating claws in graphs[END_REF] to solve

K 1,3 -IS-Deletion in time O * (2 O(t 2 )
). The crucial observation is the following: the existence of proper induced subgraphs of H that are fully contained in the current bag X w can be checked locally within that bag, without needing to root their vertices. That is, we distinguish these local occurrences of proper induced subgraphs of H, and we encode them separately in H w , without rooting their vertices in X w . Note that the number of choices for those local occurrences depends only on H. In particular, since the proper subgraphs of H have at most h -1 vertices, the previous observation implies that we never need to root exactly h -1 vertices of an induced subgraph of H, since such occurrences would be fully contained in X w . This permits to improve the running time to O * (2 O(t h-2 ) ). The details can be found in the full version.

Note that we may assume that H has at least three vertices, as otherwise it is a clique or an independent set, and then H-IS-Deletion can be solved in single-exponential time by the algorithms in Subsection 3.

Lower bounds for H-IS-Deletion

In this section we present lower bounds for the H-IS-Deletion problem. Our reductions will be from the 3-Sat problem restricted to clean formulas, and are strongly inspired by a reduction of Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF] for the H-S-Deletion problem when H is the graph obtained from K 2,h by attaching a triangle to each of the two vertices of degree h. We start by presenting the general frame of the reductions together with some generic properties that our eventual instances of H-IS-Deletion will satisfy, which allow to prove in a unified way (cf. Lemma 9) the equivalence of the instances. Variations of this general frame will yield the concrete reductions for distinct graphs H (cf. Theorems 10 and 12).

General frame of the reductions. Given a clean 3-Sat formula ϕ with n variables and m clauses, we proceed to build a so-called frame graph F H,ϕ . For each graph H considered in the reductions, F H,ϕ will be enhanced with additional vertices and edges, obtaining a graph G H,ϕ that will be the constructed instance of the H-IS-Deletion problem.

Let h be an integer depending on H, to be specified in each particular reduction, and let s be the smallest positive integer such that s h ≥ 3n, and note that s = O(n 1/h ). We introduce a set of vertices M = {w i,j | i ∈ [s], j ∈ [h]}, which we call the central part of the frame. One may think of this set M as a matrix with s rows and h columns. We will sometimes add an extra set T of vertices to the central part, with |T | depending on H, obtaining an enhanced central part M = M ∪ T .

Let L be a graph depending on each particular graph H. By attaching a copy of L between two vertices u, v ∈ V (F H,ϕ ) we mean adding a new copy of L, choosing two arbitrary distinct vertices of L, and identifying them with u and v respectively.

For each variable x of ϕ and for each clause C containing x in a literal ∈ {x, x}, we add to F ϕ a new vertex a x,C, . We also introduce another "dummy" vertex a x . Since ϕ is clean, we have introduced four vertices in F H,ϕ for each variable x. Let a x,C1, , a x,C2, ¯ , a x,C3, , a x be the four introduced vertices (recall that x appears at least once positively and negatively in ϕ). We attach a copy of L between the following four pairs of vertices: (a x,C1, , a x,C2, ¯ ), (a x,C2, ¯ , a x,C3, ), (a x,C3, , a x ), and (a x , a x,C1, ). We denote by A the union of all the vertices in these variable gadgets.

For each clause C of ϕ and for each literal in C, we add to F ϕ a new vertex b C, . Since ϕ is clean, we have introduced two or three vertices in F H,ϕ for each clause C. We attach a copy of L between every pair of these vertices. We denote by B the union of all the vertices in these clause gadgets. This concludes the construction of the frame F H,ϕ ; cf. Figure 1. In all our reductions, the graph G H,ϕ will satisfy the following property: P1: All the connected components of G H,ϕ \ M are of size bounded by a function of H. Also, in all our reductions the budget that we set for the solution of H-IS-Deletion on G H,ϕ is k := 2n + C∈ϕ (|C| -1) = 5n -m, where |C| denotes the number of literals in clause C. For each fixed graph H, the choice of k, the edges within M , and the edges between M and the sets A, B will force the following behavior in G H,ϕ : P2: For each gadget corresponding to a variable x, at least one of the pairs (a x,C1, , a x,C3, ) and (a x , a x,C2, ¯ ) needs to be in the solution and, for each gadget corresponding to a clause C, at least |C| -1 vertices in the set {b C, | ∈ C} need to be in the solution.

The above property together with the choice of k imply that the budget is tight: exactly one of the pairs (a x,C1, , a x,C3, ) and (a x , a x,C2, ¯ ) is in the solution, thereby defining the M F C S 2 0 2 0 82:10 Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs true/false assignment of variable x; and exactly one of the vertices in {b C, | ∈ C} is not in the solution, corresponding to a satisfied literal in C. More precisely, our graph G H,ϕ will satisfy the following key property: We now show that the above three properties are enough to construct the desired reductions.

w 1,1 w 2,1 w s,1 w i,j w s,h w 1,h w 1,2 M h s B A L L L b C, 1 b C, 2 b C, 3 a x,C 3 , M T a x,C 2 , ¯ L L L a x,C 1 , a x a x,C 2 , ¯ L a x,C 1 , a x
P3: Let X ⊆ V (G H,ϕ ) contain

Lemma 9 ( ).

Let H be fixed graph and, given a clean 3-Sat formula ϕ, let G H,ϕ be a graph constructed starting from the frame graph F H,ϕ described above, where the central part M has h columns for some constant h ≥ 1 depending on H. If G H,ϕ satisfies properties P1, P2, and P3, then the H-IS-Deletion problem cannot be solved in time O * (2 o(t h ) ) unless the ETH fails, where t is the width of a given tree decomposition of the input graph.

We now proceed to describe concrete reductions for several instantiations of H. In order to add edges between the enhanced central part M and the sets A, B, we use the following nice trick introduced in [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF]. To each pair (C, ), where C is a clause of ϕ and is a literal in C, we assign a function f C, : [h] → [s]. We assign these functions in such a way that f C, = f C , whenever (C, ) = (C , ); note that this is possible by the choice of s and the fact that, since ϕ is clean, each clause contains at most three literals. We assume henceforth that these functions are fixed. We start with the following result that provides tight lower bounds for two graphs that are "close" to a clique. Theorem 10. Let h ≥ 1 be a fixed integer and let H ∈ {K h+2 -e, K h + I 2 }. Then, unless the ETH fails, the H-IS-Deletion problem cannot be solved in time O * (2 o(t h ) ), where t is the width of a given tree decomposition of the input graph.

Proof. For each graph H ∈ {K h+2 -e, K h + I 2 }, we will present a reduction from the 3-Sat problem restricted to clean formulas. Given such a formula ϕ, let F H,ϕ be the frame graph described above, where the constant h, the graph L, and the set T will be specified below for each H. In each case, we will build, starting from F H,ϕ , an instance G H,ϕ of H-IS-Deletion with budget k = 5n -m satisfying properties P1, P2, and P3, and then Lemma 9 will imply the claimed lower bound.

We focus here on the case H = K h +2 -e for some h ≥ 1, and the case H = K h + I 2 can be found in the full version. Let F H,ϕ be the frame graph with h = h , L = K h+2 -e, and T = ∅. We add an edge between any two vertices w i,j , w i ,j ∈ M with j = j . That is, we turn G H,ϕ [M ] into a complete h-partite graph, where each part has size s. For each clause C and each literal in C, where ∈ {x, x} for some variable x, we add the edges {a C,x, , w f C, (j),j } and {b C, , w f C, (j),j } for every j ∈ [h]. This concludes the construction of G H,ϕ , which clearly satisfies property P1. By the choice of k and the fact that there is a copy of H between the corresponding vertices of A and B (cf. Figure 1), property P2 holds as well. Let X ⊆ V (G H,ϕ ) be a set as in property P3, and let H be an induced subgraph of G Note that, in the proof of Theorem 2 for H = K h+2 -e, all the occurrences of H in G H,ϕ are induced, and therefore the lower bound also applies to the (K h+2 -e)-S-Deletion problem. On the other hand, for H = K h + I 2 the proof of Theorem 2 strongly uses the fact that H cannot occur as an induced subgraph. The following lemma explains why the proof does not work for the subgraph version: it can be easily solved in single-exponential time. This points out an interesting difference between both problems. Lemma 11 ( ). For every two fixed integers h ≥ 1 and ≥ 0, the (K h + I )-S-Deletion problem can be solved in time O * (2 O(t) ), where t is the width of a given tree decomposition of the input graph.

H,ϕ \ X isomorphic to H. Since ω(G H,ϕ [M ]) = h, ω(G H,ϕ [(A ∪ B) \ X]) ≤ h,
By Theorem 2, the lower bounds presented in Theorem 10 for H ∈ {K h+2 -e, K h + I 2 } are tight under the ETH. These two graphs are very symmetric, in the sense that each of them contains two non-adjacent vertices that are either complete or anticomplete to a "central" clique K h (cf. Figure 2). Unfortunately, for graphs without two such non-adjacent symmetric vertices, our framework described above is not capable of obtaining tight lower bounds. Nevertheless, in the full version we show how to obtain lower bounds for other graphs, namely for the graph K h+1 + v x for 0 ≤ x ≤ h -1, defined as the graph obtained from K h+1 by adding a vertex v adjacent to x vertices in the clique (cf. Figure 2). Another direction for generalizing the lower bound of Theorem 10 to other graphs H is to complete bipartite graphs.

K h + I 2 K h a b K h+1 + v x K h a b x K h+2 -e K h a b
Theorem 12 ( ). For any integer h ≥ 2, the K h,h -IS-Deletion problem cannot be solved in time O * (2 o(t h ) ) unless the ETH fails, where t is the width of a given tree decomposition of the input graph. M F C S 2 0 2 0 82:12 Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs It can be easily verified that the proof of Theorem 12 works for both K h,h -IS-Deletion and K h,h -S-Deletion, since all the occurrences of K h,h in the constructed graph G H,ϕ are induced. Hence, as the particular case of Theorem 12 for h = 2 we get the following corollary, which answers a question of Mi. Pilipczuk [START_REF] Pilipczuk | Problems parameterized by treewidth tractable in single exponential time: A logical approach[END_REF] about the asymptotic complexity of C 4 -S-Deletion parameterized by treewidth. As mentioned in [START_REF] Pilipczuk | Problems parameterized by treewidth tractable in single exponential time: A logical approach[END_REF], C 4 -S-Deletion can be easily solved in time O * (2 O(t 2 ) ). This fact together with Theorem 2 imply that both lower bounds of Corollary 13 are tight.

We can obtain lower bounds for other graphs H that are "close" to a complete bipartite graph. Indeed, note that the lower bound of Theorem 12 also applies to the graph H obtained from K h,h by turning one of the two parts into a clique: the same reduction works similarly, and the only change in the construction is to turn the whole central part M into a clique. We can also consider complete bipartite graphs K a,b with parts of different sizes, by letting the number of columns of the central part M be equal to max{a, b}, hence obtaining a lower bound of O * (2 o(t max{a,b} ) ). Similarly, we can also turn one of the two parts of K a,b into a clique, and obtain the same lower bound. In particular, in this way we can obtain a lower bound of O * (2 o(t h ) ) for the graph H obtained from K h+3 by removing the edges in a triangle.

Lower bounds for Colorful H-IS-Deletion

Our main reduction for the colored version is again strongly inspired by the corresponding reduction of Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF] for the non-induced version. The main difference with respect to their reduction is that in the non-induced version, the graph H is required to contain a connected component that is neither a clique nor a path, while for the induced version we only require a component that is not a clique, and therefore we need extra arguments to deal with the case where all the connected components of H are paths.

Theorem 14 ( ). Let H be a graph having a connected component on h vertices that is not a clique. Then Colorful H-IS-Deletion cannot be solved in time O * (2 o(t h-2 ) ) unless the ETH fails, where t is the width of a given tree decomposition of the input graph.

When H is a connected graph, the lower bound of Theorem 14 together with the algorithms given by Proposition 5 and Theorem 3 completely settle, under the ETH, the asymptotic complexity of Colorful H-IS-Deletion parameterized by treewidth. Note that, in particular, Theorem 14 applies when H is path, in contrast to the subgraph version that can be solved in polynomial time [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF].

Therefore, what remains is to obtain tight lower bounds when H is disconnected. In particular, Theorem 14 cannot be applied at all when all the connected components of H are cliques, since the machinery that we developed (inspired by Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF]) using the framework graph F H,ϕ crucially needs two non-adjacent vertices in the same connected component. Let us now focus on those graphs, sometimes called cluster graphs in the literature.

As mentioned in Section 3, both Colorful K 2 -IS-Deletion and Colorful I 2 -IS-Deletion can be solved in polynomial time. In our next result we show that if H is slightly larger than these two graphs (namely, K 2 or I 2 ), then Colorful H-IS-Deletion becomes hard. Namely, we provide a single-exponential lower bound for the following three graphs H on three vertices that are not covered by Theorem 14: K 3 , I 3 , and K 2 + K 1 . Note that these lower bounds are tight by the algorithm of Theorem 3.

Theorem 15 ( ). Let H ∈ {K 3 , I 3 , K 2 + K 1 }. Then, unless the ETH fails, the Colorful H-IS-Deletion problem cannot be solved in time O * (2 o(t) ), where t is the width of a given tree decomposition of the input graph.

The proof of Theorem 15 can be easily adapted to H = P 3 by complementing the appropriate neighborhoods, hence obtaining a lower bound of O * (2 o(t) ) for P 3 -IS-Deletion. Note, however, that this lower for P 3 bound already follows from Theorem 14.

It is also easy to adapt the proof of Theorem 15 to larger graphs, but then the lower bound of O * (2 o(t) ) is not tight anymore. For example, for H = 2K 2 (the disjoint union of two edges), with V (H) = {z 1 , z 2 , z 3 , z 4 } such that the edges are {z 1 , z 2 } and {z 3 , z 4 }, it suffices to take the instance (G K2+K1 , σ) of (K 2 + K 1 )-IS-Deletion defined above and to add a private neighbor colored z 4 for every vertex of G K2+K1 colored z 3 . Also, for H = K h with h ≥ 4, in the gadget L we just replace the triangles by cliques of size h, and for H = I h with h ≥ 4, we take the h-partite complement of the previous instance of K h -IS-Deletion.

Further research

Concerning H-IS-Deletion, the complexity gap is still quite large for most graphs H, as our lower bounds (Theorems 10 and 12) only apply to graphs H that are "close" to cliques or complete bipartite graphs. In particular, Theorem 10 provides tight bounds for P 3 or K 4 -e (the diamond), but we do not know the tight function f H (t) for other small graphs H on four vertices such as P 4 , K 1,3 (the claw), or 2K 2 . We think that for most graphs H on h vertices, the upper bound f H (t) = 2 O(t h-2 ) given by Theorem 2 is the asymptotically tight function, and that the single-exponential algorithms for cliques and independent sets are isolated exceptions. The reason is that, in contrast to the subgraph version, when hitting induced subgraphs, edges and non-edges behave essentially in the same way when performing dynamic programming, as one has to keep track of both the existence and the non-existence of edges in order to construct the tables, and storing this information seems to be unavoidable.

As for Colorful H-IS-Deletion, in view of Theorems 3, 5, 14, and 15, only the cases where H is a disjoint union of at least two cliques and |V (H)| ≥ 4 remain open. In particular, when H is an independent set or a matching with |V (H)| ≥ 4.

Figure 1

 1 Figure 1 Illustration of the general frame graph FH,ϕ.

  and ω(H) = h + 1, H intersects both M and A ∪ B. Moreover, since no two adjacent vertices in (A ∪ B) \ X have neighbors in M , necessarily |V ( H) ∩ (A ∪ B)| = 2 and V ( H) ∩ M induces a clique of size h, which implies that H contains a vertex in each column of M . By the definition of the functions f C, and the construction of G H,ϕ , the two vertices in V ( H) ∩ (A ∪ B) must be a x,C, ∈ A and b C , ∈ B with (C, ) = (C , ), and therefore property P3 follows and we are done by Lemma 9.

Figure 2

 2 Figure 2 Graphs H considered in Theorem 10 and in the lower bounds presented in the full version.

Corollary 13 .

 13 Neither C 4 -IS-Deletion nor C 4 -S-Deletion can be solved in time O * (2 o(t 2 )) unless the ETH fails, where t is the width of a given tree decomposition of the input graph.

  adjacent (resp. not adjacent) to every vertex in S. A vertex set S of a connected graph G is a separator if G \ S is disconnected.We denote by ∆(G) (resp. ω(G)) the maximum vertex degree (resp. clique size) of a graph G. For an integer h ≥ 1, we denote by P h (resp. I h , K h ) the path (resp. independent set, clique) on h vertices, and by K h -e the graph obtained from K h by deleting one edge. For two integers a, b ≥ 1, we denote by K a,b the bipartite graph with parts of sizes a and b. We denote the disjoint union of two graphs G 1 and G 2 byG 1 + G 2 .A graph property is hereditary if whenever it holds for a graph G, it holds for all its induced subgraphs as well. The open (resp. closed) neighborhood of a vertex v is denoted by N (v) (resp. N [v]). A vertex is simplicial if its (open or closed) neighborhood induces a clique. A graph G is chordal if it does not contain induced cycles of length at least four or, equivalently, if V (G) can be ordered v 1 , . . . , v n such that, for every 2 ≤ i ≤ n, vertex v i is simplicial in the subgraph of G induced by {v 1 , . . . , v i-1 }. Note that being chordal is a hereditary property.Given a function f : A → B between two sets A and B and a subset A ⊆ A, we denote by f | A the restriction of f to A and by im

CAPES-PRINT Institutional Internationalization Program, process 88887. 371209/ 2019-00, and projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010). Uéverton dos Santos Souza: Grant E-26/203.272/2017 Rio de Janeiro Research Foundation (FAPERJ) and Grant 303726/2017-2 National Council for Scientific and Technological Development (CNPq).

1 © Ignasi Sau and Uéverton dos Santos Souza; licensed under Creative

Theorem 2 ( ). For every graph H on h ≥ 3 vertices, the H-IS-Deletion problem can be solved in time 2 O(t h-2 ) • n, where n and t are the number of vertices and the treewidth of the input graph, respectively.

A dynamic programming algorithm similar to the one provided in Theorem 2 can also solve the Colorful H-IS-Deletion problem in time 2 O(t h-2 ) • n for every graph H on h ≥ 3 vertices. Indeed, the algorithm remains basically the same, except that we have to keep track only of colorful copies of proper subgraphs of H, and to discard only the states in which a colorful occurrence of H appears. In order to do that, in the tables of the dynamic programming algorithm we just need to replace rooted H-folios by rooted σ-H-folios, defined in the natural way. Since the number of further computations at each node in order to verify that the colors match in the obtained rooted subgraphs of H is a function dominated by 2 O(t h-2 ) , we obtain the same asymptotic running time. We omit the details.

Theorem 3. For every graph

• n, where n and t are the number of vertices and the treewidth of the input graph, respectively.

Hitting cliques and independent sets

The following folklore lemma follows easily from the definition of tree decomposition. Lemma 4. Let G be a graph and let D be a tree decomposition of G. Then every clique of G is contained in some bag of D.

Note that if H is a clique, then the (Colorful) H-IS-Deletion problem is the same as the (Colorful) H-S-Deletion problem. Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF] observed that, by Lemma 4, in order to solve (Colorful) K h -IS-Deletion it is enough to store, for every bag of a (nice) tree decomposition of the input graph, the subset of vertices of the bag that belongs to the partial hitting set, and to check locally within the bag that the remaining vertices do not induce a K h . A typical dynamic programming routine yields the following result 1 .

Theorem 5 (Cygan et al. [13]). For every integer h ≥ 1, K h -IS-Deletion and Colorful

• n, where n and t are the number of vertices and the treewidth of the input graph, respectively.

The case where H is an independent set, which is NP-hard by [START_REF] Lewis | The Node-Deletion Problem for Hereditary Properties is NP-Complete[END_REF], turns out to be more interesting. We proceed to present a single-exponential algorithm for I h -IS-Deletion, and we remark that this algorithm does not apply to the colorful version.

Note that I 2 -IS-Deletion is dual to Maximum Clique, since a minimum I 2 -hitting set is the complement of a maximum clique. This duality together with Lemma 4 yield the following key insight: in any graph G, after the removal of an optimal solution of I 2 -IS-Deletion, all the remaining vertices are contained in a single bag of any tree decomposition of G. Our algorithm is based on a generalization of this property to any h ≥ 1, stated in Lemma 7, which gives an alternative way to exploit tree decompositions in order to solve the H-IS-Deletion problem. We first need a technical lemma. A clique cover of a graph G is a collection of cliques of G that cover V (G), and its size is the number of cliques in the cover. Lemma 6. Every I h -free chordal graph G admits a clique cover of size at most h -1. 1 In fact, Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF] presented an algorithm only for Colorful K h -S-Deletion, but the algorithm for K h -S-Deletion is just a simplified version of the colorful version, just by forgetting the colors.

M F C S 2 0 2 0 82:8

Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs Proof. We prove the lemma by induction on h. For h = 2, G itself is a clique and the claim is trivial. Suppose inductively that any I h-1 -free chordal graph admits a clique cover of size at most h -2, let G be an I h -free chordal graph, and let v be a simplicial vertex of G. Since

admits a clique cover of size at most h -2. These h -2 cliques together with N [v] define a clique cover of G of size at most h -1.

Lemma 7.

Let h ≥ 2 be an integer, let G be a graph, let D be a tree decomposition of G, and let S be any solution for I h -IS-Deletion on G. Then there are at most h -1 bags

Proof. Let D be a tree decomposition of G, let S be a solution for I h -IS-Deletion on G, and let G be the graph obtained from G by adding an edge between any pair of vertices contained in the same bag of D. Note that G is a chordal graph, and that D is also a tree decomposition of G . Since being a chordal graph is a hereditary property, it follows that G \ S is chordal. Since G \ S is I h -free, and the property of being I h -free is closed under edge addition, we have that G \ S is also I h -free. Thus, G \ S is an I h -free chordal graph, and Lemma 6 implies that G \ S admits a clique cover of size at most h -1. Since any clique in G \ S is also a clique in G , and D is a tree decomposition of G , Lemma 4 implies that every clique of G \ S is contained in some bag of D, and therefore there are at most

Recall that I h -IS-Deletion is NP-hard even for h = 2, thus the problem cannot be solved in time n f (h) for any function f , unless P = NP.

Theorem 8. For every integer

where n and t are the number of vertices and the treewidth of the input graph, respectively.

Proof. For h = 1 the problem can be trivially solved in linear time, so assume h ≥ 2. Let D be a tree decomposition of G with width t, and let S be an (unknown) optimal solution for I h -IS-Deletion on G. By Lemma 7, there are at most h -1 bags X 1 , X 2 , . . . , X h-1 of D such that V (G) \ S ⊆ i∈[h-1] X i . Since we may assume that D has O(n) nodes [START_REF] Kloks | Computations and Approximations[END_REF], we can enumerate the candidate sets of bags X 1 , X 2 , . . . , X h-1 in time O(n h-1 ). For each such fixed set X 1 , X 2 , . . . , X h-1 , we generate all subsets S ⊆ i∈[h-1] X i , which are at most 2 (h-1)(t+1) many, and for each S we check whether the graph G [ S] is I h -free, in time 2 t • t O (1) • n, by computing a maximum independent set of G [ S] using dynamic programming based on treewidth [START_REF] Cygan | Parameterized Algorithms[END_REF] (note that having treewidth at most t is a hereditary property). Note that, by Lemma 7, there exists some of the considered sets S such that V (G) \ S = S, and therefore an optimal solution S of

We would like to mention that the approach used in the algorithm of Theorem 8 does not seem to be easily applicable to the colorful version of the problem. Indeed, the colored version of Lemma 6 fails: removing a clique from a σ-I h -free chordal graph does not necessarily yield a σ-I h-1 -free chordal graph, and the inductive argument does not apply.

Note that, as for any graph H and any instance (G, σ) of Colorful H-IS-Deletion, any edge between two vertices u, v with σ(u) = σ(v) can be safely deleted without affecting the instance, the Colorful K 2 -IS-Deletion problem is equivalent to computing a minimum vertex cover in a bipartite graph, which can be done in polynomial time. Similarly, the Colorful I 2 -IS-Deletion problem can also be solved in polynomial time, by computing a minimum vertex cover in the bipartite complement of the input graph. This is in sharp contrast to the uncolored version, where both problems are NP-hard [START_REF] Lewis | The Node-Deletion Problem for Hereditary Properties is NP-Complete[END_REF].