Beyond recognizing well-covered graphs
<|reference_start|>Beyond recognizing well-covered graphs: 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\'atal 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\'e, 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).<|reference_end|>
@article{feghali2024beyond,
    title={Beyond recognizing well-covered graphs},
    author={Carl Feghali, Malory Marin and R'emi Watrigant},
    journal={arXiv preprint arXiv:2404.07853},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.07853},
    primaryClass={math.CO cs.DM}
}