Problemas de decomposição de fluxos em redes

Abstract

Flows on networks are a fundamental tool in the Graph Theory, with several practical applications. A network N is formed by a (multi)digraph D together with a capacity function u : A(D) → R+, and it is denoted by N = (D, u). A flow on N is a function x : A(D) → R+ such that x(a) ≤ u(a) for all a ∈ A(D). We say that a flow is λ-uniform if its value on each arc of the network with positive flow value is exactly λ, for some λ ∈ R ∗ +. According to Granata et al. (2013), arc-coloured networks are used to model qualitative differences among different regions through which the flow will be sent. They have applications in several areas such as communication networks, multimodal transportation, molecular biology, packing etc. In this work, we deal with two types of flows - (s, t)-flow and s-branching flow. An (s, t)-flow represents the amount of flow that can be sent from s to t in a network N = (D, u). According to Baier, Köhler e Skutella (2005), an (s, t)-flow is k-splittable if it can be decomposed into up to k paths. We consider the problem of decomposing a flow over an arc-coloured network with minimum cost, that is, with minimum sum of the cost of its paths, where the cost of each path is given by its number of colours. We show that this problem is N P-Hard for general flows. When we restrict the problem to λ-uniform flows, we show that it can be solved in polynomial time for networks with at most two colours, and it is N P-Hard for general networks with three colours and for acyclic networks with at least five colours. An s-branching flow must reach every vertex of a network N = (D, u) from a vertex s while loosing exactly one unit of flow in each vertex other than s. According to Bang-Jensen e Bessy (2014), when u ≡ n − 1, the network admits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoint s-branchings. Thus, a classical result by Edmonds (1973) stating that a digraph contains k arc-disjoint s-branchings if and only if the indegree of every set X ⊆ V (D) \ {s} is at least k also characterizes the existence of k arc-disjoint s-branching flows in those networks. In this work, we investigate how a property that is a natural extension of the characterization by Edmonds is related to the existence of k arc-disjoint s-branching flows in networks. Although this property is always necessary for the existence of such flows, we show that it is not always sufficient and that it is hard to decide if the desired flows exist even if we know beforehand that the network satisfies it.