2024/04/11 by Carl Feghali, Feghali, Carl, Malory Marin +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2404.07853
openalex publication_date 2024/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 - Wk if for any k pairwise disjoint independent vertex sets A1, …, Ak in G, there exist k pairwise disjoint maximum independent sets S1, …,Sk in G such that Ai ⊆ Si for i ∈ [k]. - Es 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 W1 graphs or, equivalently, well-covered graphs is coNP-complete. We extend this result by showing that recognizing \mathbfWk+1 graphs in either Wk or Es 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 \mathbfEs+1 graphs is Θ2p-complete even in Es graphs, where Θ2p = PNP[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 Wk and Es graphs which, in particular, simplifies and generalizes a result of Dettlaff, Henning and Topp (2023).