Water transport on finite graphs

Timo Vilkas · 2025

Read Water transport on finite graphs by Timo Vilkas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16911.txt.

Introduction

Timo Vilkas set out a deceptively simple optimization puzzle in 2025. Picture equal barrels on level ground, each holding a varied amount of water, joined by locked pipes filled with water running beneath them. Unlocking a pipe lets two barrels level out. Focusing on one chosen barrel, the question is how high its water level can possibly be raised by opening and closing pipes in a clever order, with no pumps allowed.

The problem is modeled on a finite graph, barrels as nodes and pipes as edges. It grew out of the study of an opinion formation process, where a similar leveling dynamic spreads views through a network. Vilkas argues the puzzle is intricate enough to deserve study in its own right. And hard from an algorithmic standpoint, since the number of possible pipe-opening orders explodes and the best sequence is far from obvious.

Catalog record

CREATORTimo Vilkas
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16911

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Water transport on finite graphs Timo Vilkas Abstract Consider a simple finite graph and its nodes to represent identical water barrels (containing different amounts of water) on a level plane. Each edge corresponds to a (locked, water-filled) pipe connecting two barrels below the plane. We fix one node v v and consider the optimization problem relating to the maximum value to which the level in v v can be raised without pumps, i.e. by opening/closing pipes in a suitable order. This fairly natural optimization problem originated from the analysis of an opinion formation process and proved to be not only sufficiently intricate in order to be of independent interest, but also difficult from an algorithmic point of view. Keywords: Water transport, graph algorithms, optimization, complexity, greedy lattice animal. MSC2020: 05C35, 05C85, 91A68 1 Introduction Imagine a finite number of identical rainwater tanks, with a given capacity of c liters, placed on a plane. Some of them are connected by underground (and water-filled) pipes, which can be closed by locks. After a heavy rain, the tanks collected (potentially different) amounts of water and one can consider the optimization problem to raise the water level in a fixed tank by opening and closing the locks. To cast the problem into an apt mathematical model, consider a finite undirected graph G=(V,E) , which we can assume without loss of generality to be simple (i.e. having neither loops nor multiple edges). The barrels are represented by the nodes (with an assigned value corresponding to the water level in it) and the pipes are represented by the edges of the graph. We start with all pipes locked, an initial water profile \big(\eta_{0}(u)\big)_{u\in V}\in[0,c]^{V} and a given target vertex v\in V , in which the water level is to be maximized. To accomplish this we can open a lock, which will lead to the amounts a and b in the incident barrels to level out – partly if we close the lock early or to their average \tfrac{a+b}{2} if we don’t, see Figure 1 . Figure 1: Converging water levels after opening a lock. In order to formalize this, let us define such a move to be represented by (e,\mu) , where e=\langle x,y\rangle\in E is the pipe we opened and \mu\in[0,\frac{1}{2}] is the fraction of the difference moved from the fuller into the emptier incident barrel, i.e. if we had the profile \big(\eta_{k}(u)\big)_{u\in V} before, it will be \big(\eta_{k+1}(u)\big)_{u\in V} given by \eta_{k+1}(u)=\begin{cases}\eta_{k}(x)+\mu\,\big(\eta_{k}(y)-\eta_{k}(x)\big),&\text{for }u=x\\ \eta_{k}(y)+\mu\,\big(\eta_{k}(x)-\eta_{k}(y)\big),&\text{for }u=y\\ \eta_{k}(u),&\text{for }u\in V\setminus\{x,y\}\end{cases} (1) after the move (e,\mu) . Based on this elementary building block, we can define the objective of the optimization problem: Definition 1 . Given graph G=(V,E) , initial water profile \{\eta_{0}(u)\}_{u\in V} and a target vertex v\in V , we can execute a (finite) move sequence , represented by an ordered list of edges and fractions, \varphi\in(E\times[0,\tfrac{1}{2}])^{t} , where \varphi_{k}=(e_{k},\mu_{k}) corresponds to a single move as in ( 1 ). By \kappa(v) we denote the supremum over all water levels achievable at v with finite move sequences. Obviously, \kappa(v) wouldn’t change if we allowed infinite move sequences, as those can be approximated by finite ones. In a preliminary section, we will verify that neither restricting to complete moves (where \mu=\frac{1}{2} ) nor allowing hypermoves , i.e. to open several pipes simultaneously, changes \kappa(v) , cf. Lemmas 2.4 and 2.5 . 1.1 Main results Based on these auxiliary results, we are going to prove that there always exists a finite sequence of hypermoves achieving water level \kappa(v) at the target vertex (Theorem 3.1 ). In Section 4 some light will be shed on heuristic algorithmic approaches to this optimization problem and in Subsection 4.3 we show that the water transport problem is NP-hard (Theorem 4.1 ). Besides that, an abundance of example instances will be given both to illustrate the problems with intuitive heuristics and to deal with tractable graphs such as paths and the complete graph, for which the calculation of \kappa(v) can be done explicitely. The last section contains further observations and related open problems. 1.2 Related work First and foremost, this work complements an analysis of the same optimization problem on infinite graphs with i.i.d. random initial water levels [ 9 ] , in which it was established that the two-sided infinite path \mathbb{Z} behaves much more like a finite graph (in the sense that \kappa(v) is random) as opposed to all other infinite, quasi-transitive graphs, for which \kappa(v) is deterministic. Readers familiar with mathematical models for opinion formation in groups might find that ( 1 ) in essence resembles update rules in average preserving models for consensus formation in social networks. Indeed, the problem at hand arises naturally in the theoretical analysis of such models related to the question of how extreme an opinion a fixed agent can get, given an initial opinion profile on a specified network graph (e.g. for the bounded confidence model introduced by Deffuant et al. in 2000, which was analyzed in [ 7 ] , [ 8 ] and [ 10 ] ). In order to tackle this question, Häggström [ 7 ] introduced a non-random pairwise averaging process, which he proposed to call Sharing a drink (SAD). It was originally considered on \mathbb{Z} only, but can readily be generalized to any graph (see Definition 2 ). In fact, SAD is both a special case of (as the initial profile considered there is \eta_{0}=\delta_{u} ) and dual to the water transport described above, made precise in Lemma 2.1 . As Thm. 2.3 in [ 7 ] it was shown that on \mathbb{Z} (and as a consequence also on any finite path) with initial profile \delta_{u} it holds \kappa(v)=\frac{1}{d(u,v)+1} , where d(u,v) is the graph distance between vertices u and v . This result was recently generalized to simple graphs in full generality [ 6 ] . The duality of SAD to averaging processes in general, turned out to be a useful tool even in the analysis of other consensus formation processes, such as the edge-averaging process (cf. [ 4 ] and [ 5 ] ). 2 Preliminaries 2.1 Sharing a drink Let us first repeat the formal definition of the SAD-process: Definition 2 . For a graph G=(V,E) and some fixed vertex u\in V , let \delta_{u}:\ V\to[0,1]^{V} denote the indicator of vertex u , i.e. \delta_{u}(w)=\begin{cases}1\quad\text{for }w=u\\ 0\quad\text{for }w\neq u.\end{cases} Given a finite move sequence as above, say \varphi=\big((e_{1},\mu_{1}),(e_{2},\mu_{2}),\dots,(e_{t},\mu_{t})\big) , the interaction process called Sharing a drink (SAD) initiated from vertex u starts with initial water profile \eta_{0}=\delta_{u} , proceeds along \varphi according to ( 1 ) and after these t moves ends up with a terminal water profile \eta_{t}\in[0,1]^{V} . When implementing a (finite) move sequence on an arbitrary initial water profile \eta_{0} , the terminal values at each vertex will obviously be convex combinations of the initial values. How much each vertex u contributed to the amount of water at a given vertex v is captured by the corresponding dual SAD-process: Lemma 2.1 (Duality). Consider an initial water profile \{\eta_{0}(u)\}_{u\in V} on G=(V,E) and a finite move sequence \varphi of length t\in\mathbb{N} . Then it holds for all v\in V that \eta_{t}(v)=\sum_{u\in V}\xi_{u,v}(t)\,\eta_{0}(u), (2) where \xi_{u,v}(t) is the value at vertex u in the

Read the complete text