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}\).