The data transfer problem in a system of systems

Systems of systems are collections of independent systems which interact and share information to provide services. To communicate, systems can opportunistically make use of contacts that occur when two entities are close enough to each other. In this paper, it is assumed that reliable predictions can be made about the sequence of such contacts for each system. An information item (a datum) is split into several datum units which are to be delivered to recipient systems. During a contact between two systems, a sending system can transfer one stored datum unit to a receiving system. Source systems initially store some of the datum units. The data transfer problem consists in searching for a valid transfer plan, i.e. a transfer plan allowing the datum units to be transmitted from their source systems to the recipient systems. The dissemination problem consists in searching a valid transfer plan which minimizes the dissemination length, i.e. the number of contacts which are necessary to deliver all the datum units to the recipient nodes. To our knowledge, there is no previous work attempting to determine the theoretical complexity of these problems. The aim of this paper is to determine the frontier between easy and hard problems. We show that the problems are strongly NP-Hard when the number of recipients is equal to 2 or more (while the number of datum units is unbounded) or the number of datum units is equal to 2 or more (while the number of recipients is unbounded). We also show that these problems are polynomially solvable when the number of datum units or the number of recipient nodes is equal to 1, or when these parameters are all upper bounded by given positive numbers. The complexity of two related problems is also studied. It is shown that knowing whether there exist k mutually arc-disjoint branchings in an evolving graph and k arc-disjoint Steiner trees in a directed graph without circuit are strongly NP-Complete.