O problema probe particionado split bem-coberto é polinomial - Alves, S. R.; Couto, F.; Faria, L.; Klein, S.; Souza, U. dos S. (Anais do Encontro de Teoria da Computação (ETC); 2018: Anais do III Encontro de Teoria da Computação, 2018)
Um grafo G = (V,E) é bem-coberto se cada conjunto independente maximal de G é máximo. Um grafo G = (V,E) é split se existe uma partição V = (S,K), onde S é um conjunto independente e K é uma clique. Um grafo split bem-coberto é, ao mesmo tempo, split e bem-coberto. Dada uma classe C de grafos, um grafo G = (V,E) é C−probe se existe uma partição para V = (N,P) em probes P e não-probes N, onde N é um conjunto independente e novas arestas podem ser adicionadas entre não-probes de maneira que o grafo resultante permaneça na classe de grafos C. Dizemos que (N,P) é uma C probe partição para G. O problema C−PROBE PARTICIONADO consiste de um grafo de entrada G e uma partição probe V = (N,P) e a questão: (N,P) é uma C−partição probe? Neste artigo, consideramos C como a classe dos grafos split bem-cobertos, e provamos que o problema C−PROBE PARTICIONADO pertence à classe de problemas polinomiais P.