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

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}$$ .