Problemas de Cortes de Arestas Máximos e Mínimos em Grafos

Iniciamos este trabalho mostrando que o problema do Corte Máximo Simples (SIMPLE MAXCUT) em grafos fortemente cordais é NP-completo, o que resolve um problema em aberto da Coluna Johnson [47] . Determinamos em seguida um algoritmo 2/3-aproximativo para este problema em grafos split e resolvemos o problema para a subclasse dos grafos (k,n)-split cheios, determinando exatamente um corte máximo simples. Partimos então para o estudo da complexidade parametrizada do problema: apoiados no problema da determinação do subgrafo balanceado de tamanho máximo em um grafo sinalizado que generaliza o problema do Corte Máximo Simples mostramos que este ultimo problema é tratável por parâmetro fixo em grafos split e grafos (r,l) exibindo um núcleo quadrático em ambos os casos. Obtivemos também núcleo linear para a subclasse dos grafos d*-split. Finalmente consideramos os problemas de cortes máximo e mínimo de arestas em um grafo aresta-colorido, mostramos que ambos são problemas NP-completos mesmo em grafos completos e são tratáveis por parâmetro fixo.