On the (Parameterized) Complexity of Recognizing Well-Covered $(r,\ell )$-graphs

Abstract

An $(r, \ell )$-partition of a graph G is a partition of its vertex set into r independent sets and $\ell$ cliques. A graph is $(r, \ell )$ if it admits an $(r, \ell )$-partition. A graph is well-covered if every maximal independent set is also maximum. A graph is $(r,\ell )$-well-covered if it is both $(r,\ell )$ and well-covered. In this paper we consider two different decision problems. In the $(r,\ell )$-Well-Covered Graph problem ($(r,\ell )$ wcg for short), we are given a graph G, and the question is whether G is an $(r,\ell )$-well-covered graph. In the Well-Covered $(r,\ell )$-Graph problem (wc $(r,\ell )$ g for short), we are given an $(r,\ell )$-graph G together with an $(r,\ell )$-partition of V(G) into r independent sets and $\ell$ cliques, and the question is whether G is well-covered. We classify most of these problems into P, coNP-complete, NP-complete, NP-hard, or coNP-hard. Only the cases wc(r, 0)g for $r\ge 3$ remain open. In addition, we consider the parameterized complexity of these problems for several choices of parameters, such as the size $\alpha$ of a maximum independent set of the input graph, its neighborhood diversity, or the number $\ell$ of cliques in an $(r, \ell )$-partition. In particular, we show that the parameterized problem of deciding whether a general graph is well-covered parameterized by $\alpha$ can be reduced to the wc $(0,\ell )$ g problem parameterized by $\ell$, and we prove that this latter problem is in XP but does not admit polynomial kernels unless $\mathsf{coNP} \subseteq \mathsf{NP} / \mathsf{poly}$.

This work was supported by FAPERJ, CNPq, CAPES Brazilian Research Agencies and EPSRC (EP/K025090/1).

1 Introduction

An $(r, \ell )$-partition of a graph $G=(V,E)$ is a partition of V into r independent sets $S^1,\ldots ,$ $S^r$ and $\ell$ cliques $K^1,\ldots ,$ $K^{\ell }$. For convenience, we allow these sets to be empty. A graph is $(r, \ell )$ if it admits an $(r, \ell )$-partition. The $\mathsf{P}$ versus $\mathsf{NP}$-complete dichotomy for recognizing $(r, \ell )$-graphs is well known [2]: the problem is in $\mathsf{P}$ if $\max \{r, \ell \} \le 2$, and $\mathsf{NP}$-complete otherwise. The class of $(r,\ell )$-graphs and its subclasses have been extensively studied in the literature. For instance, list partitions of $(r,\ell )$-graphs were studied by Feder et al. [11]. In another paper, Feder et al. [12] proved that recognizing graphs that are both chordal and $(r,\ell )$ is in $\mathsf{P}$.

Well-covered graphs were first introduced by Plummer [20] 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 every maximal independent set has the same cardinality. 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 [3] and independently by Sankaranarayana and Stewart [22], but is in $\mathsf{P}$ when the input graph is known to be claw-free [18, 24].

Motivated by this latter example and by the relevance of $(r, \ell )$-graphs, in this paper we are interested in recognizing graphs that are both $(r, \ell )$ and well-covered. We note that similar restrictions have been considered in the literature. For instance, Kolay et al. [16] recently considered the problem of removing few vertices from a perfect graph so that it additionally becomes $(r, \ell )$.

Let $r, \ell \ge 0$ be two fixed integers. A graph is $(r, \ell )$ -well-covered if it is both $(r, \ell )$ and well-covered. More precisely, in this paper we focus on the following two decision problems.

We establish an almost complete characterization of the complexity of the $(r,\ell )$ wcg and wc $(r,\ell )$ g problems. Our results are shown in the following tables, where r (resp. $\ell$) corresponds to the rows (resp. columns) of the tables, and where $\mathsf{coNPc}$ stands for coNP-complete, $\mathsf{NPh}$ stands for NP-hard, $\mathsf{NPc}$ stands for NP-complete, and $\mathsf{(co)NPh}$ stands for both NP-hard and coNP-hard. The symbol ‘?’ denotes that the complexity of the corresponding problem is open.

We note the following simple facts that we will use to fill the above tables:

Fact 1

If $(r,\ell )$ wcg is in P, then wc $(r,\ell )$ g is in P.

Fact 2

If wc $(r,\ell )$ g is coNP-hard, then $(r,\ell )$ wcg is coNP-hard.

Note that wc $(r,\ell )$ 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,\ell )$ wcg we have the following facts, which are easy to verify:

Fact 3

For any pair of integers $(r,\ell )$ such that the problem of recognizing an $(r,\ell )$-graph is in P, the $(r,\ell )$ wcg problem is in coNP.

Fact 4

For any pair of integers $(r,\ell )$ such that the wc $(r,\ell )$ g problem is in P, the $(r,\ell )$ wcg problem is in NP.

In this paper we prove that (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), and (1, 2)wcg can be solved in polynomial time, which by Fact 1 yields that wc(0, 1), (1, 0), (0, 2),(1, 1), (2, 0), and (1, 2)g can also be solved in polynomial time. On the other hand, we prove that wc(2, 1)g is coNP-complete, which by Facts 2 and 3 will yield that (2, 1)wcg is also coNP-complete. Furthermore, we also prove that wc $(0,\ell )$ g and wc $(1,\ell )$ g are polynomial, and that (0, 3), (3, 0), and (1, 3)wcg 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,\ell )$ g (resp. $(r,\ell )$ wcg) to wc $(r+1,\ell )$ g (resp. $(r+1,\ell )$ wcg), and wc $(r,\ell +1)$ g (resp. $(r,\ell +1)$ wcg).

Together, these results correspond to those shown in the above tables. Note that the only remaining open cases are wc(r, 0)g for $r\ge 3$. As an 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 [10, 21, 26]. So far, only partial characterizations exist [14, 15].

In addition, we consider the parameterized complexity of these problems for several choices of the parameters, such as the size $\alpha$ of a maximum independent set of the input graph, its neighborhood diversity, or the number $\ell$ of cliques in an $(r, \ell )$-partition. We obtain several positive and negative results. In particular, we show that the parameterized problem of deciding whether a general graph is well-covered parameterized by $\alpha$ can be reduced to the wc $(0,\ell )$ g problem parameterized by $\ell$, and we prove that this latter problem is in XP but does not admit polynomial kernels unless $\mathsf{coNP} \subseteq \mathsf{NP} / \mathsf{poly}$. (For an introduction to the field of Parameterized Complexity, see [4, 7, 13, 19].)

The rest of this paper is organized as follows. In Sect. 2 we prove our results concerning the classical complexity of both problems, and in Sect. 3 we focus on their parameterized complexity.

We use standard graph-theoretic notation, and we refer the reader to [6] for any undefined notation. Throughout the paper, we let n denote the number of vertices in the input graph for the problem under consideration.

2 Classical Complexity of the Problems

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

Theorem 1

Let $r,\ell \ge 0$ be two fixed integers.

• (i) If wc $(r,\ell )$ g is coNP-complete then wc $(r+1,\ell )$ g and wc $(r,\ell +1)$ g are coNP-complete.

• (ii) If $(r,\ell )$ wcg is NP-hard (resp. coNP-hard) then $(r,\ell +1)$ wcg is NP-hard (resp. coNP-hard).

• (iii) Suppose that $r \ge 1$. If $(r,\ell )$ wcg is NP-hard (resp. coNP-hard) then $(r+1,\ell )$ wcg is NP-hard (resp. coNP-hard).

Proof

(i) This follows immediately from the fact that every $(r,\ell )$-graph is also an $(r+1,\ell )$-graph and an $(r,\ell +1)$-graph.

(ii) Let G be an instance of $(r,\ell )$ wcg. Let H be the disjoint union of G and a clique Z with $V(Z)=\{z_1,\ldots ,z_{r+1}\}$. Clearly G is well-covered if and only if H is well-covered. If G is an $(r,\ell )$-graph then H is an $(r,\ell +1)$-graph. Suppose H is an $(r,\ell +1)$-graph, with a partition into r independent sets $S^1,\ldots ,S^r$ and $\ell +1$ cliques $K^1,\ldots ,K^{\ell +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^{\ell +1}$. Then $K^{\ell +1}$ cannot contain any vertex outside of V(Z), so we may assume that $K^{\ell +1}$ contains all vertices of Z. Now $S^1,\ldots ,S^r,K^1,\ldots ,K^{\ell }$ is an $(r,\ell )$-partition of G, so G is an $(r,\ell )$-graph. Hence, H is a Yes-instance of $(r,\ell +1)$ wcg if and only if G is a Yes-instance of $(r,\ell )$ wcg.

(iii) Let G be an instance of $(r,\ell )$ wcg. Let $G'$ be the graph obtained by adding $\ell +1$ isolated vertices to G. (This guarantees that every maximal independent set in $G'$ contains at least $\ell +1$ vertices.) Since $r\ge 1$, it follows that $G'$ is an $(r,\ell )$-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 \ge \ell +1$. Let H be the join of $G'$ and a set of p independent vertices $Z=\{z_1,\ldots ,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,\ell )$-graph then H is an $(r+1,\ell )$-graph. Suppose H is an $(r+1,\ell )$-graph, with a partition into $r+1$ independent sets $S^1,\ldots ,S^{r+1}$ and $\ell$ cliques $K^1,\ldots ,K^{\ell }$. 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,\ldots ,S^r,K^1,\ldots ,K^{\ell }$ is an $(r,\ell )$-partition of G, so G is an $(r,\ell )$-graph. Thus H is a Yes-instance of $(r+1,\ell )$ wcg if and only if G is a Yes-instance of $(r,\ell )$ wcg.    $\square$

2.1 Polynomial Cases for wc $(r,\ell )$ g

Theorem 2

wc $(0,\ell )$ g and wc $(1,\ell )$ g are in P for every integer $\ell \ge 0$.

Proof

It is enough to prove that wc $(1,\ell )$ g is polynomial. Let $V=(S,K^1,K^2,$ $K^3,\ldots ,$ $K^{\ell })$ be a $(1,\ell )$-partition for G. Then each maximal independent set I of G admits a partition $I=(I_K,S\setminus N_S(I_K))$, where $I_K$ is an independent set of $K^1\cup K^2\cup K^3\cup \cdots \cup$ $K^{\ell }$.

Observe that there are at most $O(n^{\ell })$ choices for an independent set $I_K$ of $K^1\cup K^2\cup K^3\cup \cdots \cup$ $K^{\ell }$, which can be listed in time $O(n^{\ell })$, since $\ell$ is constant and $(K^1,K^2,$ $K^3,\ldots ,$ $K^{\ell })$ is given. For each of them, we consider the independent set $I=I_K\cup (S\setminus N_S(I_K))$. If I is not maximal (which may happen if a vertex in $(K^1\cup K^2\cup K^3\cup \cdots \cup$ $K^{\ell })\setminus I_K$ has no neighbors in I), we discard this choice of $I_K$. Hence, we have a polynomial number $O(n^{\ell })$ of maximal independent sets to check in order to decide whether G is a well-covered graph.    $\square$

2.2 Polynomial Cases for $(r,\ell )$ wcg

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 1

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.

Theorem 3

(0, 2)wcg can be solved in polynomial time.

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 known in the literature as split graphs.

Lemma 1

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\in K$, then $|N_{S}(x)|\le 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\in I\cap K$. Suppose for contradiction that $|N_{S}(x)|\ge 2$, and let $y,z\in N_{S}(x)$. Since $y,z\in S$, $N_G(y), N_G(z)\subseteq K$. Since K is a clique, vertex x is the only vertex of I in K. Hence, we have that $N_G(y)\cap (I\setminus \{x\})=$ $N_G(z)\cap (I\setminus \{x\})=\emptyset$. Therefore $I'=(I\setminus \{x\})\cup \{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)|\le 1$.    $\square$

Lemma 2

A graph G is a (1, 1)-well-covered graph if and only if it admits a (1, 1)-partition $V=(S,K)$ such that either for every $x\in K$, $|N_{S}(x)|=0$, or for every $x\in K$, $|N_{S}(x)|=1$.

Proof

Let G be a (1, 1)-well-covered graph. By Lemma 1 we have that, given a vertex $x\in K$, either $|N_{S}(x)|=0$ or $|N_{S}(x)|=1$. Suppose for contradiction that there are two vertices $x,y\in K$ such that $|N_{S}(x)|=0$ and $|N_{S}(y)|=1$. 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\setminus \{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\in K$, $|N_{S}(x)|=0$, or for every $x\in 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\in K$, $|N_{S}(x)|=0$, or for every $x\in K$, $|N_{S}(x)|=1$. If $K=\emptyset$, then G is (1, 0) and then G is well-covered. Hence we assume $K\ne \emptyset$. If for every $x\in K$, $|N_{S}(x)|=0$, then every maximal independent set consists of all the vertices of S and exactly one vertex $v \in K$. If for every $x\in K$, $|N_{S}(x)|=1$, then every maximal independent set is either $I=S$, or $I=\{x\}\cup (S\setminus N_S(x))$ for some $x \in K$. Since $|N_S(x)|=1$ we have $|I|=1+|S|-1=|S|$, and hence G is a (1, 1)-well-covered graph.    $\square$

Lemma 3

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$, with degree sequence either $(k,k,k,\ldots ,k,$ $i_1,i_2,\ldots ,i_s,$ $0,0,0,\ldots ,0)$ with $\sum _{j=1}^s (i_j)= k$, or $(k-1,k-1,k-1,\ldots ,k-1,$ $0,0,0,\ldots ,0)$, where the subsequences $k, \ldots , k$ (resp. $k-1, \ldots , 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\ge 0$. If $k=0$, then the degree sequence is $(0,0,0,\ldots ,0)$. If $k\ge 1$, then by Lemma 2 either for every $x\in K$, $|N_{S}(x)|=0$, or for every $x\in K$, $|N_{S}(x)|=1$. If for every $x\in K$, $|N_{S}(x)|=0$, then the degree sequence of G is $(k-1,k-1,k-1,\ldots ,k-1,$ $0,0,0,\ldots ,0)$. If for every $x\in K$, $|N_{S}(x)|=1$, then the degree sequence of G is $(k,k,k,\ldots ,k,$ $i_1,i_2,\ldots ,i_s,$ $0,0,0,\ldots ,0)$, with $\sum _{j=1}^s (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,\ldots ,k,$ $i_1,i_2,\ldots ,i_s,$ $0,0,0,\ldots ,0)$, or $(k-1,k-1,k-1,\ldots ,k-1,$ $0,0,0,\ldots ,0)$, such that $\sum _{j=1}^s (i_j)= k$. If the degree sequence of G is $(k,k,k,\ldots ,k,$ $i_1,i_2,\ldots ,i_s,$ $0,0,0,\ldots ,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,\ldots ,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,\ldots ,k-1,$ $0,0,0,\ldots ,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 2 we have that G is a well-covered graph.    $\square$

Corollary 2

(1, 1)wcg can be solved in polynomial time.

Ravindra [21] gave the following characterization of (2, 0)-well-covered graphs.

Theorem 4

(Ravindra [21]). Let G be a connected graph. G is a (2, 0)-well-covered graph if and only if G contains a perfect matching F such that for every edge $e = uv$ in F, $G[N(u)\cup N(v)]$ is a complete bipartite graph.

We now prove that Theorem 4 leads to a polynomial-time algorithm.

Theorem 5

(2, 0)wcg can be solved in polynomial time.

Proof

Assume that G is connnected and consider the weighted graph $(G,\omega )$ with $\omega :E(G)\rightarrow \{0,1\}$ satisfying $\omega (uv)=1$, if $G[N(u)\cup N(v)]$ is a complete bipartite graph, and 0 otherwise. By Theorem 4, G is well-covered if and only if $(G,\omega )$ has a weighted perfect matching with weight at least n / 2, and this can be decided in polynomial time [9].    $\square$

Theorem 6

(1, 2)wcg can be solved in polynomial time.

Proof

We can find a (1, 2)-partition of a graph G (if any) in polynomial time [2]. After that, we use the algorithm for wc $(1,\ell )$ g given by Theorem 2.    $\square$

2.3 coNP-complete Cases for wc $(r,\ell )$ g

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

Fig. 1.

Chvatal and Slater’s [3] Well-Covered Graph instance $G=(V,E)$ obtained from the satisfiable 3-sat instance $I=(U,C)= \left( \{u_1,u_2,u_3\},\{(u_1,u_2,u_3),(u_1,u_2,\overline{u}_3),\right.$ $\left. (\overline{u}_1,\overline{u}_2,\overline{u}_3)\}\right)$, where $\{c_1,c_2,\ldots ,c_m\}$ 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,\overline{u}_1,\overline{u}_2,\overline{u}_3\}$) and there is a maximal independent set of size n (e.g. $\{{u}_1,{u}_2,\overline{u}_3\}$). Note also that G is a (2, 1)-graph with (2, 1)-partition $V=(\{u_1,u_2,\ldots ,u_n\}, \{\overline{u}_1,\overline{u}_2,\ldots ,\overline{u}_n\}, \{c_1,c_2,\ldots ,c_m\}\left. \right)$.

Indeed, Chvátal and Slater [3] take a 3-sat instance $I=(U,C)=(\{u_1,u_2,u_3,\ldots ,u_n\},$ $\{c_1,c_2,c_3,\ldots ,c_m\}),$ and construct a Well-Covered Graph instance $G=(V,E)=$ $\left( \right. \{u_1,u_2,u_3,$ $\ldots , u_n,\overline{u}_1,\overline{u}_2,\overline{u}_3,\ldots , \overline{u}_n,$ $c_1,c_2,c_3,\ldots ,c_m\},$ $\{xc_j:$ $x{ \text{ occurs } \text{ in } }$ $c_j\}\ \cup$ $\{u_i\overline{u}_i : 1 \le i \le n\}\ \cup$ $\{c_ic_j:1\le i<j\le m\}\left. \right)$. Note that $\{c_ic_j:1\le i<j\le m\}$ is a clique, and that $\{u_1,u_2,u_3,$ $\ldots , u_n\},$ and $\{\overline{u}_1,\overline{u}_2,\overline{u}_3,\ldots , \overline{u}_n\}$ are independent sets. Hence, G is a (2, 1)-graph. An illustration of this construction can be found in Fig. 1. This discussion can be summarized as follows.

Theorem 7

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

As (2, 1)-graphs can be recognized in polynomial time [2], we have the following corollary.

Corollary 3

(2, 1)wcg is coNP-complete.

2.4 NP-hard Cases for $(r,\ell )$ wcg

Now we prove that (0, 3) wcg is NP-complete. For this purpose, we slightly modify an NP-completeness proof of Stockmeyer [23].

Stockmeyer’s [23] NP-completeness proof of 3-coloring considers a 3-sat instance $I=(U,C)= \left( \right. \{u_1,u_2,u_3,\ldots , u_n\}, \{c_1,c_2,c_3,\ldots , c_m\}\left. \right)$, and constructs a 3-coloring instance $G=(V,E)= \left( \{u_1,u_2,u_3,\ldots ,u_n,\overline{u}_1,\overline{u}_2,\overline{u}_3,\ldots ,\right.$ $\left. \overline{u}_n\}\cup \{v_1[j],v_2[j],v_3[j],v_4[j],v_5[j],v_6[j]: j\in \{1,2,3,\ldots ,m\}\}\cup \{t_1,t_2\},\{u_i\overline{u}_i:\right.$ $\left. i\in \{1,2,3,\ldots ,n\}\}\cup \{v_1[j]v_2[j],v_2[j]v_4[j],v_4[j]v_1[j],v_4[j]v_5[j],v_5[j]v_6[j],v_6[j]v_3\right.$ $\left. [j],v_3[j]v_5[j]: j\in \{1,2,3,\ldots , m\}\}\cup \{v_1[j]x, v_2[j]y, v_3[j]z: c_j=(x,y,z)\}\cup \{t_1\right.$ $\left. u_i,t_1\bar{u}_i : i\in \{1,2,3,\ldots , n\}\}\cup \{t_2v_6[j]:j\in \{1,2,3,\ldots , m\}\}\right)$; see Fig. 2(a).

Theorem 8

(0, 3)wcg is NP-complete.

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)wcg is in $\mathsf{NP}$.

Let $I=(U,C)$ be a 3-sat instance. We produce, in polynomial time in the size of I, a (0, 3)wcg 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 [23] 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 Fig. 2(b). Finally, we define $H=\overline{G'}$ as the complement of $G'$. Note that, by [23], 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.

Fig. 2.

(a) Stockmeyer’s [23] 3-coloring instance G obtained from the 3-sat instance $I=(U,C)= \left( \{u_1,u_2,u_3\},\{(u_1,u_2,u_3),(u_1,u_2,\overline{u}_3), (\overline{u}_1,\overline{u}_2,\overline{u}_3)\}\right)$. (b) The graph $G'$ obtained from G by adding a vertex $x_{uv}$ with $N_{G'}(x_{uv})=\{u,v\}$ for every edge uv of G not belonging to a triangle.

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 [23], I is satisfiable.    $\square$

We next prove that (3, 0)wcg is NP-hard. For this, we again use the proof of Stockmeyer [23], together with the following theorem.

Theorem 9

(Topp and Volkmann [25]). Let $G=(V,E)$ be an n-vertex graph, $V=\{v_1,v_2,v_3, \ldots ,v_n\}$, and let H be obtained from G such that $V(H)=V\cup \{u_1,u_2,u_3, \ldots ,u_n\}$ and $E(H)=E\cup \{v_iu_i: i\in \{1,2,3,\ldots , 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 \cap V$. Let $\mathcal{{U}}\subseteq \{1,2,3,\ldots ,n\}$ be the set of indices i such that $v_i\in I$. Since I is maximal, the set $\{u_i: i\in \{1,2,3,\ldots ,n\}\setminus \mathcal {U}\}$ must be contained in I, so $|I|=n$.    $\square$

Theorem 10

(3, 0)wcg 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 [23] NP-completeness proof for 3-coloring; and let H be the graph obtained from G by the transformation described in Theorem 9. 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 [23] we have that G is 3-colorable. Since a vertex $v \in V(H)\setminus 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 Theorem 9, 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 [23], I is satisfiable.    $\square$

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

Theorem 11

(1, 3)wcg 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)wcg is in $\mathsf{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)wcg 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 [23] obtained from I (see Fig. 2(a)), and let H be the graph obtained from $\overline{G}$ (the complement of the graph G) by adding one pendant vertex $p_v$ for each vertex v of $\overline{G}$. Note that $V(H)=V(G)\cup \{p_v: v\in V(G)\}$, $E(H)=E(\overline{G})\cup \{p_vv: v\in V(G)\}$, and $N_{H}(p_v)=\{v\}$.

First suppose that I is satisfiable. Then by [23], G is a (3, 0)-graph, and $\overline{G}$ is a (0, 3)-graph with partition into cliques $V(\overline{G})=(K_{\overline{G}}^1,K_{\overline{G}}^2,K_{\overline{G}}^3)$. Thus it follows that $(S=\{p_v: v\in V(G)\},K_{\overline{G}}^1,K_{\overline{G}}^2,K_{\overline{G}}^3)$ is a (1, 3)-partition of V(H). In addition, from Theorem 9 and by the construction of H, H is a well-covered 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\in V(H)\setminus V(G)$ belongs to $K^i, i\in \{1,2,3\}$. Indeed, suppose for contradiction that $p_v\in K^i$ for some $i\in \{1,2,3\}$. Then, $K^i \subseteq \{p_v, v\}$. Hence, $H\setminus K^i$ is a (1, 2)-graph and $G\setminus \{v\}$ is an induced subgraph of a (2, 1)-graph. But by construction of G, $G\setminus \{v\}$ (for any $v\in 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\in V(G)\} \subseteq S$, and since $\{p_v: v\in V(G)\}$ is a dominating set of H, $S=\{p_v: v\in V(G)\}$. Thus, $\overline{G}$ is a (0, 3)-graph with partition $V(\overline{G})=(K^1,K^2,K^3)$, and therefore G is a (3, 0)-graph, i.e., a 3-colorable graph. Therefore, by [23], I is satisfiable.    $\square$

Corollary 4

If $(r\ge 3$ and $\ell =0)$ then $(r,\ell )$ wcg is NP-hard. If $(r\in \{0,1\}$ and $\ell \ge 3)$ then $(r,\ell )$ wcg is NP-complete.

Proof

$(r,\ell )$ wcg is NP-hard in all of these cases by combining Theorems 1, 8, 10 and 11. For $(r\in \{0,1\}$ and $\ell \ge 3)$, the Well-Covered Graph problem can be solved in polynomial time on $(r,\ell )$-graphs, so by Fact 4 $(r,\ell )$ wcg is in $\mathsf{NP}$.    $\square$

3 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,\ell )$-graph. Henceforth we let $\alpha$ denote the size of a maximum independent set in the input graph G for the problem under consideration. That is, G is well-covered if and only if any maximal independent set of G has size $\alpha$.

Lemma 4

The wc $(r,\ell )$ g problem can be solved in time $2^{r \cdot \alpha } \cdot n^{O(\ell )}$. In particular, it is FPT when $\ell$ is fixed and $r, \alpha$ are parameters.

Proof

Note that each of the r independent sets $S^1, \ldots , S^r$ of the given partition of V(G) must have size at most $\alpha$. On the other hand, any maximal independent set of G contains at most one vertex in each of the $\ell$ cliques. The algorithm exhaustively constructs all maximal independent sets of G as follows: we start by guessing a subset of $\bigcup _{i=1}^r 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 $\alpha$ with $\max _{1 \le i \le r}|S^i|$, which yields a stronger result.    $\square$

The following lemma motivates the study of the Well-Covered $(0,\ell )$-Graph problem, as it shows that the Well-Covered Graph problem (on general graphs) parameterized by $\alpha$ can be reduced to the wc $(0,\ell )$ g problem parameterized by $\ell$.

Lemma 5

The Well-Covered Graph problem parameterized by $\alpha$, with $\alpha$ given as part of the input, can be fpt-reduced to the wc $(0,\ell )$ g problem parameterized by $\ell$.

Proof

Given a general graph G and $\alpha$ (recall that $\alpha$ is the size of a maximum independent set in G), we construct a $(0,\alpha )$-graph $G'$ as follows. For every vertex $v \in V(G)$, we add to $G'$ a clique $K_v$ on $\alpha$ vertices, which are denoted $v_1, \ldots , v_{\alpha }$. For every two vertices $u,v \in V(G)$ and every integer i, $1 \le i \le \alpha$, we add to $G'$ the edge $u_i v_i$. Finally, for every edge $uv \in E(G)$, we add to $G'$ a complete bipartite subgraph between $V(K_u)$ and $V(K_v)$. It is clear from the construction that $G'$ is a $(0,\alpha )$-graph, and that G is well-covered if and only if $G'$ is well-covered.    $\square$

Lemma 6

The wc $(1,\ell )$ g problem can be solved in time $n^{O(\ell )}$. In other words, it is in XP when parameterized by $\ell$.

Proof

Let $V(G) = S^1 \cup K^1 \cup \cdots \cup K^{\ell }$. The algorithm chooses at most one vertex in each clique, and adds them to a potential independent set $I_k \subseteq V(G)$. If $I_k$ is not independent, then we discard this set. Otherwise, we set $I=I_k \cup (S^1 \setminus N_{S^1}(I_k))$. This clearly defines an independent set of G, which may be maximal or not, but any maximal independent set of G can be constructed in this way. The number of sets considered by this procedure is $n^{O(\ell )}$. Finally, it just remains to check whether all the constructed independent sets, after discarding those that are not maximal, have the same size.    $\square$

Note that Lemma 6 implies that the Well-Covered $(0,\ell )$-Graph problem can also be solved in time $n^{O(\ell )}$. This observation raises the following question: are the Well-Covered $(0,\ell )$-Graph and Well-Covered $(1,\ell )$-Graph problems FPT when parameterized by $\ell$? Even if we still do not know the answer to this question, in the following them we prove that, in particular, the Well-Covered $(0,\ell )$-Graph and Well-Covered $(1,\ell )$-Graph problems are unlikely to admit polynomial kernels when parameterized by $\ell$. We first need a definition introduced by Bodlaender et al. [1].

Definition 1

(and-composition [1]). Let ${\mathcal Q} \subseteq \varSigma ^* \times \mathbb {N}$ be a parameterized problem. An and-composition for ${\mathcal Q}$ is an algorithm that, given t instances $(x_1,k),$ $\ldots , (x_t, k) \in \varSigma ^* \times \mathbb {N}$ of ${\mathcal Q}$, takes time polynomial in $\sum _{i=1}^{t}|x_i| + k$ and outputs an instance $(y,k') \in \varSigma ^* \times \mathbb {N}$ such that:

• (i) The parameter value $k'$ is polynomially bounded by k.

• (ii) The instance $(y,k')$ is Yes for ${\mathcal Q}$ if and only if all instances $(x_i,k)$ are Yes for ${\mathcal Q}$.

The following result was formulated as the ‘AND-conjecture’ by Bodlaender et al. [1], and it was finally proved by Drucker [8] (see [5] for a simplified proof).

Theorem 12

(Drucker [8]). If a parameterized problem admits a polynomial kernel and an and-composition, then $\mathsf{coNP} \subseteq \mathsf{NP} / \mathsf{poly}$.

We are ready the state our result.

Theorem 13

For any fixed integer $r \ge 0$, the wc $(r,\ell )$ g problem does not admit polynomial kernels when parameterized by $\ell$, unless $\mathsf{coNP} \subseteq \mathsf{NP} / \mathsf{poly}$.

Proof

By Theorem 12, to prove the result it is enough to present an and-composition for the Well-Covered $(0,\ell )$-Graph problem, which implies the result for the Well-Covered $(r,\ell )$-Graph for any $r \ge 0$, as any $(0,\ell )$-graph is also an $(r,\ell )$-graph for $r \ge 0$. Let $G_1, \ldots , G_t$ be the given $(0,\ell )$-graphs. For every $1 \le i \le t$, take arbitrarily a maximal independent set $S_i$ of $G_i$, and let $G_i'$ be the graph obtained from $G_i$ by adding $\ell - |S_i|$ isolated vertices. As any independent set in $G_i$ can have at most one vertex in each clique $K^j$, it follows that $|S_i| \le \ell$, and thus $G_i'$ is well-defined. Note also that for every $1 \le i \le t$, $G_i'$ is a $(0,2\ell )$-graph (just consider a new clique for each isolated vertex). The following two properties are easy to verify:

• (i) For every $1 \le i \le t$, $G_i'$ is well-covered if and only if $G_i$ is well-covered.

• (ii) For every $1 \le i \le t$, if $G_i'$ is well-covered then every maximal independent set of $G_i'$ has size $\ell$.

We create a graph G by taking the disjoint union of the $G_i$’s and then adding, for every $i,j \in \{1, \ldots ,t\}$, $i \ne j$, all edges between $V(G_i')$ and $V(G_j')$. We set the parameter of G as $\ell ' = 2 \ell$. Since each $G_i'$ is a $(0,2\ell )$-graph, by construction G is also a $(0,2\ell )$-graph. Note that, by construction of G, any independent set of G can intersect only one $G_i$, and therefore, if we let $\mathcal {S}$ (resp. $\mathcal {S}_i$) denote the set of all maximal independent sets of G (resp. $G_i'$), it follows that

$$\begin{aligned} \mathcal {S} = \bigcup \{\mathcal {S}_i : 1 \le i \le t\}. \end{aligned}$$

(1)

We claim that G is well-covered if and only if $G_i$ is well-covered for every $1 \le i \le t$, which will conclude the proof.

Indeed, first suppose that G is well-covered. Then, by Eq. (1), $G_i'$ is well-covered for every $1 \le i \le t$, and by Property (i) this implies that $G_i$ is also well-covered for every $1 \le i \le t$.

Conversely, suppose that $G_i$ is well-covered for every $1 \le i \le t$. Then, by Property (i), $G_i'$ is also well-covered for every $1 \le i \le t$ and, by Property (ii), for every $1 \le i \le t$, any maximal independent set of $G_i'$ has size $\ell$. This implies by Eq. (1) that any maximal independent set of G also has size $\ell$, and therefore G is well-covered, as we wanted to prove.    $\square$

3.1 Taking the Neighborhood Diversity as the Parameter

The vertex cover number is a classical graph parameter that has been widely used as a parameter in the multivariate complexity analysis of problems, including those that are not directly related to the vertex cover number. Neighborhood diversity is another graph parameter, defined by Lampis [17], which captures more precisely than vertex cover number the property that two vertices with the same neighborhood are “equivalent”. This parameter is defined as follows.

Definition 2

The neighborhood diversity $\mathbf{nd}(G)$ of a graph $G=(V,E)$ is the minimum t such that V can be partitioned into t sets $V_1,\ldots ,V_t$ where for every $v\in V(G)$ and every $i\in \{1,\ldots ,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.

Neighborhood diversity is a stronger parameter than vertex cover, in the sense that bounded vertex cover graphs are a subclass of bounded neighborhood diversity graphs. It is known that an optimal neighborhood diversity decomposition of a graph G can be computed in time $O(n^3)$. See [17] for more details.

Lampis [17] showed that: (i) for every graph G we have $\mathbf{nd}(G)\le 2^{vc(G)}+vc(G)$, where vc(G) is the vertex cover number of G; $cw(G)\le \mathbf{nd}(G)+1$, where cw(G) is the clique-width of G; (iii) there exist graphs of constant treewidth and unbounded neighborhood diversity and vice versa; (iv) an optimal neighborhood diversity decomposition of a graph G can be computed in polynomial time.

Lemma 7

The Well-Covered Graph problem is FPT when parameterized by the 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 [17]. Let $t:=\mathbf{nd}(G)$ and let $V_1,\ldots ,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\in S_u$ there exists another maximal independent set $S_v$ such that $S_v = S_u\setminus \{u\} \cup \{v\}$. Hence, we can contract each partition $V_i$ which is an independent set into a single vertex $v_i$ with weight $\tau (v_i)=|S_i|$, and contract each partition $V_i$ which is a clique into a single vertex $v_i$ with weight $\tau (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 $\tau (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 $2^t \cdot n^{O(1)}$ time.    $\square$

Corollary 5

The Well-Covered Graph problem is FPT when parameterized by the vertex cover number $n-\alpha$.