A graph G = ( V , E ) is C probe 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 C . We say that ( N , P ) is a C probe partition for G. The C unpartitioned probe problem consists of an input graph G and the question: Is G a C probe graph? A ( 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 , ? ) if it has a ( k , ? ) -partition. We prove the full complexity dichotomy into NP-complete and polynomial for ( k , ? ) unpartitioned probe problems: they are NP-complete if k + ? ? 3 , and polynomial otherwise. This gives the first examples of graph classes C that can be recognized in polynomial time but whose probe graph classes are NP-complete. We prove the full complexity dichotomy into NP-complete and polynomial for ( 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.
['Simone Dantas', 'Luerbio Faria', 'Celina M. Herrera de Figueiredo', 'Rafael B. Teixeira']
The (k,ℓ) unpartitioned probe problem NP-complete versus polynomial dichotomy