Topological and Online Analysis of Dynamic Storage Networks

Storage sites are a key component of future power grids that have a high share of renewable energy [4, 18, 73]. Using dynamic flow networks and techniques from online problems [3, 9, 28], we model and analyze the question of how to utilize these storage sites most efficiently. Our model consists of a multi-terminal flow network where each terminal is a supply, storage, or demand node. For sequences of supplies and demands that are revealed step by step, we answer the two questions at which storage nodes to store flow if any is oversupplied, and from which storage nodes to take flow if too little is supplied. The limited capacities of a network coupled with the unknown future supplies and demands may produce scenarios in which flow cannot be stored in a way that an optimal use of it can be guaranteed. Using external flow patterns known from the context of mimicking networks [40], we develop a technique to obtain optimal online algorithms for such problems. We apply it to show that in every network with a single producer and a single consumer node, there is always an online algorithm that can guarantee that approximately 83% of the supplied energy can be consumed in comparison to the offline setting where all future supplies and demands are known ahead. We also show that there are networks with a single producer and a single consumer node where no better performance than this is possible. Two multi-terminal networks are mimicking networks if they share identical external flow patterns, i. e., for every flow that evokes certain net flows at the terminals of the one network, there is a flow evoking the same net flows at the terminals of the other network. For these mimicking networks, we show that the common assumption that for every terminal bipartition there is a unique min-cut separating the terminals according to this bipartition [52, 55] is a quite strong restriction and yields wrong expectations concerning the complexity of related problems. We show that the techniques commonly used to enforce this assumption may yield networks whose smallest contraction-based mimicking network is exponentially larger than of the original one. We examine problems in this setting without this unique mincuts assumption and give close upper and lower bounds on the complexity of mcbmn, i. e., of deciding whether the number of nodes of the smallest contraction-based mimicking network of a given network is at most a given number. We show that mcbmn is in P2 and that mcbmn is coNP-hard. The analysis of this problem parameterized over the number of terminals is difficult without the unique min-cuts assumption. We pinpoint few cases that suggest that this problem is not fixed-parameter tractable anymore when the assumption is dropped. So far, it was only known that the problem is in FPT under the unique min-cuts assumption [52]. The lifted unique min-cuts assumption gives rise to up to exponentially many min-cuts for each terminal bipartition. By representing min-cuts either by all nodes on the source side or by all edges that are cut, different types of set systems are obtained. These set systems are poorly understood and, especially in the multi-terminal case, the root for many unsolved problems in this and related areas. For the classical 2-terminal case, we find a short characterization for the set systems that represent min-cuts as node sets. For the edge set representation, we develop a new framework that replaces 3 the set systems of well-known NP-complete problems by the edge set system implicitly encoded in an s-t flow network. The two opposing effects of succinct representation and restrictions on the sets that can be encoded are shown to outweigh each other depending on whether the emerging problem involves counting all min-cuts. If no counting is involved, the problems are P-complete. Otherwise, the problems are conjectured to be PP-complete since the counting versions are #P-complete [71]. For the analysis of these problems, the notion of the max-flow DAG is developed that succinctly represents the min-cut set systems. It allows simple algorithmic solutions and helps us to discover several dualities among the new problems.