Fluxos Ramificados Arco-disjuntos em Redes de Capacidade Restrita
Resumo
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).
Referências
Bang-Jensen, J. and Bessy, S. (2014). (Arc-) disjoint flows in networks. Theoretical Computer Science, 526:28–40.
Bang-Jensen, J. and Gutin, G. Z. (2008). Digraphs: theory, algorithms and applications. Springer Science & Business Media.
Bang-Jensen, J., Havet, F., and Yeo, A. (2016). The complexity of finding arc-disjoint branching flows. Discrete Applied Mathematics, 209:16–26.
Bang-Jensen, J. and Yeo, A. (2015). Balanced branchings in digraphs. Theoretical Computer Science, 595:107 – 119.
Edmonds, J. (1973). Edge-disjoint branchings. Combinatorial Algorithms, pages 91–96.
Fortune, S., Hopcroft, J., and Wyllie, J. (1980). The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111 – 121.
Impagliazzo, R., Paturi, R., and Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512 – 530.
Lovász, L. (1976). On two minimax theorems in graph. Journal of Combinatorial Theory, Series B, 21(2):96 – 103.
