Data: 10/06/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: An study of an Edmonds-like property for branching flows
Palestrante: Ana Karolinna Maia de Oliveira (UFC)


Resumo: An s-branching flow f in a network N= (D, u), such that u is the capacity function, is a flow that reaches every vertex in V(D)\{s} from s while loosing exactly one unit of flow in each vertex other than s. It is known that the hardness of the problem of finding k arc-disjoints-branching flows in a network N is linked to the capacity u of the arcs in N: for fixed c, the problem is solvable in polynomial time if every arc has capacity n−c and, unless the Exponential Time Hypothesis (ETH) fails, there is no polynomial time algorithm for it for most other choices of u. The hardness of a few cases remains open. We further investigate a property depending on k and the capacity function that aims to characterize networks admitting k arc-disjoints-branching flows. Such property is a generalization of similar result when all arcs have capacity n−1, basedon Edmonds’ branching theorem. We show that, although in general this property doesn’t offer a complete characterization, it characterizes particular cases of networks containing k arc-disjoints-branching flows. For such positive cases, we also remark that there are polynomial-time algorithms to find the arc-disjoint flows, if they exist.