Fluxos Ramificados Arco-disjuntos em Redes de Capacidade Restrita - Maia, A. Karolinna; Costa, Jonas; Lopes, Raul (Anais do Encontro de Teoria da Computação (ETC), 2018)
Determinar se uma rede possui um fluxo viável é um problema amplamente estudado e que pode ser resolvido em tempo polinomial. Investigamos um tipo específico de fluxo, o fluxo ramificado, que pode ser aplicado na busca por ramificações em digrafos. Consideramos o problema de encontrar múltiplos fluxos ramificados arco-disjuntos em uma rede e estudamos a complexidade deste problema com diferentes capacidades nos arcos. Um resultado anterior prova que, sob uma suposição teórica conhecida (ETH), em redes com n vértices tais que todos os arcos possuem capacidade n−f(n), para uma função limitada f, o problema é difícil. Estendemos este resultado mostrando que, sob a mesma hipótese, o problema também é difícil quando as capacidades são iguais a f(n).