Corte mínimo k mais rápido de um gráfico simples

Consideramos o problema k-CUT (exato, mínimo): dado um gráfico e um inteiro k, delete um conjunto de arestas de peso mínimo de modo que o gráfico restante tenha pelo menos k componentes conectados. Este problema é uma generalização natural do problema de corte mínimo global, onde o objetivo é dividir o gráfico em k=2 partes. Nosso resultado principal é um algoritmo k-CUT (combinatório) em gráficos simples que roda em n (1+o (1)) k para qualquer constante k, melhorando o anteriormente melhor algoritmo de tempo n (2ω/3+o (1)) k de Gupta et al. FOCS'18 e o anteriormente melhor algoritmo combinatório de tempo n^(1.981+o (1)) k de Gupta et al. STOC'19. Para algoritmos combinatórios, este algoritmo é ótimo até fatores o(1), assumindo as recentes conjecturas de dificuldade: mostramos por uma redução direta que o k-CUT em um gráfico simples é tão difícil quanto (k-1)-clique, estabelecendo um limite inferior de n (1-o(1)) k para k-CUT. Isso resolve, até fatores de ordem inferior, a complexidade do k-CUT em um gráfico simples para algoritmos combinatórios.