On the probe problem for (r,ℓ)-well-coveredness: Algorithms and complexity.

• C -probe graphs are graphs having stable sets N for which edges can be added to obtain a supergraph in C. • A graph G is an (r , ℓ) -graph if V (G) can be partitioned into r independent sets and ℓ cliques. • A graph G is well-covered if every maximal independent set is also maximum. • This paper studies the complexity of recognizing probe graphs for the class of (r , ℓ) -well-covered graphs. Let C be a class of graphs. A graph G = (V , E) is C -probe if V (G) can be partitioned into two sets: non-probes N and probes P , where N is an independent set and new edges may be added between some non-probe vertices such that the resulting graph is in the class C. In this case, we say that (N , P) is a C - probe partition of G. In the Unpartitioned Probe problem for a graph class C we are given a graph G and asked whether G has a C -probe partition, i.e., such a problem consist of recognizing the class of C -probe graphs. A graph G = (V , E) is an (r , ℓ) -graph when V can be partitioned into (S 1 , S 2 , ... , S r , K 1 , K 2 , ... , K ℓ) such that S 1 , S 2 , ... , S r are independent sets, and K 1 , K 2 , ... , K ℓ are cliques. A graph G is well-covered if every maximal independent set is also maximum, and it is (r , ℓ) -well-covered if it is well-covered as well as an (r , ℓ) -graph. In this paper, we study the complexity of the Unpartitioned Probe problem for the class of (r , ℓ) -well-covered graphs. We classify all but the (2 , 0) and (1 , 2) cases. [ABSTRACT FROM AUTHOR]