Solucionadores MaxIS baseados em ramificação recentes melhoram a qualidade da solução através de busca recursiva e ramificação direcionada Hespe D, Lamm S, Schorr C. Ramificação direcionada para o problema do conjunto independente máximo. 2021, mas seu tempo de execução pode crescer rapidamente em grandes grafos de conflito da IoT. Este artigo propõe o KernelGreedyMaxIS, uma estrutura determinística em tempo polinomial para o cálculo escalável de conjuntos independentes. O método combina kernelização leve baseada em grau com inferência gulosa de grau mínimo, separando reduções justificadas localmente da seleção heurística. Este design melhora a reprodutibilidade, evita sementes aleatórias e dados de treinamento e proporciona um comportamento de tempo de execução previsível. A análise teórica prova a correção da redução, viabilidade, terminação determinística e complexidade no pior caso O(n2logn). Experimentos mostram qualidade de solução competitiva com tempo de execução rápido em grafos de referência e do mundo real.
Verma et al. (Mon,) estudaram esta questão.