11institutetext: Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon
1, LIP UMR5668, France
11email<EMAIL_ADDRESS>
# Beyond recognizing well-covered graphs

Carl Feghali  Malory Marin  Rémi Watrigant

###### Abstract

We prove a number of results related to the computational complexity of
recognizing well-covered graphs. Let $k$ and $s$ be positive integers and let
$G$ be a graph. Then $G$ is said

  * •

$\mathbf{W_{k}}$ if for any $k$ pairwise disjoint independent vertex sets
$A_{1},\dots,A_{k}$ in $G$, there exist $k$ pairwise disjoint maximum
independent sets $S_{1},\dots,S_{k}$ in $G$ such that $A_{i}\subseteq S_{i}$
for $i\in[k]$.

  * •

$\mathbf{E_{s}}$ if every independent set in $G$ of size at most $s$ is
contained in a maximum independent set in $G$.

Chvátal and Slater (1993) and Sankaranarayana and Stewart (1992) famously
showed that recognizing $\mathbf{W_{1}}$ graphs or, equivalently, well-covered
graphs is coNP-complete. We extend this result by showing that recognizing
$\mathbf{W_{k+1}}$ graphs in either $\mathbf{W_{k}}$ or $\mathbf{E_{s}}$
graphs is coNP-complete. This answers a question of Levit and Tankus (2023)
and strengthens a theorem of Feghali and Marin (2024). We also show that
recognizing $\mathbf{E_{s+1}}$ graphs is $\Theta_{2}^{p}$-complete even in
$\mathbf{E_{s}}$ graphs, where $\Theta_{2}^{p}=\text{P}^{\text{NP}[\log]}$ is
the class of problems solvable in polynomial time using a logarithmic number
of calls to a Sat oracle. This strengthens a theorem of Bergé, Busson, Feghali
and Watrigant (2023). We also obtain the complete picture of the complexity of
recognizing chordal $\mathbf{W_{k}}$ and $\mathbf{E_{s}}$ graphs which, in
particular, simplifies and generalizes a result of Dettlaff, Henning and Topp
(2023).

##  1 Introduction

In a graph, an _independent set_ is a set of pairwise non-adjacent vertices.
An independent set is said to be _maximum_ if it is of maximum size, and
_maximal_ if it is not a subset of any other independent set. Merging these
two notions, Plummer [17] introduced the class of _well-covered_ graphs,
defined as those graphs in which every maximal independent set is also
maximum. Well-covered graphs have since been extensively studied; for
instance, the problem of recognizing well-covered graphs is coNP-complete on
general graphs [5, 22], but polynomial-time solvable on claw-free graphs [25],
bipartite graphs [20], graphs with girth at least $5$ [9], graphs with no
cycle of length $4$ and $5$ [10], graphs of bounded degree [4], chordal graphs
[19], cographs [13], and perfect graphs with bounded clique number [6]. See
the seminal survey by Plummer for more details [18].

In this paper, we continue the study of well-covered graphs from a complexity
viewpoint, though in a broader context. Staples introduced in 1975 [24] the
hierarchy $\mathbf{W_{k}}$, as a generalization of well-covered graphs. For a
positive integer $k$, a graph $G$ is $\mathbf{W_{k}}$ if for any $k$ pairwise
disjoint independent vertex subsets $A_{1},\dots,A_{k}$ in $G$, there exist
$k$ pairwise disjoint maximum independent sets $S_{1},\dots,S_{k}$ in $G$ such
that $A_{i}\subseteq S_{i}$ for $i\in[k]$. Observe, by definition, that a
graph is $\mathbf{W_{1}}$ if and only if it is well-covered, and that
$\mathbf{W_{k+1}}\subseteq\mathbf{W_{k}}$ for each $k\geqslant 1$. The class
of $\mathbf{W_{2}}$ graphs was studied more specifically due to its relation
to _shedding vertices_ : a vertex $v$ in a graph $G$ is shedding if there does
not exist an independent set in $V(G)\setminus N[v]$ which dominates $N(v)$.
In particular, a graph without isolated vertices is $\mathbf{W_{2}}$ if, and
only if, all of its vertices are shedding [14]. Shedding vertices were also
used in order to characterize well-covered graphs of high girth [9] (they are
called extendable vertices). Deciding whether a vertex of a graph is shedding
is coNP-complete [15], even in triangle-free graphs. Similarly, recognizing
$\mathbf{W_{k}}$ graphs was recently shown to be coNP-complete (for each fixed
$k\geqslant 2$) [8], answering a recent question from [15]. However, the more
challenging complexity problems (also raised in [15]) of recognizing
$\mathbf{W_{2}}$ graphs and shedding vertices when the input graph is well-
covered remained open.

######  Problem 1 ([15]).

Determine the complexity of recognizing $\mathbf{W_{2}}$-graphs when the input
graph is well-covered.

######  Problem 2 ([15]).

Determine the complexity of recognizing shedding vertices when the input graph
is well-covered.

In this paper, we resolve Problems 1 and 2 in the following theorems.

######  Theorem 1.1.

Let $k\geqslant 2$ and $G$ be $\mathbf{W_{k-1}}$. Then deciding if $G$ is
$\mathbf{W_{k}}$ is coNP-complete.

######  Theorem 1.2.

Deciding whether a vertex is shedding in a well-covered graph is coNP-
complete.

The proofs of these can be found in Section 2.

A related class of graphs, namely B-graphs, was introduced by Berge [2] to
study well-covered graphs. It consists of graphs in which every vertex belongs
to a maximum independent set (MIS). As recently observed [3], B-graphs play a
key role in Wi-Fi networks: under saturation, the throughput of an access
point of a Wi-Fi network is proportional to the number of MIS this access
point belongs to in the conflict graph. In particular, if the conflict graph
is a B-graphs, it ensures that no access points will have its throughput close
to zero.

In [6], the class of B-graphs was generalized to that of _$k$ -extendable
graphs_; for a positive integer $k$, a graph is $k$-extendable if every
independent set of size (exactly) $k$ is contained in an MIS. Thus, B-graphs
are exactly the $1$-extendable graphs and a graph $G$ is well-covered if and
only if it is $k$-extendable for every $k\in\\{1,2,\dots,|V(G)|\\}$. This
motivates an extension of the $\mathbf{W_{k}}$ hierarchy via
$k$-extendability. Namely, if we denote by $\mathbf{E_{s}}$ the class of
$k$-extendable graphs for all $k\in[s]$, we can infer that
$\mathbf{E_{s+1}}\subseteq\mathbf{E_{s}}$ and
$\mathbf{W_{1}}\subseteq\mathbf{E_{s}}$. At the same time, there exist graphs
which are $k$-extendable but not $(k-1)$-extendable (for instance, a graph
with a universal vertex and different from a clique might be $2$-extendable,
but cannot be $1$-extendable), hence the class $\mathbf{E_{s}}$ and the class
of $s$-extendable graphs ($s$ fixed) are not identical. However, notice that
in a $s$-extendable graph, where $s$ is fixed, testing $k$-extendability for
$k\leqslant s$ can be done in polynomial time. This is achieved by checking if
any independent set of size $k$ is contained in an independent set of size
$s$. Dean and Zito [6] showed that in certain classes of graphs (namely:
bipartite graphs and perfect graphs with bounded clique number), if the graph
is $k$-extendable for “small values” of $k$ then it is well-covered. It is
thus natural to ask whether testing well-coveredness becomes easier if the
input graph is $\mathbf{E_{s}}$. Unfortunately, we demonstrate that this is
not the case, as stated in our next theorem, which we prove in Section 3.

######  Theorem 1.3.

Let $k\geqslant 2$ and $s\geqslant 1$ and $G$ be $\mathbf{E_{s}}$. Then
deciding whether $G$ is $\mathbf{W_{k}}$ is coNP-complete.

We should note that, unlike recognizing $\mathbf{W_{1}}$ graphs (which are in
coNP [5, 22], where a polynomial certificate for not being well-covered
consists of two maximal independent sets of different sizes), there is no
known polynomial certificate for being $1$-extendable, despite recognizing
$1$-extendable graphs being NP-hard [3], even on subcubic planar graphs and on
unit disk graphs. Moreover, a close examination of the same reduction also
establishes that recognizing $1$-extendable graphs is coNP-hard (see Section
3). So unless NP = coNP, this problem is neither in NP nor in coNP. In our
next result, whose proof is given in Section 3, we determine the precise
complexity of this problem.

######  Theorem 1.4.

Let $s\geqslant 1$ and $G$ be $\mathbf{E_{s-1}}$. Then deciding whether $G$ is
$\mathbf{E_{s}}$ is $\Theta_{2}^{p}$-complete.

Notice that $\Theta_{2}^{p}=\text{P}^{\text{NP}[\log]}$ is the class of
problems that can be solved by a polynomial time algorithm using a logarithmic
number of calls to a Sat oracle.

For tractable graph classes, we note that a characterization of chordal well-
covered graphs was established in [19], stating that _a chordal graph $G$ is
well-covered if and only if the simplices of $G$ form a partition of $V(G)$_,
which, in turn, leads to a linear-time algorithm for deciding if a chordal
graph is well-covered. In [3], the authors asked whether an analogous
characterization for $1$-extendable graphs can be established. This was
recently settled in [7] using a new object called successive clique covers.
Unfortunately, this characterization does not yield a linear-time algorithm.
In our next theorem, whose proof is in Section 4.2, we simplify their
characterization, and use it to describe a linear-time algorithm.

######  Theorem 1.5.

A chordal graph $G$ is $1$-extendable if, and only if, there exists a
partition of $V(G)$ into $\alpha(G)$ parts such that each part is a maximal
clique of $G$. This can be tested in linear time.

Finally, in Section 5, we conclude the paper with some old and new open
problems.

##  2 Recognizing $\mathbf{W_{k}}$ graphs

We start by proving simultaneously Theorem 1.2 and the case $k=2$ of Theorem
1.1, thereby resolving both Problems 1 and 2.

$v$$v_{1}$$v_{2}$$v_{m}$$x_{1}$$\overline{x_{1}}$$x_{2}$$\overline{x_{2}}$$x_{n}$$\overline{x_{n}}$
Figure 1: The graph $G^{\prime}$.

######  Theorem 2.1.

Let $G$ be a well-covered graph and $v\in V(G)$. Then the problems of deciding
if $G$ is $\mathbf{W_{2}}$ and if $v$ is shedding are both coNP-complete.

###### Proof.

From [8], recognizing $\mathbf{W_{2}}$ graphs is in coNP. And deciding if a
vertex is shedding is also in coNP, where a certificate consists of an
independent set $S$ of $V(G)\setminus N[v]$ that dominates $N(v)$.

To show the hardness for both problems, we describe a generic reduction from
the complement of 3-Sat. Let $\Phi$ be a 3-CNF formula with a set $C$ of $m$
clauses $c_{1},...,c_{m}$ and a set $X$ of $n$ variables $x_{1},...,x_{n}$.
Consider the graph $G$ (with $m+1+4n$ vertices) that is obtained from $\Phi$
as follows:

  * •

create a clique $K$ of size $m$ with vertex labels $v_{1},\dots,v_{m}$;

  * •

add a new vertex $v$ adjacent to all vertices of $K$;

  * •

for each variable $x_{i}$, create vertices $x_{i}^{1}$, $x_{i}^{2}$,
$\overline{x_{i}}^{1}$, $\overline{x_{i}}^{2}$, and add all (six) possible
edges between them;

  * •

if $x_{i}$ (resp. $\overline{x_{i}}$) appears in clause $c_{j}$, add the edges
$x_{i}^{1}v_{j}$ and $x_{i}^{2}v_{j}$ (resp. $\overline{x_{i}}^{1}v_{j}$ and
$\overline{x_{i}}^{2}v_{j}$).

That completes the construction of $G$; see also Figure 1 for an illustration.

We must show that $G$ is well-covered and that $\Phi$ is unsatisfiable if, and
only if, $G$ is $\mathbf{W_{2}}$. For $1\leq i\leq n$, write
$K^{i}=\\{\ell^{b}\\}_{\ell\in\\{x_{i},\overline{x_{i}}\\},b\in\\{1,2\\}}$ and
note that $K^{i}$ is, by construction, isomorphic to the complete graph
$K_{4}$ on four vertices.

######  Claim.

$G$ is well-covered.

###### Proof.

Any independent set of $G$ can contain at most vertex from $\\{v\\}\cup K$ and
at most one vertex from each $K^{i}$. Thus, $\alpha(G)\leqslant n+1$. However,
since we can construct an independent set of size $n+1$ by taking
$\\{v\\}\cup\\{x_{i}^{1}\\}_{1\leqslant i\leqslant n}$, we have that
$\alpha(G)=n+1$. So, to prove the claim, if we let $S$ be any maximal
independent set of $G$, we must show that $S$ has size $n+1$.

If $S$ contains $v$, then $S-\\{v\\}$ is a maximal independent set of
$G-(K\cup\\{v\\})$, which is exactly a disjoint union of $n$ copies of
$K_{4}$. Thus, $S$ has size $n+1$. So we may assume that $S$ does not contain
$v$. In this case, it must contain, by maximality and construction, a vertex
$v_{j}\in V(K)$ for some $j\in[m]$. Consider the literals
$\ell_{1},\ell_{2},\ell_{3}$ appearing in $c_{j}$. Then $S-\\{v_{j}\\}$ is
maximal in
$G-(K\cup\\{v\\}\cup\\{\ell_{i}^{b}\\}_{i\in\\{1,2,3\\},b\in\\{1,2\\}})$, and,
as it consists of a disjoint union of $n-3$ copies of $K_{4}$ and three copies
of $K_{2}$, $S$ has again size $n+1$, as required. ∎

We first show that $\Phi$ is unsatisfiable if, and only if, $G$ is
$\mathbf{W_{2}}$.

First, suppose that $G$ is $\mathbf{W_{2}}$. For any truth assignment to $X$,
for $1\leqslant i\leqslant n$, define a new variable $\ell_{i}$ by
$\ell_{i}=x_{i}$ if $x_{i}$ is set to true, and by $\ell_{i}=\overline{x_{i}}$
otherwise. Let $S_{1}=\\{\ell_{i}^{1}\\}_{1\leqslant i\leqslant n}$ and
$S_{2}=\\{v\\}$ and note that these form independent sets in $G$. Now, since
$G\in\mathbf{W_{2}}$, $S_{1}$ is contained in an MIS $I$ of $G$ and, by our
choice of $S_{2}$, $I=S_{1}\cup\\{v_{j}\\}$ for some $j\in[m]$. Thus, by the
definition of $S_{1}$, $v_{j}$ is not adjacent to any vertex that corresponds
to a literal that is set to true, and hence the clause $c_{j}$ is not
satisfied by the assignment. Thus, for every truth assignment there is an
unsatisfied clause, which means that $\Phi$ is unsatisfiable, as needed.

Conversely, suppose that $\Phi$ is unsatisfiable, and let $S_{1}$ and $S_{2}$
be disjoint independent sets of $G$. We show how to extend both of them to
disjoint independent sets of size $n+1$. The first step is to add a vertex
from $V(K)\cup\\{v\\}$. For each $r\in\\{1,2\\}$, if $S_{r}\cap
V(K)=\emptyset$, there exists a vertex $v_{i_{r}}$ of $K$ such that
$v_{i_{r}}$ is not adjacent to any vertex of $S_{r}$, since otherwise, by
setting a literal to true whenever its corresponding vertex is a member of
$S_{r}$, we can readily infer, by construction, that $\Phi$ is satisfied,
which is a contradiction. Hence, if $S_{1}\cap V(K)=\emptyset$, we can add
$v_{i_{1}}$ to $S_{1}$ unless $v_{i_{1}}\in S_{2}$, in which case we add $v$
to $S_{1}$. The same argument holds for $S_{2}$. So we can assume that both
$S_{1}$ and $S_{2}$ contain a vertex from $V(K)\cup\\{v\\}$. For each
$i\in[n]$ and $r\in\\{1,2\\}$ such that $S_{r}$ does not contain any vertex
from $K^{i}$, observe that there are always at least two vertices from $K^{i}$
which are not adjacent to any vertex of $S_{r}$, hence we can add vertices so
that both $S_{1}$ and $S_{2}$ contain a different vertex from each $K^{i}$.
Eventually, the resulting sets $S_{1}$ and $S_{2}$ are disjoint, independent
and, by construction, of size $n+1$. This completes the hardness of deciding
if $G$ is $\mathbf{W_{2}}$.

It remains to show that $\Phi$ is unsatisfiable if, and only if, $v$ is
shedding.

If $\Phi$ is satisfiable by some truth assignment, define a new variable
$\ell_{i}=x_{i}$ if $x_{i}$ is set to true and $\ell_{i}=\overline{x_{i}}$
otherwise. Consider the independent sets $S=\\{\ell_{i}^{1}\\}_{1\leqslant
i\leqslant n}$. Since the truth assignment satisfies $\Phi$, $S$ dominates
$V(K)=N(v)$, and thus $v$ is not shedding.

Conversely, if $v$ is not shedding, there exists an independent set $S$ of
$V(G)\setminus N[v]$ that dominates $N(v)=V(K)$. Up to the addition of some
vertices, we assume that $S$ is maximal in $V(G)\setminus N[v]$, and thus
contains exactly one vertex per $K^{i}$ for any $1\leqslant i\leqslant n$.
Consider the truth assignment $\mu$ on $X$ defined by $\mu(\ell)=1$ if, and
only if, $\ell^{1}\in S$ or $\ell^{2}\in S$ for some literal $\ell$. Since any
clause vertex is dominated by $S$, $\mu$ satisfies $\Phi$. This completes the
proof. ∎

###### Proof of Theorem 1.1.

From [8], recognizing $\mathbf{W_{k}}$ graphs is in coNP.

The proof of hardness is essentially identical to that of Theorem 2.1, but we
include the details for completeness. We reduce from the complement of 3-Sat.
Let $\Phi$ be a 3-CNF formula with a set $C$ of $m$ clauses $c_{1},...,c_{m}$
and a set $X$ of $n$ variables $x_{1},...,x_{n}$. Consider the graph $G$ that
is obtained from $\Phi$ as follows:

  * •

create a clique $K$ of size $m$ with vertex labels $v_{1},\dots,v_{m}$;

  * •

create a clique $U$ of size $k-1$ with vertex labels $u_{1},\dots,u_{k-1}$ and
add an edge between each vertex of $U$ and each vertex of $K$;

  * •

for each variable $x_{i}$, add the vertices $x_{i}^{1},\cdots x_{i}^{k}$ and
$\overline{x_{i}}^{1},\cdots\overline{x_{i}}^{k}$, and all possible edges
between them;

  * •

if $x_{i}$ (resp. $\overline{x_{i}}$) appears in clause $c_{j}$, add the edges
$(x_{i}^{b},v_{j})$ (resp. $(\overline{x_{i}}^{b},v_{j})$) for each $b\in[k]$.

For $1\leq i\leq n$, write
$K^{i}=\\{\ell^{b}\\}_{\ell\in\\{x_{i},\overline{x_{i}}\\},b\in[k]}$ and note
that $K^{i}$ is, by construction, isomorphic to the complete graph $K_{2k}$.

######  Claim.

$G$ is $\mathbf{W_{k-1}}$.

###### Proof.

As before, $\alpha(G)=n+1$. Now, let $A_{1},\dots,A_{k-1}$ be disjoint
independents sets of $G$. We must show that there exists pairwise vertex
disjoint independents sets $S_{1},\dots,S_{k-1}$ each of size $n+1$ such that
$A_{i}\subseteq S_{i}$ for $i\in[k-1]$.

Since $U$ is of size $k-1$ and is not adjacent to any vertex of any $K^{i}$,
we can extend each $A_{r}$ to make sure that $|A_{r}\cap(U\cup K)|=1$ for
every $r=1,\dots,k-1$. Now, for every $r\in[k-1]$, if $A_{r}\cap K=\emptyset$,
then since each $K^{i}$ consists of $2k$ vertices, one can extend each $A_{r}$
so that $|A_{r}\cap K^{i}|=1$. If $A_{r}\cap K=\\{v_{j}\\}$ for some
$j\in[m]$, then since we can assume that each clause does not contain a
literal and its negation, there must be $k$ vertices of each $K^{i}$ with no
neighbor in $A_{r}$, hence we can extend $A_{i}$ to an independent set of size
$n+1$. ∎

We now show that $\Phi$ is unsatisfiable if, and only if, $G$ is
$\mathbf{W_{k}}$. First, suppose that $G$ is $\mathbf{W_{k}}$. For any truth
assignment to $X$, for $1\leqslant i\leqslant n$, define a new variable
$\ell_{i}$ by $\ell_{i}=x_{i}$ if $x_{i}$ is set to true, and by
$\ell_{i}=\overline{x_{i}}$ otherwise. Let $S_{r}=\\{u_{r}\\}$ for
$r\in\\{1,\dots,k-1\\}$ and $S_{k}=\\{\ell_{i}^{1}\\}_{1\leqslant i\leqslant
n}$. Clearly, $S_{1},\dots,S_{k-1}$ are pairwise disjoint independent sets in
$G$. Since, by assumption, $G\in\mathbf{W_{k}}$, each $S_{k}$ is contained in
an MIS $I_{k}$ of $G$. By our choice of the $S_{j}$’s,
$I_{k}=S_{k}\cup\\{v_{j}\\}$ for some $j\in[m]$. Thus, by the definition of
$S_{k}$, $v_{j}$ is not adjacent to any vertex that corresponds to a literal
that is set to true, and hence the clause $c_{j}$ is not satisfied by the
assignment. Thus, for every truth assignment there is an unsatisfied clause,
which means that $\Phi$ is unsatisfiable, as needed.

Conversely, suppose that $\Phi$ is unsatisfiable, and let $S_{1},\dots,S_{k}$
be disjoint independent sets of $G$. We show that there exists pairwise
disjoint independents sets $T_{1},\dots,T_{k}$ each of size $n+1$ such that
$S_{i}\subseteq T_{i}$ for $i\in[k]$.

The first step is to add a vertex from $V(K)\cup V(U)$. Specifically, for
$r\in\\{1,\cdots,k\\}$, if $S_{r}\cap V(K)=\emptyset$, then there exists a
vertex $v_{i_{r}}$ of $K$ such that $v_{i_{r}}$ is not adjacent to any vertex
of $S_{r}$, since otherwise, by setting a literal to true whenever its
corresponding vertex is a member of $S_{r}$, we can readily infer, by
construction, that $\Phi$ is satisfied, which is a contradiction. Hence, if
$S_{1}\cap V(K)=\emptyset$, we can add $v_{i_{1}}$ to $S_{1}$ unless
$v_{i_{1}}\in\bigcup_{r>1}S_{r}$, in which case there exists $u_{j_{1}}\in
V(U)$ such that $u_{j_{1}}\notin\bigcup_{r>1}S_{r}$. The same argument holds
for $S_{r}$ for $r\in\\{2,\cdots,k\\}$. In the following, we may assume that
all $S_{r}$ contain a vertex from $V(K)\cup V(U)$. For each $i\in[n]$ and
$r\in\\{1,\cdots,k\\}$ such that $S_{r}$ does not contain any vertex from
$K^{i}$, observe that there are always at least two vertices from $K^{i}$
which are not adjacent to any vertex of $S_{r}$, hence we can add vertices so
that all $S_{r}$ contain a different vertex from each $K^{i}$, as desired. ∎

Since $\mathbf{W_{k}}\subseteq\mathbf{E_{s}}$ for any $s,k\geqslant 1$, we
have the following:

######  Corollary 1.

Let $k\geqslant 2$ and $s\geqslant 1$ and $G$ be $\mathbf{E_{s}}$. Then
deciding if $G$ is $\mathbf{W_{k}}$ is coNP-complete.

We can also address the missing case in the statement of Corollary 1 (with $k$
replaced by $1$), which requires a different proof.

######  Theorem 2.2.

Let $s\geqslant 1$ and $G$ be $\mathbf{E_{s}}$. Then deciding if $G$ is well-
covered is coNP-complete.

###### Proof.

From [5], recognizing well-covered graphs is in coNP. We reduce from the
complement of 3-Sat. Let $\Phi$ be a 3-CNF formula with a set $C$ of clauses
$c_{1},...,c_{m}$ and a set $X$ of variables $x_{1},...,x_{n}$.

We first test all $O(n^{s}\cdot 2^{s})$ partial assignments of $s$ variables.
If, for one of them, all clauses are satisfied, then it means that $\Phi$ is a
satisfiable formula, and we output in this case a dummy negative instance of
our problem. In the following, we can thus assume that for any partial
assignment of $s$ variables, there is at least one clause which is not (yet)
satisfied.

Let $G$ be the graph obtained from $\Phi$ as follows:

  * •

create a clique $K$ of size $m$ with vertex labels $v_{1},\dots,v_{m}$;

  * •

for each variable $x_{i}$, add three new vertices
$u_{i},\overline{u_{i}},w_{i}$ that form a triangle;

  * •

if $x_{i}$ (resp. $\overline{x_{i}}$) appears in clause $c_{j}$, add the edge
$u_{i}v_{j}$ (resp. $\overline{u_{i}}v_{j}$).

######  Claim.

$G$ is $\mathbf{E_{s}}$.

###### Proof.

It can be observed that $\alpha(G)=n+1$. Let $S\subseteq V(G)$ be an
independent set of size $s$, and let $I=\\{i\mid
S\cap\\{u_{i},\overline{u_{i}},w_{i}\\}=\emptyset\\}$. If $S$ contains a
vertex from $K$, then $S\cup\\{w_{i}\\}_{i\in I}$ is an independent set of
size $n+1$ that contains $S$. Assume now that $S\cap K=\emptyset$. If there is
a vertex $c$ in $K$ that has no neighbor in $S$, we add $c$ to $S$ and proceed
as previously. Otherwise, assigning $true$ (resp. $false$) to every variable
$x_{i}$ such that $u_{i}\in S$ (resp. $\overline{u_{i}}\in S$) leads to a
partial assignment of at most $s$ variables such that all clauses are
satisfied, which is impossible. ∎

Now, suppose $G$ is well-covered. For any truth assignment to the variables in
$X$, we form an independent set $S$ in $G$ by adding to $S$ vertex $u_{i}$ if
variable $x_{i}$ is set to true, and vertex $\overline{u_{i}}$ if variable
$x_{i}$ is set to false. Note that $|S|=n$; moreover, as $G$ is well-covered
and $\alpha(G)=n+1$, there is a vertex not in $S$ that has no neighbor in $S$.
By construction, this vertex is $v_{i}$ for some $i\in[m]$, and so clause
$c_{i}$ does not contain a true literal. Therefore, $\Phi$ is unsatisfiable.

Conversely, suppose that $\Phi$ is unsatisfiable. Let $S$ be any maximal
independent set in $G$. By maximality,
$|S\cap\\{u_{i},\overline{u_{i}},w_{i}\\}|=1$ for each $i\in[n]$. Moreover,
observe that $|S\cap K|=1$ since if $S\cap K=\emptyset$ then, by setting to
true the variables in $S\setminus\\{w_{i}\\}_{1\leqslant i\leqslant n}$, one
obtains a (possibly partial) truth assignment that satisfies $\Phi$, which is
a contradiction. Thus $|S|=n+1$ as needed. ∎

##  3 Recognizing $\mathbf{E_{s}}$ graphs

In this section, we prove Theorem 1.4. First, let us make a few observations.
Recall that recognizing $1$-extendable graphs is NP-hard [3], though the
existence of an NP (or coNP) certificate is not clear. Moreover, its NP-
hardness proof is via a reduction from Exact MIS, where, given a graph $G$ and
an integer $k$, the problem is to determine if $\alpha(G)=k$, which, in turn,
is NP-hard via a reduction from the classical Maximum Independent Set problem.
Let us note that Exact MIS belongs to the DP complexity class, introduced by
Papadimitriou [16], and consists of problems which are the “intersection” of
an NP problem and a coNP problem. Notice that this is different from being in
NP and in coNP, since being DP-complete actually implies being both NP-hard
and coNP-hard, which in turn implies not being in NP nor in coNP, unless NP =
coNP. However, it appears that DP does not contain the problem of recognizing
$1$-extendable graphs. Indeed, we show rather surprisingly that recognizing
$1$-extendable graphs, and more generally $\mathbf{E_{s}}$ graphs, is
$\Theta_{2}^{p}$-complete. The complexity class
$\Theta_{2}^{p}=\text{P}^{\text{NP}[O(\log(n)]}$ refers to problems solvable
by a polynomial-time deterministic algorithm using a logarithmic number of
calls to a Sat oracle. This class has received attention, mainly because it
contains various optimization problems across fields such as AI and voting
schemes [21, 23, 26, 27]. Interestingly, it also contains an approximation
version of well-coveredness [11], where one is interested in the graph class
where the greedy algorithm for Maximum Independent Set provides a constant
approximation ratio. We first show that recognizing $\mathbf{E_{s}}$ graphs is
in $\Theta_{2}^{p}$.

######  Lemma 1.

For any $s\geqslant 1$, recognizing $\mathbf{E_{s}}$ graphs is in
$\Theta_{2}^{p}$.

###### Proof.

We must describe an algorithm that solves the problem with only a logarithmic
number of calls to a Sat oracle. To do so, for a fixed $s\geqslant 1$, we
introduce the problem Partial $s$-Extendable, where, given a graph $G$ and an
integer $r$, the task is to determine if each independent set of size at most
$s$ can be extended to an independent set of size at least $r$. This problem
is in NP, a certificate being the set of independent sets of $G$ of size $r$
that extend all independent sets of size at most $s$, and this certificate has
a size of at most $O(r\cdot n^{s})$. Therefore, Partial $s$-Extendable can be
solved with a Sat oracle.

The algorithm recognizing $\mathbf{E_{s}}$ graphs operates as follows on input
$G$:

  1. 1.

Compute $r=\alpha(G)$ using binary search, requiring $O(\log(n))$ Sat oracle
calls to solve Maximum Independent Set.

  2. 2.

Solve Partial $s$-Extendable on input $(G,r)$ using only one Sat oracle.

This algorithm straightforwardly recognizes $\mathbf{E_{s}}$ graphs in
polynomial time, utilizing $O(\log(n))$ Sat oracle calls, thus the problem is
in $\Theta_{2}^{p}$ as required. ∎

Thus, it remains to establish hardness. To do so, we shall proceed by
induction on $s$. To begin with, we need an complete problem for the class
$\Theta_{2}^{p}$. An example of such a problem is MIS Equality which asks,
given two graphs $G$ and $H$, if $\alpha(G)=\alpha(H)$. Notice that the
equivalent problems for graph coloring, vertex cover and clique are also
$\Theta_{2}$-complete [26, 11]. In addition, we shall need the following
construction (extracted from [3]).

For two disjoint graphs $G$ and $H$, let $\pi(G,H)$ be the graph obtained from
$G$ and $H$ by adding a complete bipartite graph $(\Pi_{G}:=\\{\pi_{u}\mid
u\in V(G)\\},\Pi_{H}:=\\{\pi_{u}\mid u\in V(H)\\})$, and adding the edge
$u\pi_{u}$ for each $u\in V(G)\cup V(H)$, Notice that $\pi(G,H)$ has
$2(|V(G)|+|V(H)|)$ vertices and
$\alpha(\pi(G,H))=\max(|V(G)|+\alpha(H),|V(H)|+\alpha(G))$. Let us first
address the base case $s=1$.

######  Lemma 2.

Recognizing $1$-extendable graphs is $\Theta_{2}^{p}$-hard.

###### Proof.

To prove the lemma, we reduce from MIS Equality.

Let $(G,H)$ be an instance of MIS Equality, where up to the addition of some
universal vertices, both $G$ and $H$ have the same number $n$ of vertices. Let
$G^{\prime}:=\pi(G,H)$, so that $G^{\prime}$ has $4n$ vertices and
$\alpha(G^{\prime})=n+\max(\alpha(G),\alpha(H))$. We show that $G^{\prime}$ is
$1$-extendable if and only if $\alpha(G)=\alpha(H)$.

Suppose that $\alpha(G)=\alpha(H)=\alpha$. For each vertex $v\in V(G)$, set
$S_{v}=\\{v\\}\cup(\Pi_{G}\setminus\\{\pi_{v}\\})\cup S_{H}$, where $S_{H}$ is
any MIS of $H$. Then $S_{v}$ has cardinality $n+\alpha$ and thus is an MIS of
$G^{\prime}$. Notice that $\Pi_{v}\cup S_{H}$ is also an MIS of $G^{\prime}$,
and thus $\pi_{v}$ belongs to an MIS too. By symmetry, all vertices from
$V(H)\cup\Pi_{H}$ belong to an MIS of $G^{\prime}$, thus $G^{\prime}$ is
$1$-extendable.

Now, suppose that $G^{\prime}$ is $1$-extendable. Then either
$\alpha(G^{\prime})=\alpha(G)+n$ or $\alpha(G^{\prime})=\alpha(H)+n$. Assume
that $\alpha(G^{\prime})=n+\alpha(G)$. Let $v\in V(G)$. By $1$-extendability
of $G^{\prime}$, $\pi_{v}$ is in an MIS $S$ of $G^{\prime}$. Let
$S_{G}=(V(G)\cup\Pi_{G})\cap S$ and $S_{H}=(V(H)\cup\Pi_{H})\cap S$. Since
$\pi_{v}\in S$ and $S$ is independent, $S$ contains no vertex from $\Pi_{H}$.
It follows that $S_{H}$ is an MIS of $H$ of cardinality $\alpha(H)$. In
addition, $S_{G}$ is an MIS of $G^{\prime}[V(G)\cup\Pi_{v}]$ and thus has
cardinality $n$. Altogether, $|S|=n+\alpha(H)=\alpha(G^{\prime})$, which gives
$\alpha(G)=\alpha(H)$. This completes the proof. ∎

######  Corollary 2 ([3]).

Recognizing $1$-extendable graphs is both NP-hard and coNP-hard, and thus
neither in NP nor in coNP unless NP=coNP.

To address the general case $s\geq 1$, we require one more lemma. Given a
graph $G$, let $G^{+}=\pi(G_{1},G_{2})$ where $G_{1}$ and $G_{2}$ are two
copies of $G$. Notice that $\alpha(G^{+})=|V(G)|+\alpha(G)$. For brevity, we
write $\Pi_{1}=\Pi_{G_{1}}$ and $\Pi_{2}=\Pi_{G_{2}}$ in $G^{+}$.

######  Lemma 3.

For any graph $G$ and any $s\geqslant 1$, $G^{+}\in\mathbf{E_{s}}$ if and only
if $G\in\mathbf{E_{s-1}}$.

###### Proof.

Suppose first that $G\in\mathbf{E_{s-1}}$. Let $A\subseteq V(G^{+})$ be an
independent set of size at most $s$. We must show that $A$ is contained in an
MIS of $G^{+}$.

Suppose $A\cap(\Pi_{1}\cup\Pi_{2})=\emptyset$. If $A\subseteq V(G_{1})$, then
$A$ can be extended into an independent set of size $|V(G)|$ by adding only
vertices of $\Pi_{1}$, and then, in turn, into an independent set of size
$|V(G)|+\alpha(G)$ by adding any MIS of $G_{2}$. Similarly, if $A\subseteq
V(G_{2})$ then we are done. So we can assume that $A$ intersects both
$V(G_{1})$ and $V(G_{2})$ (notice that this case does not happen if $s=1$). As
$|A|\leq s$, we have that $|A\cap V(G_{1})|\leqslant s-1$. Since
$G_{1}\in\mathbf{E_{s-1}}$, $A\cap V(G_{1})$ can be extended into an MIS
$\tilde{A_{1}}$ of $G_{1}$. At the same time, $A\cap V(G_{2})$ can be extended
to an independent set $\tilde{A_{2}}$ of size $|V(G)|$ using only new vertices
from $\Pi_{2}$. Notice that $\tilde{A_{1}}\cup\tilde{A_{2}}$ is an independent
set of size $|V(G)|+\alpha(G)$ that contains $A$.

So we can assume that $A\cap(\Pi_{1}\cup\Pi_{2})\neq\emptyset$. Since there
are all possible edges between $\Pi_{1}$ and $\Pi_{2}$ in $G^{+}$, trivially
$A$ intersects at most one of $\Pi_{1}$ and $\Pi_{2}$, say $\Pi_{1}$. Let
$A_{1}=A\cap(V(G_{1})\cup\Pi_{1})$, and $A_{2}=A\cap V(G_{2})$. As in the
preceding paragraph, $A_{1}$ can be extended to an independent set
$\tilde{A_{1}}$ of size $|V(G)|$ using only new vertices from $\Pi_{1}$, and
since $|A_{2}|\leqslant s-1$ and $G_{2}\in\mathbf{E_{s-1}}$, $A_{2}$ can be
extended to an independent set $\tilde{A_{2}}$ of size $\alpha(G)$ using only
vertices from $V(G_{2})$. Then $\tilde{A_{1}}\cup\tilde{A_{2}}$ is an MIS of
$G^{+}$ that contains $A$. Therefore, $G^{+}$ is $\mathbf{E_{s}}$.

Conversely, suppose $G^{+}\in\mathbf{E_{s}}$. Let $A\subseteq V(G)$ be an
independent set of $G$ of size at most $s-1$. We must show that $A$ extends
into an MIS in $G$. Let $v\in\Pi_{2}$, and consider the independent set
$A_{1}\cup\\{v\\}$ where $A_{1}$ is exactly $A$ in the copy $G_{1}$ of $G$ in
$G^{+}$. Since $A_{1}\cup\\{v\\}$ is an independent set of $G^{+}$ of size at
most $s$, it can be extended to an MIS $S$ of $G^{+}$, which has size
$|V(G)|+\alpha(G)$. Since $v\in S$, $S\cap\Pi_{1}=\emptyset$. Thus, $S$ can be
partitioned into two sets $S_{1}$ and $S_{2}$, where $S_{1}$ induce a maximum
independent set of $G_{1}$ and $S_{2}$ a maximum independent set of
$G^{+}[V(G_{2})\cup\Pi_{2}]$. We notice that $|S_{2}|=|V(G)|$, and thus
$|S_{1}|=\alpha(G)$. In addition, $A_{1}\subseteq S_{1}$ and so $A$ can be
extended to an MIS of $G$. ∎

We are now ready to prove Theorem 1.4; in fact, we prove the following more
general result.

######  Theorem 3.1.

Let $s\geqslant 2$ and $G$ be $\mathbf{E_{s-1}}$. Then deciding whether $G$ is
$\mathbf{E_{s}}$ is $\Theta_{2}^{p}$-complete.

###### Proof.

By Lemma 1, the problem is in $\Theta_{2}^{p}$. To show hardness, we proceed
by induction on $s$. For $s=1$, by Lemma 2, $\mathbf{E_{1}}$ graphs is
$\Theta_{2}^{p}$-complete on arbitrary (that is, $\mathbf{E_{0}}$) graphs. So
we can assume that $s\geq 2$ and that, given a graph $G$ in
$\mathbf{E_{s-2}}$, deciding whether $G$ is $\mathbf{E_{s-1}}$ is
$\Theta_{2}^{p}$-hard.

Now, since $G\in\mathbf{E_{s-2}}$, it follows from Lemma 3 that
$G^{+}\in\mathbf{E_{s-1}}$ and that $G\in\mathbf{E_{s-1}}$ if and only if
$G^{+}\in\mathbf{E_{s}}$. This implies the result. ∎

As said in the introduction, $s$-extendable graphs and $\mathbf{E_{s}}$ are
slightly different. Nevertheless, the same proof, word by word, implies

######  Corollary 3.

Let $s\geq 1$. Recognizing $s$-extendable graphs is $\Theta_{2}^{p}$-complete.

##  4 Chordal graphs

Let us recall some usual definitions and facts.

A vertex $v$ is simplicial in a graph $G$ if $G[N(v)]$ is a complete graph. If
$v$ is simplicial, we say that $N[v]$ is a simplex. A chordal graph is a graph
with no induced cycle of size at least four. By a celebrated and folklore
theorem of Dirac, a graph $G$ is chordal if and only if (iff) every induced
subgraph of $G$ has a simplicial vertex. Phrased differently, $G$ is chordal
iff there exists an ordering $v_{1},\dots,v_{n}$ of $V(G)$, called a _perfect
elimination ordering_ , such that for $i\in[n]$, the graph induced by
$\\{v_{j}:v_{i}v_{j}\in E(G),j<i\\}$ is complete. Another classical and
convenient object related to a chordal graph is its clique tree decomposition.
For any chordal graph, its clique tree decomposition is a tree whose vertex
set is in bijection with set of maximal cliques of $G$, and such that for
every vertex of $G$, the vertices of the tree corresponding to cliques
containing this vertex induce a connected subtree. It is a folklore result
that such object can be found in linear time.

###  4.1 Recognizing $\mathbf{W_{k}}$ chordal graphs

In this subsection, we show that deciding whether a chordal graph is
$\mathbf{W_{k}}$ can be done in linear time for each $k\geq 1$. Recall that
the case $k=1$, that is, the well-coveredness of chordal graphs, has already
been studied before, showing that a chordal graph is well-covered if, and only
if, each vertex belongs to exactly one simplex. Equivalently, the following
result was established.

######  Theorem 4.1 ([19]).

A chordal graph $G$ is well-covered if, and only if there exists a partition
of $V(G)$ into simplices.

The previous theorem directly leads to an algorithm that decides if a chordal
graph is well-covered. The naive algorithm that decides if a given chordal
graph $G$ is $\mathbf{W_{k}}$ consists in checking, for any subset of $k-1$
vertices $V^{\prime}\subseteq V(G)$, whether $G-V^{\prime}$ is well-covered.
The complexity of this naive algorithm is $O(n^{k}(n+m))$. This running time
can be improved by generalizing the previous characterization of well-covered
chordal graphs to $\mathbf{W_{k}}$ chordal graphs.

######  Proposition 1.

Let $k\geqslant 1$. A chordal graph $G$ is $\mathbf{W_{k}}$, if and only if,
if there exists a partition of $V(G)$ into simplices, each of them having at
least $k$ simplicial vertices.

###### Proof.

Recall that from Staples, a graph $G$ is $\mathbf{W_{k}}$ if, and only if, for
any set $S\subseteq V(G)$ of $k-1$ vertices, $G-S$ is well-covered and
$\alpha(G)=\alpha(G-S)$.

If a graph $G$ is $\mathbf{W_{k}}$, it is indeed well-covered, and thus there
exists a partition $V_{1},...,V_{q}$ of $V(G)$ such that each $V_{i}$ induces
a simplex. By contradiction, assume that $V_{1}$ has less than $k$ simplicial
vertices. Let $S$ be the set of simplicial vertices of $V_{1}$, we have
$|S|\leqslant k-1$. Then, notice that $G-S$ is not well-covered using the
characterization of chordal well-covered graphs. Indeed, the vertices of
$V_{1}\setminus S$ are not in any simplex.

Reciprocally, if there exists a partition of $V(G)$ into $V_{1},...,V_{q}$
such that each $V_{i}$ is a simplex with at least $k$ simplicial vertices,
then after removing any $k-1$ vertices of $G$, there still exists a partition
of $V(G)$ into simplices, and there is still an MIS of size $q$. ∎

The previous theorem leads to a linear algorithm to check if a chordal graph
is $\mathbf{W_{k}}$. Indeed, one can find the partition into simplices in time
$O(n+m)$, and then check if each simplex has at least $k$ simplicial vertices
in time $O(n+m)$.

###  4.2 Recognizing $\mathbf{E_{s}}$ chordal graphs

In this subsection, we prove Theorem 1.5. Let us first establish the first
part, which consists in the characterization.

######  Theorem 4.2.

Let $G$ be a chordal graph. $G$ is $1$-extendable iff there is a partition of
$V(G)$ into $\alpha(G)$ parts such that each of them is a maximal clique in
$G$.

###### Proof.

Let $G$ be a chordal graph. Assume first that $G$ is $1$-extendable. We prove
by induction on $\alpha(G)$ that $V(G)$ can be partitioned into $\alpha(G)$
maximal cliques, the statement being obvious if $\alpha(G)=1$. In the
following, we assume $\alpha(G)>1$. Let $v$ be a simplicial vertex of $G$
which belongs to a leaf $C_{v}$ of the tree decomposition of $G$ (it is thus a
maximal clique). Let $G^{\prime}=G[V(G)\setminus C_{v}]$. Observe that
$\alpha(G^{\prime})=\alpha(G)-1$, hence we can apply the induction hypothesis
on $G^{\prime}$ and obtain a partition of $V(G^{\prime})$ into $C_{1}$,
$\dots$, $C_{q}$ with $q=\alpha(G)-1$. We claim that for every $i\in[q]$,
$C_{i}$ is also a maximal clique in $G$. Indeed, if there is $u\in C_{v}$ such
that $C_{i}\cup\\{u\\}$ is also a clique, then $u$ would not belong to any
maximum independent set in $G$ which violates its $1$-extendability, since any
maximum independent set of $G$ must intersect $C_{i}$.

We also prove the other direction by induction on $\alpha(G)$. Assume that
$V(G)$ can be partitioned into $C_{1}$, $\dots$, $C_{\alpha(G)}$, where each
$C_{i}$ is a maximal clique. In the tree decomposition of $G$, we choose an
arbitrary node of degree at least $2$ to be the root, and w.l.o.g. we may
assume that $C_{1}$ is a leaf of the tree decomposition. Let $P$ be the
maximal clique of $G$ which is the parent of $C_{1}$ in the tree
decomposition. We denote by $v$ any simplicial vertex of $C_{1}$. Let
$G^{\prime}=G[V(G)\setminus C_{1}]$. We have $\alpha(G^{\prime})=\alpha(G)-1$,
and by induction $G^{\prime}$ is $1$-extendable. It remains to show that every
vertex of $C_{1}$ belongs to a maximum independent set of $G$. This is clearly
the case for $v$ since it is only adjacent to vertices in $C_{1}$. This is
also the case for every $u\in C_{1}\setminus\\{v\\}$ since otherwise it would
mean that $u$ is adjacent to every vertex of $P$, but then $P$ would not be a
maximal clique in $G$. ∎

Deciding if a given chordal graph is $k$-extendable can naively be done in
time $O(n^{k}(n+m))$ by enumerating all independent sets of $G$ of size $k$ in
time $O(n^{k})$ and by checking the independence number of the graph when
removing such an independent set. In particular, with this method the
complexity for testing $1$-extendability of a chordal graph can be done in
$O(n(n+m))$ time. The previous characterization allows to do it in linear
time. We first need the following observation.

######  Lemma 4.

If a chordal graph $G$ is $1$-extendable and $v$ is a simplicial vertex, then
$G-N[v]$ is $1$-extendable.

###### Proof.

First, notice that $\alpha(G-N[v])=\alpha(G)-1$. Let $u\in V(G)\setminus
N[v]$, and since $G$ is $1$-extendable, there exists an MIS $S$ of $G$ such
that $u\in S$. If $S$ does not contain any vertex from $N[v]$, then
$S\cup\\{v\\}$ is an independent set of size $\alpha(G)+1$, which is not
possible. In addition, since $N[v]$ induces a clique, $S$ contains exactly one
vertex of $N[v]$. Thus, $S\setminus N[v]$ is a maximum independent set of
$G-N[v]$ that contains $u$. ∎

We are now ready to complete the proof of Theorem 1.5.

######  Theorem 4.3.

There exists an algorithm that decide if a given chordal graph is
$1$-extendable running in time $O(n+m)$.

###### Proof.

We describe an algorithm that, given a perfect elimination ordering of a
chordal graph, decides if it is $1$-extendable and if it is the case, returns
a partition of the vertex set into maximal cliques.

Let $G$ be a chordal graph, and consider a perfect elimination ordering
$v_{1},...,v_{n}$ of $G$. First, we check in time $O(n+m)$ if $G$ is a clique,
and thus if $\alpha(G)=1$. Otherwise, since $v_{1}$ is simplicial in $G$,
$\alpha(G-N[v_{1}])=\alpha(G)-1$ and $G-N[v_{1}]$ has to be $1$-extendable by
Lemma 4. We run the algorithm on $\\{v_{1},...,v_{n}\\}\setminus N[v_{1}]$,
which checks if $G-N[v_{1}]$ is indeed $1$-extendable. If not, $G$ cannot be
$1$-extendable, and otherwise, we obtain the clique partition
$C_{2},...,C_{q}$ in time $(n-d(v_{1}))+(m-\sum_{u\in N[v_{1}]}d(u))$. Now,
observe that $\\{N[v],C_{2},\dots,C_{q}\\}$ is a partition of $V(G)$ into
maximal cliques unless some vertex $v\in N(v)$ is adjacent to all vertices of
some $C_{i}$, but in that case $v$ cannot belong to any independent set of $G$
(since $\alpha(G)=q+1$), and hence $G$ is not $1$-extendable. This test can be
performed in $O(m)$ time, and thus the overall complexity is $O(n+m)$. ∎

However, contrary to $\mathbf{W_{k}}$, this algorithm cannot be extended to a
linear-time algorithm for recognizing $\mathbf{E_{s}}$ graphs for any
$s\geqslant 2$, as shows the following rather surprising result.

######  Theorem 4.4.

Given a chordal graph $G$ and an integer $s\geqslant 1$, the problem of
deciding whether $G$ is in $\mathbf{E_{s}}$ is coW[2]-hard when parameterized
by $s$.

###### Proof.

We reduce from the complement of Minimum Dominating Set. Let $(G,s)$ be the
input, with $|V(G)|=n$. We may assume that $G$ does not contain a universal
vertex, otherwise the problem is trivial. Construct $G^{\prime}$ as follows:
$V(G^{\prime})$ is composed of a set $C=\\{c_{v}:v\in V(G)\\}$ inducing a
clique together with two sets $I=\\{i_{v}:v\in V(G)\\}$ and
$I^{\prime}=\\{i^{\prime}_{v}:v\in V(G)\\}$ inducing two independent sets,
respectively. For every $uv\in E(G)$, we connect $i_{v}$ to $c_{v}$, $c_{u}$
and $i^{\prime}_{v}$. It can be observed that $G^{\prime}$ is indeed a chordal
graph ($G^{\prime}[C\cup I]$ is a split graph, and $I^{\prime}$ is a set of
vertices of degree one). Moreover, $G^{\prime}$ is $1$-extendable, as
$\alpha(G^{\prime})=n+1$, and each vertex belongs to an independent set of
size $n+1$ since $G$ does not contain a universal vertex. In particular,
observe that any maximum independent set of $G^{\prime}$ contains a vertex of
$C$. We prove that $G^{\prime}\notin\mathbf{E_{s}}$ if, and only if $G$
contains a dominating set of size at most $s$.

If $G^{\prime}\notin\mathbf{E_{s}}$, then there exists a set $S\subseteq
V(G^{\prime})$ of size at most $s$ that is not contained in any independent
set of size $n+1$. If $S\cap C\neq\emptyset$, then let
$S^{\prime}=S\cup\\{i^{\prime}_{v}\mid i_{v}\notin S\\}$, and notice that
$|S^{\prime}|=n+1$ and thus $S^{\prime}$ is an MIS that contains $S$, which is
not possible. So we may assume that $S\cap C=\emptyset$. Let
$S^{\prime}=S\cup\\{i^{\prime}_{v}\mid i_{v}\notin S\\}$ which an independent
set that contains $S$ and for any $v\in V(G)$, $S^{\prime}$ contains either
$i_{v}$ or $i^{\prime}_{v}$. Since $S^{\prime}$ cannot be extended to an MIS,
it implies that $S^{\prime}$ dominates $C$, which implies that $S\cap I$ is in
one-to-one correspondence with a dominating set in $G$ of at most $s$.

Conversely, assume that $G^{\prime}\in\mathbf{E_{s}}$, and let $D$ be any
subset of $V(G)$ of size at most $s$. Then the set $S=\\{i_{v}:v\in D\\}$ is
an independent set of size at most $s$ in $G^{\prime}$ which is thus contained
in an MIS $S^{\prime}$ of $G^{\prime}$, which necessarily intersects $C$ on,
say, $c_{v^{*}}$. It implies that $i_{v^{*}}$ does not belong to $S$ and that
$c_{v^{*}}$ is not adjacent to any vertex of $S$, which means that $v^{*}$
does not belong to $D$ nor is dominated by $D$ in $G$, and thus $D$ is not a
dominating set in $G$. ∎

##  5 Conclusion and open questions

We extended the $\mathbf{W_{k}}$-hierarchy and investigated relative
computational complexities within this hierarchy. We addressed open questions
by demonstrating that recognizing $\mathbf{W_{k}}$ graphs and shedding
vertices are coNP-complete on well-covered graphs. We closed the complexity
gap of testing $1$-extendability, proving that the problem is
$\Theta_{2}^{p}$-complete. Additionally, we provided a simple characterization
of $1$-extendable chordal graphs, leading to a linear-time algorithm to decide
if a graph is $1$-extendable, addressing questions left open in [3]. Up to our
knowledge, several questions remain open, with two of particular interest.

######  Problem 3.

What is the computational complexity of recognizing well-covered triangle-free
graphs?

This problem was indirectly raised by Plummer in his survey [18], where he
asked if there exists a characterization of well-covered or $\mathbf{W_{2}}$
graphs of girth at least $4$. In fact, the complexity of recognizing well-
covered $K_{t}$-free graphs is still open for any constant $t\geqslant 3$, and
even the same problem on graphs such that $\chi(G)=t$ for any fixed
$t\geqslant 3$ [1]. Notice that recognizing $\mathbf{E_{s}}$ triangle-free
graphs is also $\Theta_{2}^{p}$-complete. In the instance $(G,H)$ of MIS
Equality, we can assume that both graphs are triangle-free, up to an even
subdivision of the edges. Then, one can check that every reduction does not
create any triangle. A similar problem, raised by Hujdurović, Milanič, Martin
and Ries, concerns co-well-covered graphs, i.e., graphs for which the
complement is well-covered.

######  Problem 4 ([12]).

What is the computational complexity of recognizing graphs which are both
well-covered and co-well-covered?

Both problems are linked, as any triangle-free graph with no isolated vertex
is co-well-covered. Thus, if recognizing triangle-free well-covered graphs is
coNP-complete, the same holds for the second problem. Conversely, if there
exists a polynomial-time algorithm to check if a graph is well-covered and co-
well-covered, one can recognize triangle-free well-covered graphs in
polynomial time.

We conclude with two problems related to extendability. The first concerns
$1$-extendable graphs with high girth. While there is a characterization of
well-covered graphs of girth $5$, recognizing $1$-extendable graphs is NP-hard
even for arbitrarily large girth [3]. Can we find some structural property for
$1$-extendable graphs of large girth, such as the existence of a linear-size
independent set (which is the case for well-covered graphs of girth $5$)? The
second concerns the computational complexity of recognizing $\mathbf{E_{s}}$
graphs when $s$ is part of the input. The problem is $\Theta_{2}^{p}$-hard but
not complete. One can show that it belongs to $\Pi_{2}^{p}$ in the polynomial
hierarchy; it would be interesting to close this complexity gap.

## References

  * [1] Sancrey Rodrigues Alves, Konrad K. Dabrowski, Luerbio Faria, Sulamita Klein, Ignasi Sau, and Uéverton S. Souza.  On the (parameterized) complexity of recognizing well-covered $(r,\ell)$-graph.  Theoretical Computer Science, 746:36–48, 2018.
  * [2] Claude Berge.  Some common properties for regularizable graphs, edge-critical graphs and b-graphs.  In Peter L. Hammer, Alexander Rosa, Gert Sabidussi, and Jean Turgeon, editors, Theory and Practice of Combinatorics, volume 60 of North-Holland Mathematics Studies, pages 31–44. North-Holland, 1982.
  * [3] Pierre Bergé, Anthony Busson, Carl Feghali, and Rémi Watrigant.  1-extendability of independent sets.  Algorithmica, pages 1–25, 2023.
  * [4] Yair Caro, Mark N. Ellingham, and J. E. Ramey.  Local structure when all maximal independent sets have equal weight.  SIAM J. Discret. Math., 11(4):644–654, 1998.
  * [5] Václav Chvátal and Peter J. Slater.  A note on well-covered graphs.  In John Gimbel, John W. Kennedy, and Louis V. Quintas, editors, Quo Vadis, Graph Theory?, volume 55 of Annals of Discrete Mathematics, pages 179–181. Elsevier, 1993.
  * [6] Nathaniel Dean and Jennifer Zito.  Well-covered graphs and extendability.  Discrete Mathematics, 126(1):67–80, 1994.
  * [7] Magda Dettlaff, Michael A. Henning, and Jerzy Topp.  On $\alpha$-excellent graphs.  Bulletin of the Malaysian Mathematical Sciences Society, 46(2):65, 01/16 2023.  ID: Dettlaff2023.
  * [8] Carl Feghali and Malory Marin.  Three remarks on $\mathbf{W_{2}}$ graphs.  Theoretical Computer Science, 990:114403, 2024.
  * [9] A. Finbow, B. Hartnell, and R.J. Nowakowski.  A characterization of well covered graphs of girth 5 or greater.  Journal of Combinatorial Theory, Series B, 57(1):44–68, 1993.
  * [10] Art Stephen Finbow, Bert L. Hartnell, and Richard J. Nowakowski.  A characterization of well-covered graphs that contain neither 4- nor 5-cycles.  J. Graph Theory, 18(7):713–721, 1994.
  * [11] Edith Hemaspaandra and Jörg Rothe.  Recognizing when greed can approximate maximum independent sets is complete for parallel access to np.  Information Processing Letters, 65(3):151–156, 1998.
  * [12] Ademir Hujdurović, Martin Milanič, and Bernard Ries.  Graphs vertex-partitionable into strong cliques.  Discrete Mathematics, 341(5):1392–1405, 2018.
  * [13] S. Klein, C. P. de Mello, and A. Morgana.  Recognizing well covered graphs of families with special $p_{4}$-components.  Graphs and Combinatorics, 29(3):553–567, May 2013.
  * [14] Vadim E Levit and Eugen Mandrescu.  W2-graphs and shedding vertices.  Electronic Notes in Discrete Mathematics, 61:797–803, 2017.
  * [15] Vadim E Levit and David Tankus.  Recognizing $\mathbf{W_{2}}$ graphs.  arXiv preprint arXiv:2306.17272, 2023.
  * [16] Christos H Papadimitriou and Mihalis Yannakakis.  The complexity of facets (and some facets of complexity).  In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 255–260, 1982.
  * [17] Michael D. Plummer.  Some covering concepts in graphs.  Journal of Combinatorial Theory, 8(1):91–98, 1970.
  * [18] Michael D. Plummer.  Well-covered graphs: A survey.  Quaestiones Mathematicae, 16(3):253–287, 1993.
  * [19] Erich Prisner, Jerzy Topp, and Preben Dahl Vestergaard.  Well covered simplicial, chordal, and circular arc graphs.  Journal of Graph Theory, 21(2):113–119, 1996.
  * [20] G Ravindra.  Well-covered graphs.  J. Combin. Inform. System Sci, 2(1):20–21, 1977.
  * [21] Tobias Riege and Jörg Rothe.  Completeness in the boolean hierarchy: Exact-four-colorability, minimal graph uncolorability, and exact domatic number problems-a survey.  J. Univers. Comput. Sci., 12(5):551–578, 2006.
  * [22] Ramesh S. Sankaranarayana and Lorna K. Stewart.  Complexity results for well-covered graphs.  Networks, 22(3):247–262, 1992.
  * [23] Holger Spakowski and Jörg Vogel.  $\theta_{2}^{p}$-completeness: A classical approach for new results.  In FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science: 20th Conference New Delhi, India, December 13–15, 2000 Proceedings 20, pages 348–360. Springer, 2000.
  * [24] Jo Ann Wade Staples.  On some subclasses of well-covered graphs. Vanderbilt University, 1975.
  * [25] David Tankus and Michael Tarsi.  Well-covered claw-free graphs.  Journal of Combinatorial Theory, Series B, 66(2):293–302, 1996.
  * [26] Klaus W Wagner.  More complicated questions about maxima and minima, and some closures of np.  Theoretical Computer Science, 51(1-2):53–80, 1987.
  * [27] Klaus W Wagner.  Bounded query classes.  SIAM Journal on Computing, 19(5):833–846, 1990.