ABSTRACT: 2,3,5-Trisubstituted tetrahydrofurans were prepared stereoselectively through a two-step process, involving the addition of an acyl radical to a -silyloxy acrylic ester, followed by an acid-catalyzed desilylationketalization sequence and a final oxocarbenium reduction step. High levels of 1,2-and 1,3-stereocontrol were attained using (Me3Si)3SiH as a radical then ionic hydrogen transfer agent.

The tetrahydrofuran (THF) skeleton is ubiquitous in nature and is found in many classes of natural products, as illustrated below with complex marine macrocycles gymnodimine 1 1 and chagosensine 2 2 (Figure 1). The broad array of biological activities associated with the widespread occurrence of these compounds have generated considerable interest. However, despite the development of a large number of methods to access these heterocycles, 3 some limitations have appeared, such as the unsatisfactory control of the stereochemistry in certain cases or the narrow scope of some synthetic routes. Therefore, the development of new strategies to assemble such small rings in a straightforward and stereocontrolled fashion still remains an active field of research. In the course of a program on the total synthesis of gymnodimine 1, a straightforward access to a 2,3,5-trisubstituted tetrahydrofuran was required. It was envisioned that such THF could be formed starting from a phenyl selenoester and a -alkoxy substituted acrylic ester IV (Figure 2). The assembly of the THF skeleton would involve the successive formation of C4-C5 then C5-O bonds, respectively through: (1) a diastereocontrolled addition of a nucleophilic acyl radical III onto the acrylic ester IV, followed by (2), a reductive cyclization after in situ deprotection of the silyl ether. Both reactions would be mediated by an hydride transfer agent (R3SnH or R3SiH), setting up the stereochemistry at the C3 and C5 positions. Such a strategic disconnection of THF, relying on a dual reactivity of the acyl precursor has, to our knowledge, not been described to date. Noteworthy, the use of the same hydride in both steps would potentially allow the whole sequence to be carried out in one-pot. This approach, however, raised several issues concerning the level of diastereocontrol during the reduction of the -silyloxy-ester radical I and that of the oxocarbenium intermediate II. Diastereocontrolled additions of alkyl radicals to Baylis-Hillman adducts, first reported by 4 were shown to provide the corresponding esters with high diastereocontrol when using sterically hindered alkyl groups (I, R=t-Bu), and much lower selectivity with primary alkyl groups (I, R=n-C8H17). 4b Moreover, in spite of the wealth of data in the field, 4,[START_REF] For Reviews ; Curran | Stereochemistry of Radical Reactions[END_REF][START_REF] Guérin | Radicals in Organic Synthesis[END_REF] there was no report on the diastereocontrol arising from the conjugate addition of a rather small acyl radical III onto an -substituted acrylate ester. An even more critical issue was raised by the stereochemical outcome of the ionic hydride transfer to oxonium II. Models relying on stereoelectronic and steric effects have been proposed by Reissig et al. 7 then Woerpel et al. 8 to rationalize stereocontrol in nucleophilic additions onto 5-membered ring oxocarbeniums. However, in our case, R 2 and CO2R 4 substituents, trans to each other, might induce opposite stereochemistry at C5 during hydride transfer to II, the stereochemical outcome of the process thus remaining uncertain. We report here that the acyl radical addition to -silyloxy acrylic esters, followed by the reduction of the oxocarbenium ion, may be mediated, in both steps, by (Me3Si)3SiH (TTMSH) acting as a radical then ionic hydride transfer agent. 9 This offers an entry to a series of 2,3,5-trisubstituted tetrahydrofurans in one or two-pot processes in good yield and high level of 1,2-and 1,3-diastereocontrol. a Isolated yields. b Estimated through 1 H NMR of the crude reaction mixture. c The product was obtained as a mixture of diastereoisomeric hydroxyketone and hemiacetal. d UV initiation using a sunlight lamp (300 W). e Chlorobenzene was used instead of benzene. f t-BuON=NOt-Bu (DTBHN) was used instead of AIBN.

The acyl radical was generated from phenyl selenoesters, 10 using Bu3SnH as a reducing agent and AIBN as an initiator. Under these conditions, addition of 3a onto the unprotected acrylic ester 4a led to the desired product 5a in good yield but no stereocontrol, as a mixture of free hydroxyketone and lactol (Table 1, entry 1). Protection of the alcohol as an acetate provided 5b in excellent yield albeit with low sterecocontrol (Table 1, entry 2). Increasing stereocontrol was observed with 4c having a t-BuMe2Si substituent (Table 1, entry 3), by lowering the temperature (Table 1, entry 4), and in 4e with sterically more hindered t-BuPh2Si substituent 5d (Table 1, entries 6-7). Surprisingly, the TIPS substituent in 4d led to disappointing result (Table 1, entry 5). 5h Finally, the best results were observed using (Me3Si)3SiH instead of Bu3SnH (Table 1, entries 8-9), which led to 5e in 87% yield and up to >19:1 diastereoselectivity, showing that an increase of the steric hindrance of the hydride donor was able to secure the level of stereocontrol, whatever the size of the R group in radical I (Figure 2). The syn stereochemistry of 5a-e (assigned based on X-ray diffraction studies on a crystalline analogue, i.e. 6h, vide infra) may be rationalized invoking a staggered transition state model, in which the bulky silane approaches anti relative to the large silyloxy group, the small hydrogen nearly eclipsing the ester group (Figure 3). This early transition state resembles ground state conformation of the radical intermediate I where A1,3-strain is minimized. 4,5c-d As reported by Giese, stereocontrol increases with the size of the silyl protecting group. [START_REF]The absence of selectivity with very bulky TIPS group cannot be rationalized by TS in Figure 3, and remains unexplained[END_REF] The crucial role of TTMSH is noteworthy as this reagent is well known to increase stereoselectivity in radical hydride transfers in cyclic systems, 12 but more rarely in acyclic ones. These reaction conditions were then extended to a series of phenyl selenoesters 3a-c and -silyloxyacrylic esters 4e-j (Scheme 1). Two sets of reaction conditions (A and B) were studied in order to establish the comparative efficiency of Bu3SnH and TTMSH (Scheme 1). Reactions with the silane were carried out at a higher temperature but led consistently to higher yields and stereocontrol. The benzoyl radical led to slightly lower yields and stereocontrol as compared to other acyl precursors (see for instance 6b, 6g and 6j). [START_REF] Chatgilialoglu | Competing reduction of benzoyl radical with TTMSH might explain such low yields[END_REF] The nature of the -alkyl or aryl chain did not influence the selectivity to a large extent. Adding a bulky TIPS group on the alkynyl chain as in 6l however slightly lowered the diastereocontrol as compared to the unprotected alkyne 6m. It is worth of note that the reaction could also be performed on a larger scale. For instance, esters 6c and 6m were prepared in up to 4.5 mmol in 79 and 83% yield respectively. Finally, diffraction studies performed on crystalline 6h allowed us to assign the syn-relative configuration for compounds 5a-e and 6a-m.

With ketoesters 6 in hand, the one-pot silyl group deprotection, hemiacetal formation and oxocarbenium ion reduction was then studied, using 6c as a model substrate (Table 2). The combination between a Lewis acid and a reducing agent was anticipated to trigger the desilylation, then the cyclization into an hemiacetal and the subsequent formation of the oxocarbenium intermediate. Several Lewis acids were thus tested as well as silanes. A catalytic amount of BiBr3 15a was first shown to efficiently mediate both processes but reduction with Et3SiH led to poor diastereofacial differentiation (Table 2, entry 1). Increasing the steric hindrance around silicon using iPr3SiH was found to be detrimental to the reaction (Table 2,entry 2). Stoechiometric amount of TMSOTf with Et3SiH showed little efficiency (Table 2, entry 3). A good yield, albeit low stereocontrol was observed when using 2 equivalents of BF3.OEt2 associated to Et3SiH. 7,15b More satisfyingly, a high level of diastereocontrol was attained again using TTMSH as an hydride transfer agent, affording the desired THF 7 with up to 16:1 d.r. at room temperature (Table 2, entry 5). These conditions were then extended to ketoesters 5e and 6a-m described above (Scheme 2). The cascade reaction proceeded in generally high yields and level of diastereocontrol ranging between 7:1 to > 19:1. An exception was however observed with THF 7m and 7n, which led to poor diastereocontrol, likely as a result of the lesser steric hindrance of the linear alkynyl substituent at C2. In 7j-l, deprotection of the TIPS group on the C2 chain was also observed. The reductive cyclization was shown to be even more efficient in large scale, as experiments performed with 6c (3.4 mmol) and 6d (3.2 mmol), afforded the corresponding THF 7a and 7d respectively in 93% and 92% yield. The 2,3,5-trans,trans relative configuration of tetrahydrofurans 7a-n was assigned, based on the X-ray diffraction studies of a crystalline derivative (i.e. 10, vide infra). Scheme 2. TTMSH-mediated reductive cyclization of ketoesters 6.

TTMSH is a choice reagent for radical reductive processes, 9,13 but to our knowledge its use has not been reported for the reduction of oxocarbeniums ions, where cheaper Et3SiH generally affords satisfying results. The high level of stereocontrol observed with TTMSH may be rationalized invoking a transition state model such as A (Figure 4), in which the oxocarbenium ion adopts an envelope conformation with the polar substituent at C3 in a pseudoaxial position, as recently reported by Woerpel for closely related 5-membered-ring oxocarbenium ions bearing an alkoxy group at C3. 8a The nucleophile would thus approach from inside the envelope to provide the 2,5-cis THF. The importance of the proximity of a partially negatively charged substituent in a pseudoaxial position at C3, close to the cationic C5 center (electrostatic effects), has been clearly established in these systems with alkoxy groups, but not with esters. 8a However, recent studies on glycosylation of mannuronate esters suggest that an ester group may also be an efficient stereodirecting group. 16 TS model A may finally provide an explanation for the low diastereocontrol observed with compounds 7m-n, as linear alkynyl groups (R 2 ) at C2 should also allow the approach of the silane from outside the envelope. The whole sequence was also performed in one pot, as shown with the conversion of 4f into 7a occurring with a high stereocontrol and satisfying overall yield, demonstrating that such trisubstituted tetrahydrofurans may be generated from simple Baylis-Hillman adduct in a single step and selective manner (Scheme 3). Further manipulations of these THFs are also allowed. The ester function of 7a was also transformed into a methyl, in 34% overall yield and 5 steps from 4f, to produce the corresponding THF 9 having substituent and stereochemistry present in gymnodimine 1. Finally, X-ray diffraction studies on benzoate 10 secured the relative configuration of the tetrahydrofuran series 7a-n. Scheme 3. One-pot synthesis and further elaboration of 7a.

In summary, we reported straightforward access to 2,3,5-substituted tetrahydrofurans using radical then ionic (Me3Si)3SiH mediated hydrogen transfers. High levels of 1,2-and 1,3-stereocontrol were achieved, relying in both cases on the steric hindrance of the above silane. Application of this methodology to the construction of the gymnodimine THF framework is currently underway in our laboratory and will be reported in due course.

  Valérie Desvergnes, and Yannick Landais* University of Bordeaux, Institute of Molecular Sciences, UMR-CNRS 5255, 351 cours de la libération, 33405 Talence, France.

Figure 1 .

 1 Figure 1. Tetrahydrofuran fragments in marine natural products.

Figure 2 .

 2 Figure 2. Strategic disconnections to 2,3,5-trisubstituted tetrahydrofurans.

13

 13

Figure 3 .

 3 Figure 3. Transition state model for acyl addition to acrylates. Scheme 1. TTMSH-mediated addition of acyl radicals to -silyloxyacrylic esters.

Figure 4 .

 4 Figure 4. Transition state models for the TTMSH-reduction of oxocarbeniums.

Table 1 .

 1 Optimization of the acyl radical addition to -silyloxy acrylates 4a-e.

	entry	ester	M-H	temp (°C)	5, yield a (%)	dr b
	1	4a	Bu3SnH	90	70	n.d. c
	2	4b	Bu3SnH	90	90	2.4:1
	3	4c	Bu3SnH	90	90	3.5:1
	4 d	4c	Bu3SnH	0	81	4.4:1
	5 d	4d	Bu3SnH	0	62	1:1
	6 d	4e	Bu3SnH	0	75	6.5:1
	7 d,e	4e	Bu3SnH	-20	65	8:1
	8	4e	TTMSH	90	91	5:1
	9 f	4e	TTMSH	45	87	>19:1

Table 2 .

 2 Optimization of the tandem cyclization-reduction of -silyloxy ester 6c.

	entry	Lewis acid (equiv.)	MH (4 equiv)	temp (°C)	7, yield a (%)	dr b
	1	BiBr3 (0.1)	Et3SiH	25	87	1.8:1
	2	BiBr3 (0.1)	iPr3SiH	25	0	-
	3 c	TMSOTf (1)	Et3SiH	-78	29	1.4:1
	4	BF3.Et2O (2)	Et3SiH	-40	78	2.4:1
	5	BF3.Et2O (2)	TTMSH	25	87	16:1

a Isolated yields.

b

Estimated through 1 H NMR of the crude reaction mixture. c CH2Cl2 instead of MeCN.


domain: math info

text:
Rodrigues Sancrey
email: sancrey@cos.ufrj.br

Alves

Konrad K Dabrowski
email: konrad.dabrowski@durham.ac.uk

Luerbio Faria
email: luerbio@cos.ufrj.br

Sulamita Klein

Ignasi Sau
email: ignasi.sau@lirmm.fr

Uéverton S Souza
email: ueverton@ic.uff.br

On the (Parameterized) Complexity of Recognizing Well-covered (r, )-graphs

Keywords: well-covered graph, (r, )-graph, coNP-completeness, FPT-algorithm, parameterized complexity, coW[2]-hardness

An (r, )-partition of a graph G is a partition of its vertex set into r independent sets and cliques. A graph is (r, ) if it admits an (r, )-partition. A graph is well-covered if every maximal independent set is also maximum. A graph is (r, )-well-covered if it is both (r, ) and well-covered. In this paper we consider two different decision problems. In the (r, )-Well-Covered Graph problem ((r, )wc-g for short), we are given a graph G, and the question is whether G is an (r, )-well-covered graph. In the Well-Covered (r, )-Graph problem (wc-(r, )g for short), we are given an (r, )-graph G together with an (r, )partition, and the question is whether G is well-covered. This generates two infinite families of problems, for any fixed non-negative integers r and , which we classify as being P, coNP-complete, NP-complete, NP-hard, or coNP-hard. Only the cases wc-(r, 0)g for r ≥ 3 remain open. In addition, we consider the parameterized complexity of these problems for several choices of parameters, such as the size α of a maximum independent set of the input graph, its neighborhood diversity, its clique-width, or the number of cliques in an (r, )-partition. In particular, we show that the parameterized problem of determining whether every maximal independent set of an input graph G has cardinality equal to k can be reduced to the wc-(0, )g problem parameterized by . In addition, we prove that both problems are coW[2]-hard but can be solved in XP-time.

Introduction

One of the most important combinatorial problems is Maximum Independent Set (MIS), where the objective is to find a maximum sized subset S ⊆ V of pairwise non-adjacent vertices in a graph G = (V, E). Maximum independent sets appear naturally in a wide range of situations, and MIS also finds a number of "real world" relevant applications.

Unfortunately, the decision version of MIS is an NP-complete problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF], and thus it cannot be solved in polynomial time unless P = NP. In spite of the fact that finding a maximum independent set is a computationally hard problem, a maximal independent set of a graph can easily be found in linear time. Indeed, a naive greedy algorithm for finding maximal independent sets consists simply of selecting an arbitrary vertex v to add to a set S, and updating the current graph by removing the closed neighborhood N [v] of v. This algorithm always outputs a maximal independent set in linear time, but clearly not all choices lead to a maximum independent set.

Well-covered graphs were first introduced by Plummer [START_REF] Plummer | Some covering concepts in graphs[END_REF] in 1970. Plummer defined that "a graph is said to be well-covered if every minimal point cover is also a minimum cover". This is equivalent to demanding that all maximal independent set have the same cardinality. Therefore, well-covered graphs can be equivalently defined as the class of graphs for which the naive greedy algorithm discussed above always outputs a maximum independent set.

The problem of recognizing a well-covered graph, which we denote by Well-Covered Graph, was proved to be coNP-complete by Chvátal and Slater [4] and independently by Sankaranarayana and Stewart [START_REF] Sankaranarayana | Complexity results for wellcovered graphs[END_REF]. On the other hand, the Well-Covered Graph problem is in P when the input is known to be a perfect graph of bounded clique size [START_REF] Dean | Well-covered graphs and extendability[END_REF] or a claw-free graph [START_REF] Lesk | Equi-matchable graphs[END_REF][START_REF] Tankus | Well-covered claw-free graphs[END_REF].

Let r, ≥ 0 be two fixed integers. An (r, )-partition of a graph G = (V, E) is a partition of V into r independent sets S 1 , . . . , S r and cliques K 1 , . . . , K . For convenience, we allow these sets to be empty. A graph is (r, ) if it admits an (r, )-partition. Note that the notion of (r, )-graphs is a generalization of that of r-colorable graphs.

A P versus NP-complete dichotomy for recognizing (r, )-graphs was proved by Brandstädt [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF]: the problem is in P if max{r, } ≤ 2, and NP-complete otherwise. The class of (r, )-graphs and its subclasses have been extensively studied in the literature. For instance, list partitions of (r, )-graphs were studied by Feder et al. [START_REF] Feder | List partitions[END_REF]. In another paper, Feder et al. [19] proved that recognizing graphs that are both chordal and (r, ) is in P.

A graph is (r, )-well-covered if it is both (r, ) and well-covered. In this paper we analyze the complexity of the (r, )-Well-Covered Graph problem, which consists of deciding whether a graph is (r, )-well-covered. In particular, we give a complete classification of the complexity of this problem.

Additionally, we analyze the complexity of the Well-Covered-(r, )-Graph problem, which consists of deciding, given an (r, )-graph G = (V, E) together with an (r, ) partition, whether G is well-covered or not. We classify the complexity of this problem for every pair (r, ), except for the cases when = 0 and r ≥ 3, which we leave open.

We note that similar restrictions have been considered in the literature. For instance, Kolay et al. [START_REF] Kolay | Parameterized algorithms on perfect graphs for deletion to (r, )-graphs[END_REF] recently considered the problem of removing a small number of vertices from a perfect graph so that it additionally becomes (r, ).

To the best of our knowledge, this is the first time in the literature that a decision problem obtained by "intersecting" two recognition NP-complete and coNP-complete properties has been studied. From our results, the (r, )wc-g problem has a very peculiar property, namely that some cases of the problem are in NP, but other cases are in coNP. And if P = NP, there are some cases where the decision problem is neither in NP nor in coNP.

In addition, according to the state of the art for the Well-Covered Graph problem, to the best of our knowledge this is the first work that associates the hardness of Well-Covered Graph with the number of independent sets and the number of cliques of an (r, )-partition of the input graph. This shows an important structural property for classifying the complexity of subclasses of well-covered graphs.

As a by-product of this paper, an infinite class of decision problems was classified as being both NP-hard and coNP-hard. Hence, unless P = NP these decision problems are neither in NP nor in coNP.

More formally, in this paper we focus on the following two decision problems.

(r, )-Well-Covered Graph ((r, ) wc-g ) Input: A graph G. Question: Is G (r, )-well-covered?

Well-Covered (r, )-Graph ( wc-(r, )g )

Input: An (r, )-graph G, together with a partition of V (G) into r independent sets and cliques. Question: Is G well-covered?

We establish an almost complete characterization of the complexity of the (r, )wc-g and wc-(r, )g problems. Our results are shown in the following tables, where r (resp. ) corresponds to the rows (resp. columns) of the tables, and where coNPc stands for coNP-complete, NPh stands for NP-hard, NPc stands for NP-complete, and (co)NPh stands for both NP-hard and coNP-hard. We note the following simple facts, which we will use to fill the above tables:

Fact 1. If (r, )wc-g is in P, then wc-(r, )g is in P. Fact 2. If wc-(r, )g is coNP-hard, then (r, )wc-g is coNP-hard.
Note that wc-(r, )g is in coNP, since a certificate for a NO-instance consists just of two maximal independent sets of different size. On the other hand, for (r, )wc-g we have the following facts, which are easy to verify: Fact 3. For any pair of integers (r, ) such that the problem of recognizing an (r, )-graph is in P, the (r, )wc-g problem is in coNP. Fact 4. For any pair of integers (r, ) such that the wc-(r, )g problem is in P, the (r, )wc-g problem is in NP.

In this paper we prove that (r, )wc-g with (r, ) ∈ {(0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (1, 2)} can be solved in polynomial time, which by Fact 1 yields that wc-(r, )g with (r, ) ∈ {(0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (1, 2)} can also be solved in polynomial time. On the other hand, we prove that wc-(2, 1)g is coNPcomplete, which by Fact 2 and Fact 3 yields that (2, 1)wc-g is also coNPcomplete. Furthermore, we also prove that wc-(0, )g and wc-(1, )g are in P, and that (r, )wc-g with (r, ) ∈ {(0, 3), (3, 0), (1, 3)} are NP-hard. Finally, we state and prove a "monotonicity" result, namely Theorem 1, stating how to extend the NP-hardness or coNP-hardness of wc-(r, )g (resp. (r, )wc-g) to wc-(r + 1, )g (resp. (r + 1, )wc-g), and wc-(r, + 1)g (resp. (r, + 1)wc-g). Together, these results correspond to those shown in the above tables.

In addition, we consider the parameterized complexity of these problems for several choices of the parameters, such as the size α of a maximum independent set of the input graph, its neighborhood diversity, its clique-width or the number of cliques in an (r, )-partition. We obtain several positive and negative results. In particular, we show that the parameterized problem of determining whether every maximal independent set of an input graph G has cardinality equal to k can be reduced to the wc-(0, )g problem parameterized by . In addition, we prove that both problems are coW [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF]-hard, but can be solved in XP-time.

The rest of this paper is organized as follows. We start in Section 2 with some basic preliminaries about graphs, parameterized complexity, and width parameters. In Section 3 we prove our results concerning the classical complexity of both problems, and in Section 4 we focus on their parameterized complexity. We conclude the paper with Section 5.

Preliminaries

Graphs. We use standard graph-theoretic notation, and we refer the reader to [START_REF] Diestel | Graph Theory[END_REF] for any undefined notation. A graph G = (V, E) consists of a finite non-empty set V of vertices and a set E of unordered pairs (edges) of distinct elements of V . If uv ∈ E(G), then u, v are said to be adjacent, and u is said to be a neighbor of v. A clique (resp. independent set) is a set of pairwise adjacent (resp. non-adjacent) vertices. A vertex cover is a set of vertices containing at least one endpoint of every edge in the graph. The open neighborhood N (v) or neighborhood, for short, of a vertex v ∈ V is the set of vertices adjacent to v. The closed neighborhood of a vertex v is defined as

N [v] = N (v) ∪ {v}. A dominating set is a set of vertices S ⊆ V such that v∈S N [v] = V . Given S ⊆ V and v ∈ V , the neighborhood N S (v) of v in S is the set N S (v) = N (v) ∩ S.
Throughout the paper, we let n denote the number of vertices in the input graph for the problem under consideration.

Parameterized complexity. We refer the reader to [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF] for basic background on parameterized complexity, and we recall here only some basic definitions. A parameterized problem is a language L ⊆ Σ * × N. For an instance I = (x, k) ∈ Σ * × N, k is called the parameter. A parameterized problem is fixed-parameter tractable (FPT) if there exists an algorithm A, a computable function f , and a constant c such that given an instance I = (x, k), A (called an FPT-algorithm) correctly decides whether I ∈ L in time bounded by f (k)|I| c .

Within parameterized problems, the class W[1] may be seen as the parameterized equivalent to the class NP of classical optimization problems. Without entering into details (see [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF] for the formal definitions), a parameterized problem being W[1]-hard can be seen as a strong evidence that this problem is not FPT. The canonical example of a W[1]-hard problem is Independent Set parameterized by the size of the solution 2 .

The class W [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF] of parameterized problems is a class that contains W [START_REF] Alves | On the (parameterized) complexity of recognizing well-covered (r, )-graphs[END_REF], and so the problems that are W [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF]-hard are even more unlikely to be FPT than those that are W[1]-hard (again, see [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF] for the formal definitions). The canonical example of a W[2]-hard problem is Dominating Set parameterized by the size of the solution3 .

For i ∈ [1, 2], to transfer W[i]-hardness from one problem to another, one uses an fpt-reduction, which given an input I = (x, k) of the source problem, computes in time f (k)|I| c , for some computable function f and a constant c, an equivalent instance I = (x , k ) of the target problem, such that k is bounded by a function depending only on k.

Hence, an equivalent definition of W[1]-hard (resp. W[2]-hard) problem is any problem that admits an fpt-reduction from Independent Set (resp. Dominating Set) parameterized by the size of the solution.

Even if a parameterized problem is

W[1]-hard or W[2]
-hard, it may still be solvable in polynomial time for fixed values of the parameter; such problems are said to belong to the complexity class XP. Formally, a parameterized problem whose instances consist of a pair (x, k) is in XP if it can be solved by an algorithm with running time f (k)|x| g (k) , where f, g are computable functions depending only on the parameter and |x| represents the input size. For example, Independent Set and Dominating Set parameterized by the solution size are easily seen to belong to XP.

Width parameters. A tree-decomposition of a graph G = (V, E) is a pair (T, X ), where T = (I, F ) is a tree, and X = {B i }, i ∈ I is a family of subsets of V (G), called bags and indexed by the nodes of T , such that 1. each vertex v ∈ V appears in at least one bag, i.e., i∈I B i = V ; 2. for each edge e = {x, y} ∈ E, there is an i ∈ I such that x, y ∈ B i ; and

3. for each v ∈ V the set of nodes indexed by {i | i ∈ I, v ∈ B i } forms a subtree of T .
The width of a tree-decomposition is defined as max i∈I {|B i | -1}. The treewidth of G, denoted by tw(G), is the minimum width of a tree-decomposition of G.

The clique-width of a graph G, denoted by cw(G), is defined as the minimum number of labels needed to construct G, using the following four operations:

1. Create a single vertex v with an integer label (denoted by (v)); 2. Take the disjoint union (i.e., co-join) of two graphs (denoted by ⊕); 3. Join by an edge every vertex labeled i to every vertex labeled j for i = j (denoted by η(i, j));

4. Relabel all vertices with label i by label j (denoted by ρ(i, j)).

An algebraic term that represents such a construction of G and uses at most k labels is said to be a k-expression of G (i.e., the clique-width of G is the minimum k for which G has a k-expression).

Graph classes with bounded clique-width include cographs [START_REF] Brandstädt | New graph classes of bounded clique-width[END_REF], distancehereditary graphs [START_REF] Golumbic | On the clique-width of some perfect graph classes[END_REF], graphs of bounded treewidth [START_REF] Courcelle | Upper bounds to the clique width of graphs[END_REF], graphs of bounded branchwidth [START_REF] Robertson | Graph minors. X. obstructions to treedecomposition[END_REF], and graphs of bounded rank-width [START_REF] Kamiński | Recent developments on graphs of bounded clique-width[END_REF].

Classical Complexity of the Problems

We start with a monotonicity theorem that will be very helpful to fill the tables presented in Section 1. The remainder of this section is divided into four subsections according to whether (r, )wc-g and wc-(r, )g are polynomial or "hard" problems.

Theorem 1. Let r, ≥ 0 be two fixed integers. Then it holds that:

(i) if wc-(r, )g is coNP-complete then wc-(r + 1, )g and wc-(r, + 1)g are coNP-complete; (ii) if (r, )wc-g is NP-hard (resp. coNP-hard) then (r, + 1)wc-g is NP-hard (resp. coNP-hard); (iii) supposing that r ≥ 1, if (r, )wc-g is NP-hard (resp. coNP-hard) then (r + 1, )wc-g is NP-hard (resp. coNP-hard).
Proof. (i) This follows immediately from the fact that every (r, )-graph is also an (r + 1, )-graph and an (r, + 1)-graph.

(ii) Let G be an instance of (r, )wc-g. Let H be an (r, +1)wc-g instance defined as the disjoint union of G and a clique Z with V (Z) = {z 1 , . . . , z r+1 }. Clearly G is well-covered if and only if H is well-covered. If G is an (r, )well-covered graph then H is an (r, + 1)-well-covered graph. Suppose H is an (r, + 1)-well-covered graph, with a partition into r independent sets S 1 , . . . , S r and + 1 cliques K 1 , . . . , K +1 . Each independent set S i can contain at most one vertex of the clique Z. Therefore, there must be a vertex z i in some clique K j . Assume without loss of generality that there is a vertex of Z in K +1 . Then K +1 cannot contain any vertex outside of V (Z), so we may assume that K +1 contains all vertices of Z. Now S 1 , . . . , S r , K 1 , . . . , K is an (r, )partition of G, so G is an (r, )-well-covered graph. Hence, H is a YES-instance of (r, + 1)wc-g if and only if G is a YES-instance of (r, )wc-g.

(iii) Let G be an instance of (r, )wc-g. Let G be an (r + 1, )wc-g instance obtained from G by adding + 1 isolated vertices. (This guarantees that every maximal independent set in G contains at least + 1 vertices.) Since r ≥ 1, it follows that G is an (r, )-graph if and only if G is. Clearly G is well-covered if and only if G is.

Next, find an arbitrary maximal independent set in G and let p be the number of vertices in this set. Note that p ≥ + 1. Let H be the join of G and a set of p independent vertices Z = {z 1 , . . . , z p }, i.e., N H (z i ) = V (G ) for all i. Every maximal independent set of H is either Z or a maximal independent set of G and every maximal independent set of G is a maximal independent set of H. Therefore, H is well-covered if and only if G is well-covered. Clearly, if G is an (r, )-graph then H is an (r + 1, )-graph. Suppose H is an (r + 1, )graph, with a partition into r + 1 independent sets S 1 , . . . , S r+1 and cliques K 1 , . . . , K . Each clique set K i can contain at most one vertex of Z. Therefore there must be a vertex z i in some independent set S j . Suppose that there is a vertex of Z in S r+1 . Then S r+1 cannot contain any vertex outside of Z.

Without loss of generality, we may assume that S r+1 contains all vertices of Z. Now S 1 , . . . , S r , K 1 , . . . , K is an (r, )-partition of G, so G is an (r, )-graph. Thus H is a YES-instance of (r + 1, )wc-g if and only if G is a YES-instance of (r, )wc-g.

Proof. It is enough to prove that wc-(1, )g is in P. Let V = (S, K 1 , K 2 , K 3 , . . . , K ) be a (1, )-partition for G. Then each maximal independent set I of G admits a partition I = (I K , S \ N S (I K )), where I K is an independent set of K 1 ∪ K 2 ∪ K 3 ∪ • • • ∪ K .
Observe that there are at most O(n ) choices for an independent set

I K of K 1 ∪K 2 ∪K 3 ∪• • • ∪ K , which can be listed in time O(n ), since is constant and (K 1 , K 2 , K 3 , . . . , K ) is given.
For each of them, we consider the independent set

I = I K ∪ (S \ N S (I K )). If I is not maximal (which may happen if a vertex in (K 1 ∪ K 2 ∪ K 3 ∪ • • • ∪ K ) \ I K has
no neighbors in I), we discard this choice of I K . Hence, we have a polynomial number O(n ) of maximal independent sets to check in order to decide whether G is a well-covered graph.

Polynomial

Cases for (r, )wc-g Fact 5. The graph induced by a clique or by an independent set is well-covered.

The following corollary is a simple application of Fact 5.

Corollary 3. G is a (0, 1)-well-covered graph if and only if G is a (0, 1)-graph. Similarly, G is a (1, 0)-well-covered graph if and only if G is a (1, 0)-graph.

The following is an easy observation.

Lemma 4. (0, 2)wc-g can be solved in polynomial time.

Proof. By definition, a graph G = (V, E) is a (0, 2)-graph if and only if its vertex set can be partitioned into two cliques, and this can be tested in polynomial time. It follows that every (0, 2)-graph has maximum independent sets of size at most 2. Let G be a (0, 2)-graph with (0, 2)-partition (K 1 , K 2 ). If V is a clique, then G is a (0, 1)-well-covered graph, and hence a (0, 2)-well-covered graph. If V is not a clique, then G is a (0, 2)-well-covered graph if and only if G has no universal vertex.

In the next three lemmas we give a characterization of (1, 1)-well-covered graphs in terms of their graph degree sequence. Note that (1, 1)-graphs are better known in the literature as split graphs.

Lemma 5. Let G = (V, E) be a (1, 1)-well-covered graph with (1, 1)-partition V = (S, K), where S is a independent set and K is a clique.

If x ∈ K, then |N S (x)| ≤ 1.
Proof. Suppose that G is a (1, 1)-well-covered graph with (1, 1)-partition V = (S, K), where S is a independent set and K is a clique. Let I be a maximal independent set of G such that x ∈ I ∩ K. Suppose for contradiction that |N S (x)| ≥ 2, and let y, z ∈ N S (x). Since y, z ∈ S, N G (y), N G (z) ⊆ K. Since K is a clique, vertex x is the only vertex of I in K. Hence, we have that Let z be the vertex of S adjacent to y. Let I be a maximal independent set containing vertex y. Note that the vertex x is non-adjacent to every vertex of I \ {y} since there is at most one vertex of I in K. The same applies to the vertex z. Hence, a larger independent set I , with size |I | = |I| + 1, can be obtained from I by replacing vertex y with the non-adjacent vertices x, z, i.e., I is a maximal independent set of G that is not maximum, a contradiction. Thus, either for every x ∈ K, |N S (x)| = 0, or for every

N G (y) ∩ (I \ {x}) = N G (z) ∩ (I \ {x}) = ∅. Therefore I = (I \ {x}) ∪ {y, z} is an independent set of G such that |I | = |I| + 1. Thus, I is a maximal independent set that is not maximum, so G is not well-covered. Thus, |N S (x)| ≤ 1. Lemma 6. A graph G is a (1,
x ∈ K, |N S (x)| = 1.
Conversely, suppose that there is a (1, 1)-partition V = (S, K) of G such that either for every x ∈ K, |N S (x)| = 0, or for every Proof. Since we can check in polynomial time whether G is a (1, 1) graph [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF], and one can enumerate all (1, 1)-partitions of a split graph in polynomial time, we can solve the (1, 1)wg-g problem in polynomial time.

x ∈ K, |N S (x)| = 1. If K = ∅, then G is (1, 0)
The next lemma shows that (1, 1)-well-covered graphs can be recognized from their degree sequences. Lemma 8. G is a (1, 1)-well-covered graph if and only if there is a positive integer k such that G is a graph with a (1, 1)-partition V = (S, K) where |K| = k, such that the degree sequence of V is either (k, k, k, . . . , k, i 1 , i 2 , . . . , i s , 0, 0, 0, . . . , 0) with s j=1 (i j ) = k, or (k -1, k -1, k -1, . . . , k -1, 0, 0, 0, . . . , 0), where the subsequences k, . . . , k (resp. k -1, . . . , k -1) have length k.

Proof. Let G be a (1, 1)-well-covered graph. Then G admits a (1, 1)-partition V = (S, K) where k := |K|, k ≥ 0. If k = 0, then the degree sequence is (0, 0, 0, . . . , 0). If k ≥ 1, then by Lemma 6 either for every x ∈ K, |N S (x)| = 0, or for every x ∈ K, |N S (x)| = 1. If for every x ∈ K, |N S (x)| = 0, then the degree sequence of G is (k -1, k -1, k -1, . . . , k -1, 0, 0, 0, . . . , 0). If for every x ∈ K, |N S (x)| = 1, then the degree sequence of G is (k, k, k, . . . , k, i 1 , i 2 , . . . , i s , 0, 0, 0, . . . , 0), with s j=1 (i j ) = k. Suppose that there is a positive integer k such that G is a graph with (1, 1)partition V = (S, K) where |K| = k, with degree sequence either (k, k, k, . . . , k, i 1 , i 2 , . . . , i s , 0, 0, 0, . . . , 0), or (k -1, k -1, k -1, . . . , k -1, 0, 0, 0, . . . , 0), such that s j=1 (i j ) = k. If the degree sequence of G is (k, k, k, . . . , k, i 1 , i 2 , . . . , i s , 0, 0, 0, . . . , 0), then the vertices of K are adjacent to k -1 vertices of K and exactly one of S, since the vertices with degree i 1 , i 2 , . . . , i s , have degree at most k and the vertices with degree 0 are isolated. If the degree sequence of G is (k -1, k -1, k -1, . . . , k -1, 0, 0, 0, . . . , 0), then the vertices of K are adjacent to k -1 vertices of K and none of S and the vertices with degree 0 are isolated. By Lemma 6 we have that G is a well-covered graph.

Ravindra [START_REF] Ravindra | Well-covered graphs[END_REF] gave the following characterization of (2, 0)-well-covered graphs.

Proposition 9 (Ravindra [START_REF] Ravindra | Well-covered graphs[END_REF]). Let G be a connected graph. G is a (2, 0)-wellcovered graph if and only if G contains a perfect matching F such that for every edge e = uv in F , G[N (u) ∪ N (v)] is a complete bipartite graph.

We now prove that Proposition 9 leads to a polynomial-time algorithm. Lemma 10. (2, 0)wc-g can be solved in polynomial time.

Proof. Assume that G is connected and consider the weighted graph (G, ω)

with ω : E(G) → {0, 1} satisfying ω(uv) = 1, if G[N (u) ∪ N (v)
] is a complete bipartite graph, and 0 otherwise. By Proposition 9, G is well-covered if and only if (G, ω) has a weighted perfect matching with weight at least n/2, and this can be decided in polynomial time [START_REF] Edmonds | Paths, trees and flowers[END_REF].

Lemma 11. (1, 2)wc-g can be solved in polynomial time.

Proof. We can find a (1, 2)-partition of a graph G (if such a partition exists) in polynomial time [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF]. After that, we use the algorithm for wc-(1, )g given by Theorem 2.

Below we summarize the cases for which we have shown that wc-(r, )g or (r, )wc-g can be solved in polynomial time.

Theorem 12. (r, )wc-g with (r, ) ∈ {(0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0)} and wc-(r, )g with r ∈ {0, 1} or (r, ) = (2, 0) can be solved in polynomial time.

Proof. The first part follows from Corollary 3, Lemma 4, Corollary 7, Lemma 11, and Lemma 10, respectively. The second part follows from Theorem 2, and Lemma 10 together with Fact 1. v 3 [1] v 2 [1] v 5 [1] v 4 [1] v 6 [1] v 1 [1] v

1 [2] v 4 [2]
v 5 [2] v 2 [2] v 3 [2] v 6 [2] v 3 [1] v 2 [1] v 5 [1] v 4 [1] v 6 [1] v 1 [1] v 1 [2] v

4 [2] v 5 [2]
v 2 [2] v 3 [2] v 6 [2] N Proof. As by Theorem 2 the Well-Covered Graph problem can be solved in polynomial time on (0, 3)-graphs, by Fact 4 (0, 3)wc-g is in NP.

F T/F T/F T/F T/F T/F T/F t 1 t 2 u 1 u 1 u 2 u 2 u 3 u 3 N F T/F T/F T/F T/F T/F T/F t 1 t 2 u 1 u 1 u 2 u 2 u 3 u 3 (a) (b)
Let I = (U, C) be a 3-sat instance. We produce, in polynomial time in the size of I, a (0, 3)wc-g instance H, such that I is satisfiable if and only if H is (0, 3)-well-covered. Let G = (V, E) be the graph of [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF] obtained from I, and let G be the graph obtained from G by adding to V a vertex x uv for every edge uv of G not belonging to a triangle, and by adding to E edges ux uv and vx uv ; see Figure 2(b). Finally, we define H = G as the complement of G . Note that, by [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF], I is satisfiable if and only if G is 3-colorable. Since x uv is adjacent to only two different colors of G, clearly G is 3-colorable if and only if G is 3-colorable. Hence, I is satisfiable if and only if H is a (0, 3)-graph. We prove next that I is satisfiable if and only if H is a (0, 3)-well-covered graph.

Suppose that I is satisfiable. Then, since H is a (0, 3)-graph, every maximal independent set of H has size 3, 2, or 1. If there is a maximal independent set I in H with size 1 or 2, then I is a maximal clique of G of size 1 or 2. This contradicts the construction of G , since every maximal clique of G is a triangle. Therefore, G is well-covered.

Suppose that H is (0, 3)-well-covered. Then G is 3-colorable, so G is also 3-colorable. Thus, by [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF], I is satisfiable.

We next prove that (3, 0)wc-g is NP-hard. For this, we again use the proof of Stockmeyer [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF], together with the following theorem.

Proposition 16 (Topp and Volkmann [37]). Let G = (V, E) be an n-vertex graph, V = {v 1 , v 2 , v 3 , . . . , v n }, and let H be obtained from G such that V (H) = V ∪ {u 1 , u 2 , u 3 , . . . , u n } and E(H) = E ∪ {v i u i : i ∈ {1, 2, 3, . . . , n}}. Then H is a well-covered graph where every maximal independent set has size n.

Proof. Observe that every maximal independent set I of H has a subset I G = I ∩ V . Let U ⊆ {1, 2, 3, . . . , n} be the set of indices i such that v i ∈ I. Since I is maximal, the set {u i : i ∈ {1, 2, 3, . . . , n} \ U } must be contained in I, so |I| = n. Lemma 17. (3, 0)wc-g is NP-hard.

Proof. Let I = (U, C) be a 3-sat instance; let G = (V, E) be the graph obtained from I in Stockmeyer's [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF] NP-completeness proof for 3-coloring; and let H be the graph obtained from G by the transformation described in Proposition 16. We prove that I is satisfiable if and only if H is a (3, 0)-well-covered graph. Suppose that I is satisfiable. Then by [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF] we have that G is 3-colorable. Since a vertex v ∈ V (H) \ V (G) has just one neighbor, there are 2 colors left for v to extend a 3-coloring of G, and so H is a (3, 0)-graph. Hence, by Proposition 16, H is a (3, 0)-well-covered graph. Suppose that H is a (3, 0)-well-covered graph. Then we have that G is a (3, 0)-graph. By [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF], I is satisfiable.

Note that Theorem 1 combined with Lemma 15 does not imply that (1, 3)wcg is NP-complete.

Lemma 18. (1, 3)wc-g is NP-complete.
Proof. As by Theorem 2 the Well-Covered Graph problem can be solved in polynomial time on (1, 3)-graphs, by Fact 4 (1, 3)wc-g is in NP.

Let I = (U, C) be a 3-sat instance. Without loss of generality, I has more than two clauses. We produce a (1, 3)wc-g instance H polynomial in the size of I, such that I is satisfiable if and only if H is (1, 3)-well-covered.

Let G = (V, E) be the graph of Stockmeyer [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF] obtained from I (see Figure 2(a)), and let H be the graph obtained from G (the complement of the graph G) by adding one pendant vertex p v for each vertex v of G. Note that

V (H) = V (G) ∪ {p v : v ∈ V (G)}, E(H) = E(G) ∪ {p v v : v ∈ V (G)}, and N H (p v ) = {v}.
First suppose that I is satisfiable. Then by [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF], G is a (3, 0)-graph, and G is a (0, 3)-graph with partition into cliques

V (G) = (K 1 G , K 2 G , K 3 G ). Thus it follows that (S = {p v : v ∈ V (G)}, K 1 G , K 2 G , K 3 G ) is a (1,
3)-partition of V (H). In addition, from Proposition 16 and by the construction of H, H is a wellcovered graph. Hence H is (1, 3)-well-covered.

Conversely, suppose that H is (1, 3)-well-covered, and let

V (H) = (S, K 1 , K 2 , K 3 ) be a (1, 3)-partition for H. Then we claim that no vertex p v ∈ V (H) \ V (G) belongs to K i , i ∈ {1, 2, 3}. Indeed, suppose for contradiction that p v ∈ K i for some i ∈ {1, 2, 3}. Then, K i ⊆ {p v , v}. Hence, H \ K i is a (1, 2)-graph
and G \ {v} is an induced subgraph of a (2, 1)-graph. But by construction of G, G\{v} (for any v ∈ V (G)) contains at least one 2K 3 (that is, two vertex-disjoint copies of K 3 ) as an induced subgraph, which is a contradiction given that 2K 3 is clearly a forbidden subgraph for (2, 1)-graphs. Therefore,

{p v : v ∈ V (G)} ⊆ S, and since {p v : v ∈ V (G)} is a dominating set of H, S = {p v : v ∈ V (G)}.
Thus, G is a (0, 3)-graph with partition V (G) = (K 1 , K 2 , K 3 ), and therefore G is a (3, 0)-graph, i.e., a 3-colorable graph. Therefore, by [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF], I is satisfiable. Definition 1. The class coW [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF] is the class of all parameterized problems whose complement is in W [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF].

For an overview of parameterized complexity classes, see [START_REF] De Haan | Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF]. We are now ready to show the next result.

Theorem 22. The wc-(0, )g problem parameterized by is coW [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF]-hard.

Proof. Red-Blue Dominating Set (RBDS) is a well-known W[2]-complete problem [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF], which consists of determining whether a given bipartite graph G = (R ∪ B, E) admits a set D ⊆ R of size k (the parameter) such that D dominates B (that is, every vertex in B has a neighbor in D). To show the coW [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF]-hardness of our problem, we present an fpt-reduction from Red-Blue Dominating Set to the problem of determining whether a given (0, )-graph is not well-covered, where = k + 1.

From an instance (G, k) of RBDS we construct a (0, )-graph G as follows. Replace the set R = {r 1 , r 2 , . . . , r m } by k copies:

R 1 = {r 1 1 , r 1 2 , . . . , r 1 m }, R 2 = {r 2 1 , r 2 2 , . . . , r 2 m }, . . . , R k = {r k 1 , r k 2 , . . . , r k m },
where each new vertex has the same neighborhood as the corresponding vertex did in G. Add edges to make B, as well as each R i for 1 ≤ i ≤ k, induce a clique. For each i ∈ {1, . . . , k}, create a vertex s i , and add all possible edges between s i and the vertices in R i . Let G be the resulting graph. Note that the vertex set of G can be partitioned into

= k + 1 cliques: B, R 1 ∪ {s 1 }, R 2 ∪ {s 2 }, . . . , R k ∪ {s k }.
Clearly, for every b ∈ B, the set {s 1 , s 2 , . . . , s k }∪{b} is an independent set of G of size k + 1. Note that such an independent set is maximum, as it contains one vertex from each of the k + 1 cliques that partition V (G ). In addition, any maximal independent set of G has size at least k, since every maximal independent set contains either s i or a vertex of R i . At this point, we claim that G has a set D ⊆ R of size k which dominates B if and only if G has a maximal independent set of size k (i.e., G is not well-covered).

If

D = {r i1 , r i2 , . . . , r i k } is a subset of R of size k which dominates B in G, then D = {r 1 i1 , r 2 i2 , . . . , r k i k } is a maximal independent set of G , implying that G is not well-covered.
Conversely, if G is not well-covered then there exists in G a maximal independent set D of size k. Note that D ∩ B = ∅ and each vertex in B has at least one neighbor in D , as otherwise D would not be a maximal independent set of size k. Therefore, by letting D be the set of vertices in R that have copies in

D ∩ {R 1 ∪ R 2 ∪ . . . ∪ R k }, we find that D is a subset of R of size at most k which dominates B in G.
From the previous theorem we immediately obtain the following corollaries. Proof. This follows immediately from Lemma 21 and Theorem 22.

Corollary 24. Unless FPT = coW [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF], the wc-(r, )g problem cannot be solved in time f (α + )n g (r) for any computable function f . Proof. This follows from the fact that an algorithm running in time f (α+ )n g (r) , would be an FPT-algorithm for wc-(0, )g parameterized by , and from the coW [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF]-hardness of the problem demonstrated in Theorem 22.

In contrast to Corollary 24, Lemma 25 shows that the wc-(r, )g problem can be solved in time 2 rα n O( ) .

Lemma 25. The wc-(r, )g problem can be solved in time 2 rα n O( ) . In particular, it is FPT when is fixed and r, α are parameters.

Proof. Note that each of the r independent sets S 1 , . . . , S r of the given partition of V (G) must have size at most α. On the other hand, any maximal independent set of G contains at most one vertex in each of the cliques. The algorithm exhaustively constructs all maximal independent sets of G as follows: we start by guessing a subset of r i=1 S i , and then choose at most one vertex in each clique. For each choice, we just have to verify whether the constructed set is a maximal independent set, and then check that all the constructed maximal independent sets have the same size. The claimed running time follows. In fact, in the statement of the lemma, one could replace rα with 1≤i≤r |S i |, which yields a stronger result.

Although wc-(1, )g parameterized by is coW [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF]-hard (see Theorem 22), Theorem 2 shows that the problem is in XP.

Corollary 26. The wc-(1, )g problem can be solved in time n O( ) . In other words, it is in XP when parameterized by .

Proof. This follows from Theorem 2 by considering to not be a constant. Table 1 summarizes the results presented so far. Note that, by Ramsey's Theorem [START_REF] Ramsey | On a problem of formal logic[END_REF], when both ω and α are parameters the input graph itself is a trivial kernel.

Taking the Neighborhood Diversity as the Parameter

Neighborhood diversity is a structural parameter based on a special way of partitioning a graph into independent sets and cliques. Therefore, it seems a natural parameter to consider for our problem, since an (r, )-partition of a graph G is also a partition of its vertex set into cliques and independent sets. Definition 2 (Lampis [START_REF] Lampis | Algorithmic meta-theorems for restrictions of treewidth[END_REF]). The neighborhood diversity nd(G) of a graph G = (V, E) is the minimum integer t such that V can be partitioned into t sets V 1 , . . . , V t where for every v ∈ V (G) and every i ∈ {1, . . . , t}, either v is adjacent to every vertex in V i or it is adjacent to none of them. Note that each part V i of G is either a clique or an independent set.

Another natural parameter to consider is the vertex cover number, because well-covered graphs can be equivalently defined as graphs in which every minimal vertex cover has the same size. However, neighborhood diversity is stronger than vertex cover, in the sense that every class of graphs with bounded vertex cover number is also a class of graphs with bounded neighborhood diversity, but the reverse is not true [START_REF] Lampis | Algorithmic meta-theorems for restrictions of treewidth[END_REF]. Thus, for our analysis, it is enough to consider the neighborhood diversity as the parameter. In addition, neighborhood diversity is a graph parameter that captures more precisely than vertex cover number the property that two vertices with the same neighborhood are "equivalent".

) (r, ) r - - para-coNP-h coW[2]-h XP coW[2]-h XP para-coNP-h r, coW[2]-h XP coW[2]-h XP para-coNP-h r, , ω FPT Trivial FPT Trivial Open (generalizes wc-(3,0)g) r, , α coW[2]-h XP coW[2]-h XP coW[2]-h, no f (α + )n g( (1,
It is worth mentioning that an optimal neighborhood diversity decomposition of a graph G can be computed in time O(n 3 ); see [START_REF] Lampis | Algorithmic meta-theorems for restrictions of treewidth[END_REF] for more details.

Lemma 27. The Well-Covered Graph problem is FPT when parameterized by neighborhood diversity.

Proof. Given a graph G, we first obtain a neighborhood partition of G with minimum width using the polynomial-time algorithm of Lampis [START_REF] Lampis | Algorithmic meta-theorems for restrictions of treewidth[END_REF]. Let t := nd(G) and let V 1 , . . . , V t be the partition of V (G). As we can observe, for any pair u, v of non-adjacent vertices belonging to the same part V i , if u is in a maximal independent set S then v also belongs to S, otherwise S cannot be maximum. On the other hand, if N [u] = N [v] then for any maximal independent set S u such that u ∈ S u there exists another maximal independent set S v such that S v = S u \ {u} ∪ {v}. Hence, we can contract each partition V i that is an independent set into a single vertex v i with weight τ (v i ) = |S i |, and contract each partition V i that is a clique into a single vertex v i with weight τ (v i ) = 1, in order to obtain a graph G t with |V (G t )| = t, where the weight of a vertex v i of G t means that any maximal independent set of G uses either none or exactly τ (v) vertices of V i . At this point, we just need to analyze whether all maximal independent sets of G t have the same weight (sum of the weights of its vertices), which can be done in time 2 t n O (1) .

Corollary 28. The Well-Covered Graph problem is FPT when parameterized by the vertex cover number n -α.

Taking the Clique-width as the Parameter

In the 90's, Courcelle proved that for every graph property Π that can be formulated in monadic second order logic (MSOL 1 ), there is an f (k)n O (1) algorithm that decides if a graph G of clique-width at most k satisfies Π (see [5,6,[START_REF] Courcelle | Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach[END_REF][START_REF] Courcelle | Monadic second-order evaluations on treedecomposable graphs[END_REF]), provided that a k-expression is given.

LinEMSOL is an extension of MSOL 1 which allows searching for sets of vertices which are optimal with respect to some linear evaluation functions. Courcelle et al. [START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique-width[END_REF] showed that every graph problem definable in LinEMSOL is linear-time solvable on graphs with clique-width at most k (i.e., FPT when parameterized by clique-width) if a k-expression is given as input. Using a result of Oum [START_REF] Oum | Approximating rank-width and clique-width quickly[END_REF], the same result follows even if no k-expression is given.

Theorem 29. The Well-Covered Graph problem is FPT when parameterized by clique-width.

Proof. Given S ⊆ V (G), first observe that the property "S is a maximal independent set" is MSOL 1 -expressible. Indeed, we can construct a formula ϕ(G, S) such that "S is a maximal independent set" ⇔ ϕ(G, S) as follows: Proof. As r and are constants, the problem of determining whether G is an (r, )-graph is also MSOL 1 -expressible.

Note that, since for every graph G we have cw(G) ≤ nd(G)+1 [START_REF] Lampis | Algorithmic meta-theorems for restrictions of treewidth[END_REF], Lemma 27 is also a corollary of Theorem 29. Nevertheless, the algorithm derived from the proof of Lemma 27 is much simpler and faster than the one that follows from the meta-theorem of Courcelle et al. [START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique-width[END_REF].

Further Research

Concerning the complexity of the (r, )wc-g and wc-(r, )g problems, note that the only remaining open cases are wc-(r, 0)g for r ≥ 3 (see the tables in Section 1). We do not even know if there exists some integer r ≥ 3 such that wc-(r, 0)g is coNP-complete, although we conjecture that this is indeed the case.

As another avenue for further research, it would be interesting to provide a complete characterization of well-covered tripartite graphs, as has been done for bipartite graphs [START_REF] Favaron | Very well-covered graphs[END_REF][START_REF] Ravindra | Well-covered graphs[END_REF][START_REF] Villarreal | Unmixed bipartite graphs[END_REF]. So far, only partial characterizations exist [START_REF] Haghighi | A generalization of Villarreal's result for unmixed tripartite graphs[END_REF][START_REF] Zaare-Nahandi | Unmixed r-partite graphs[END_REF].

3. 1 .

 1 Polynomial Cases for wc-(r, )g Theorem 2. wc-(0, )g and wc-(1, )g are in P for every integer ≥ 0.

  1)-well-covered graph if and only if it admits a (1, 1)-partition V = (S, K) such that either for every x ∈ K, |N S (x)| = 0, or for every x ∈ K, |N S (x)| = 1. Proof. Let G be a (1, 1)-well-covered graph. By Lemma 5 we have that, given a vertex x ∈ K, either |N S (x)| = 0 or |N S (x)| = 1. Suppose for contradiction that there are two vertices x, y ∈ K such that |N S (x)| = 0 and |N S (y)| = 1.

  and then G is well-covered. Hence we assume K = ∅. If for every x ∈ K, |N S (x)| = 0, then every maximal independent set consists of all the vertices of S and exactly one vertex v ∈ K. If for every x ∈ K, |N S (x)| = 1, then every maximal independent set is either I = S, or I = {x} ∪ (S \ N S (x)) for some x ∈ K. Since |N S (x)| = 1 we have |I| = 1 + |S| -1 = |S|, and hence G is a (1, 1)-well-covered graph. Corollary 7. (1, 1)wc-g can be solved in polynomial time.

Figure 2 :

 2 Figure 2: (a) Stockmeyer's [35] 3-coloring instance G obtained from the 3-sat instance I = (U, C) = ({u 1 , u 2 , u 3 }, {(u 3 , u 2 , u 1 ), (u 1 , u 2 , u 3 )}). (b) The graph G obtained from G by adding a vertex xuv with N G (xuv) = {u, v} for every edge uv of G not belonging to a triangle.

Corollary 23 .

 23 The k-Well-Covered Graph problem is coW[START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF]-hard.

[

  u, v ∈ S : edge(u, v)] ∧ [ S : (S ⊆ S ) ∧ ( x, y ∈ S : edge(x, y))] Since ϕ(G, S) is an MSOL 1 -expression, the problem of finding goal(S) : ϕ(G, S) for goal ∈ {max, min} is definable in LinEMSOL. Thus we can find max(S) and min(S) satisfying ϕ(G, S) in time f (cw(G))n O(1) . Finally, G is well-covered if and only if | max(S)| = | min(S)|. Corollary 30. The Well-Covered Graph problem is FPT when parameterized by treewidth.Proof. This follows from the fact that graphs with treewidth bounded by k have clique-width bounded by a function of k[START_REF] Courcelle | Upper bounds to the clique width of graphs[END_REF].Corollary 31. For any fixed r and , the (r, )-Well-Covered Graph problem is FPT when parameterized by clique-width.

  The symbol '?' denotes that the complexity of the corresponding problem is open.

	(r, )wc-g	0	1	2	≥ 3
	0	-	P	P	NPc
	1	P	P	P	NPc
	2	P	coNPc	coNPc	(co)NPh
	≥ 3	NPh (co)NPh (co)NPh (co)NPh
	wc-(r, )g	0	1	2	≥ 3
	0	-	P	P	P
	1	P	P	P	P
	2	P	coNPc	coNPc	coNPc
	≥ 3	?	coNPc	coNPc	coNPc

Table 1 :

 1 Parameterized complexity of wc-(r, )g.

	Param.\Class	(0, )

Given a graph G and a parameter k, the problem is to decide whether there exists an independent set S ⊆ V (G) such that |S| ≥ k.

Given a graph G and a parameter k, the problem is to decide whether there exists a dominating set S ⊆ V (G) such that |S| ≤ k.

Acknowledgement. We would like to thank the anonymous reviewers for helpful remarks that improved the presentation of the manuscript.

This work was supported by FAPERJ, CNPq, CAPES Brazilian Research Agencies, EP-SRC (EP/K025090/1), the Leverhulme Trust (RPG-2016-258) and the DE-MO-GRAPH grant ANR-16-CE40-0028. An extended abstract of this paper appeared in the proceedings of CO-COA 2016 [1].

Chvátal and Slater's [4] Well-Covered Graph instance G = (V, E) obtained from the satisfiable 3-sat instance I = (U, C) = ({u 1 , u 2 , u 3 }, {(u 1 , u 2 , u 3 ), (u 1 , u 2 , u 3 ), (u 1 , u 2 , u 3 )}), where {c 1 , c 2 , . . . , cm} is a clique of G. Observe that I is satisfiable if and only if G is not well-covered, since there is a maximal independent set with size n + 1 (e.g. {c 1 , u 1 , u 2 , u 3 }) and there is a maximal independent set of size n (e.g. {u 1 , u 2 , u 3 }). Note also that G is a (2, 1)-graph with (2, 1)-partition V = ({u 1 , u 2 , . . . , un}, {u 1 , u 2 , . . . , un}, {c 1 , c 2 , . . . , cm} ).

coNP-complete Cases for wc-(r, )g

We note that the well-Covered Graph instance G constructed in the reduction of Chvátal and Slater [4] is a (2, 1)-graph, directly implying that wc-(2, 1)g is coNP-complete.

Indeed, Chvátal and Slater [4] take a 3-sat instance

Note that {c i c j : 1 ≤ i < j ≤ m} is a clique, and that {u 1 , u 2 , u 3 , . . . , u n }, and {u 1 , u 2 , u 3 , . . . , u n } are independent sets. Hence, G is a (2, 1)-graph. An illustration of this construction can be found in Figure 1. This discussion can be summarized as follows.

Proposition 13 (Chvátal and Slater [4]). wc-(2, 1)g is coNP-complete.

As (2, 1)-graphs can be recognized in polynomial time [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF], we obtain the following.

Corollary 14. (2, 1)wc-g is coNP-complete.

NP-hard Cases for (r, )wc-g

Now we prove that (0, 3)wc-g is NP-complete. For this purpose, we slightly modify an NP-completeness proof of Stockmeyer [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF].

Stockmeyer's [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF] NP-completeness proof of 3-coloring considers a 3-sat instance

j] : j ∈ {1, 2, 3, . . . , m}} ); see Figure 2(a).

Lemma 15. (0, 3)wc-g is NP-complete.

Parameterized Complexity of the Problems

In this section we focus on the parameterized complexity of the Well-Covered Graph problem, with special emphasis on the case where the input graph is an (r, )-graph. Recall that the results presented in Section 2 show that wc-(r, )g is para-coNP-complete when parameterized by r and . Thus, additional parameters should be considered. Henceforth we let α (resp. ω) denote the size of a maximum independent set (resp. maximum clique) in the input graph G for the problem under consideration. Note that wc-(r, )g parameterized by r, , and ω generalizes wc-(r, 0)g, whose complexity was left open in the previous sections. Therefore, we focus on the complexity of wc-(r, )g parameterized by r, , and α, and on the complexity of the natural parameterized version of Well-Covered Graph, defined as follows:

k-Well-Covered Graph

Input: A graph G and an integer k. Parameter: k.

Question: Does every maximal independent set of G have size exactly k?

The next lemma provides further motivation to study of the wc-(0, )g problem, as it shows that k-Well-Covered Graph (on general graphs) can be reduced to the wc-(0, )g problem parameterized by .

Lemma 21. The k-Well-Covered Graph problem can be fpt-reduced to the wc-(0, )g problem parameterized by .

Proof. Consider an arbitrary input graph G with vertices u 1 , . . . , u n . First, we find an arbitrary maximal (with respect to set-inclusion) independent set I in G. Without loss of generality we may assume that |I| = k and I = {u 1 , . . . , u k }.

We construct a (0, )-graph G with vertex set {v i,j : i ∈ {1, . . . , }, j ∈ {1, . . . , n}} as follows:

• For all i ∈ {1, . . . , } add edges to make V i := {v i,j : j ∈ {1, . . . , n}} into a clique.

• For all j ∈ {1, . . . , n} add edges to make W j := {v i,j : i ∈ {1, . . . , }} into a clique.

• For all pairs of adjacent vertices u a , u b in G, add edges between v i,a and v j,b for all i, j ∈ {1, . . . , } (so that V a is complete to V b ).

Note that the sets V i partition G into cliques, so G is indeed a (0, )-graph, where = k + 1.

The graph G has a maximal independent set of size k, namely {v 1,1 , . . . , v k,k }, so G is well-covered if and only if every maximal independent set in G has size exactly k. Every maximal independent set in G has at most one vertex in any set V i and at most one vertex in any set W j , since V i and W j are cliques. As there are = k + 1 sets V i , it follows that every independent set in G contains at most k + 1 vertices. If G contains an independent set {v i1,j1 , . . . , v ix,jx } for some x then {u j1 , . . . , u jx } is an independent set in G. If G contains an independent set {u j1 , . . . , u jx } for some x then {v 1,j1 , . . . , v min(x,k+1),j min(x,k+1) } is an independent set in G . Therefore G contains a maximal independent set smaller than k if and only if G contains a maximal independent set smaller than k and G contains a (not necessarily maximal) independent set of size at least k+1 if and only G contains a maximal independent set of size exactly k+1. It follows that G is well-covered if and only if G is. As = k + 1, this completes the proof.

Recall that the Well-Covered Graph problem is coNP-complete [4,[START_REF] Sankaranarayana | Complexity results for wellcovered graphs[END_REF]. In order to analyze the parameterized complexity of the problem, we will need the following definition.