The (k,ℓ) unpartitioned probe problem NP-complete versus polynomial dichotomy

• We prove the full complexity dichotomy into NP-complete and polynomial for (k,ℓ)(k,ℓ)unpartitioned probe problems.
• The established full complexity dichotomy answers negatively the SPGC conjecture of Le and Ridder, published in WG 2007.
• The established full complexity dichotomy answers a question of Chang, Hung and Rossmanith, published in DAM 2013.

A graph G=(V,E)G=(V,E) is CCprobe if V can be partitioned into two sets, probes P and non-probes N, where N   is independent and new edges may be added between non-probes such that the resulting graph is in the graph class CC. We say that (N,P)(N,P) is a CCprobe partition for G  . The CCunpartitioned probe problem consists of an input graph G and the question: Is G   a CC probe graph? A (k,ℓ)(k,ℓ)-partition of a graph G is a partition of its vertex set into at most k independent sets and ℓ   cliques. A graph is (k,ℓ)(k,ℓ) if it has a (k,ℓ)(k,ℓ)-partition. We prove the full complexity dichotomy into NP-complete and polynomial for (k,ℓ)(k,ℓ)unpartitioned probe problems: they are NP-complete if k+ℓ≥3k+ℓ≥3, and polynomial otherwise. This gives the first examples of graph classes CC that can be recognized in polynomial time but whose probe graph classes are NP-complete.