arXiv:2605.09432v1 [cs.NI] 10 May 2026
The Carrier Pigeon Internet Protocol: An Algorithmic (and Lighthearted) Perspective Matthias Bentert
Shay Kutten
Darya Melnyk
TU Berlin Berlin, Germany [email protected]
Technion Haifa, Israel [email protected]
TU Berlin Berlin, Germany [email protected]
Tijana Milentijević
Stefan Schmid
TU Berlin Berlin, Germany [email protected]
TU Berlin Berlin, Germany [email protected]
Abstract The theoretical model behind the pigeon post as a link layer in a communication network was introduced by Shannon (under the guise of studying One-Time Pads for cryptography). That is, to send a one-hop message to 𝑣, a node 𝑢 needs a mail pigeon bred and raised at 𝑣. When sending a message using a pigeon to 𝑣, node 𝑢 loses the pigeon. To send another message to 𝑣, node 𝑢 needs another pigeon of 𝑣. It has been demonstrated that the communication bandwidth achievable with pigeon post can exceed that of networks using other media. This has already motivated the introduction of Internet standards that allow the use of pigeons as Internet link-layer media. In this paper, we begin to fill in the missing piece: designing algorithms for breeding and scheduling pigeons to meet a given communication demand efficiently, minimizing the number of pigeons required. We consider singlehop, 2-hop, and multihop pigeon use. While the singlehop variant admits a simple characterization, both the 2-hop and the multihop variants are NP-hard. For the latter variants, we present a polynomial-time algorithm based on demand aggregation that achieves a 2-approximation for the number of pigeons used. We believe that this pigeon-based perspective offers both amusing and instructive insights into network design and hopefully, into ornithology.
CCS Concepts • Networks → Traffic engineering algorithms; • Theory of computation → Design and analysis of algorithms.
Keywords Internet protocols, routing, non-terrestrial networks, carrier pigeon service
1
Introduction
The AI revolution places heavy demands on communication bandwidth, which is often the bottleneck in AI tasks such as training models; see, e.g., [24, 32]. In the quest to increase bandwidth, researchers turn to the time-tested communication method of the pigeon post, but adapt it for modern communication. See IP over Avian Carriers (IPoAC) [10, 47] and the Carrier Pigeon Internet Protocol (CPIP) [22]. A motivation for such link layer standards can be the demonstration that the bandwidth of communication
using pigeons could be much higher than that of competing media1 , since a pigeon can carry a chip containing a substantial amount of information by using the PEI protocol (Pigeon Enabled Internet) in the TCP framework (Transmission by Carrier Pigeons) [7]. This was demonstrated again in [5, 44] and in [35, 43]. Pigeons have also been used in other layers of the Internet, see, e.g. [42, 48]. Environmental aspects also support the use of pigeon post. Fiber optics, the current leading alternative, requires substantial amounts of silicon, commonly in the form of sand. This comes at a time when sand in various parts of the world is disappearing, a development that worries environmentalists, economists, and governments [9, 28, 36]. The UN is also worried [33]. So, next time you are sitting on the beach in the Riviera, or Cancun, or Thailand, or the Maldives, remember that the sand is in danger. If you want to keep having such vacations, supporting Pigeon Post as opposed to fiber optics is the way to go. In the long term, pigeon post also has the potential to help increase agricultural yields. Using more pigeons generates more guano [7]. This guano is a good fertilizer [30, 39], which suggests that using pigeon post may help grow more food. This, in turn, may allow one to free up land for ecological restoration, thus restoring forests and wetlands, and increasing biodiversity. 2 The theoretical basis for Pigeon Post was laid in Shannon’s seminal work [38]. Shannon, however, did not mention pigeons by name. Instead, he referred to his version of Vernam’s encryption protocol [46]. This is known today as a “one-time pad” and appears in many popular spy-related books in the fiction literature, e.g. [19, 41].3 The spy has some text (or a bit string) given to her by her country’s secret service. Let us call this text a “pigeon”. Using this pigeon, she encrypts a message to generate a “ciphertext” to be read by the secret service (often, the encryption is just an XOR operation between each bit of the message and the corresponding bit of the pigeon). The service reads the message by applying the reverse operation (often just XORing the ciphertext with the corresponding bit of the same pigeon). Shannon analyzed the version in 1 Provided that one does not communicate at night and that one does not mind the
shit [7]. 2 On a serious note, whatever one may think of pigeon post, the environmental crisis [14] and the hunger crisis [26] are prevalent; let us hope that this paper will make at least a small contribution to increasing awareness. 3 A reader who reads these two books as a result of our paper has already gained a lot from the paper. The authors do not have any financial interest in the books or the publishers.
Conference’17, July 2017, Washington, DC, USA
Model Singlehop 2-hop 2-hop -
ILP
Multihop Multihop -
ILP
Matthias Bentert, Shay Kutten, Darya Melnyk, Tijana Milentijević, and Stefan Schmid
Approximation optimal Algorithm 1 2-approx. Algorithm 2
Number of pigeons Θ(𝑛 2 ) Theorem 2 𝑂 (|𝑆 | + |𝐷 |) Theorem 3
optimal
optimal
2-approx. Algorithm 2
𝑂 (|𝑆 | + |𝐷 |) Theorem 3
optimal
optimal
Runtime 𝑂 (|𝑆 | + |𝐷 |) Theorem 2 𝑂 (𝑛 2 ) Theorem 3 exponential Theorem 5 𝑂 (𝑛 2 ) Theorem 3 exponential Theorem 7
Table 1: Summary of results.
which both sides then discard the pigeon. Hence, if the spy initially has 𝑥 pigeons to send messages to the secret service (each such pigeon could not be sent to anyone but that secret service), then after the message is sent, the spy has only 𝑥 − 1 pigeons remaining. As is sometimes regrettably the case, the ancient Egyptians, Persians, Greeks, Romans, etc., did not wait for Shannon’s theoretical foundations but instead proceeded with the practice of using pigeons to send messages.4 See [49]. Our Contributions. We view this paper as an “Introduction to Pigeon Post”. We first formally define how network communication can be implemented using mail pigeons (also known as carrier or homing pigeon). We thereby assume that the mail pigeons can be bred in a demand-aware manner, i.e., the breeders are aware of the future communication demands. Optimizing these breeding locations is critical as later in their lives, mail pigeons can only fly in one direction: home (their birthplace). The objective is to find a pigeon traffic pattern that uses as few pigeons as possible (model details will follow). We first analyze a scenario where messages have to be sent directly to their receivers, by a single pigeon (singlehop), and present a simple optimal algorithm. We then generalize the model and allow forwarding of messages using two or more homes; these homes can serve as intermediate nodes where messages are relayed to other pigeons (multihop). We show that the general problem is NP-hard, even if the number of homes for forwarding is unlimited. We further present a 2-approximation algorithm for a scenario where we are allowed to use one intermediate node, that is, two pigeons (2-hop). We also present elegant Integer Linear Programs for the NP-hard problems we discuss. Our results are summarized in Table 1. Further Related Work. The design of demand-aware structures such as codes (e.g., Huffman codes [25]), data structures (e.g., biased binary search trees [8, 12, 40]), and networks (e.g., splay nets [3, 37]) is an evergreen topic in algorithm theory. Recently, demand-aware networks have received particular interest in the context of reconfigurable datacenter networks, whose topology can be optimized to match the traffic workload [4, 16, 18], see, for example, Google’s Jupiter datacenter [34]. Demand-aware networks are attractive as communication traffic is known to exhibit substantial structure [2], which can be exploited for optimization. 4 Modern physics does not rule out the possibility of time travel, so it may be the case
that those early adopters did rely on Shannon’s work after all [29].
Many optimization problems in communication rely on demand matrices, including traffic engineering [17], and the early works date back to the beginnings of the Internet [27]. There is also interesting research on estimating the amount of communication to be sent from each node 𝑖 to each node 𝑗 [31]. Matrices for a directed graph (such as the graph we use here) are addressed, e.g., in [21]. For even older versions, see e.g., [23] (the famous transportation problem) and [6]. The problem is also connected to multi-commodity flow problems [20] as well as graph layout problems [13, 15]: the design of a demand-aware graph of degree 2 corresponds to the minimum linear arrangement problem [3]. These problems are NP-hard in many scenarios, also on directed networks [15] (like our demand graph). Vehicle routing problem [45] relates to our problem as well. However, different variants of this problem, including the multidepot vehicle routing [11], to the best of our knowledge, do not consider the relaying of goods between vehicles, which is essential for our problem. More remotely, our storage model is inspired by the PigeonHole Principle (see, e.g., [1]): that is, if there are more pigeons than holes in a pigeon house, then some holes will simply need to accommodate multiple pigeons.
2
Model
In our model, communication demands may arise between different locations. We represent these locations by a set of nodes 𝑉 with |𝑉 | = 𝑛 and the communication demand as a directed and unweighted demand graph 𝐺 𝐷 = (𝑉 , 𝐸𝐷 ). There is a directed edge (𝑖, 𝑗) ∈ 𝑉 ×𝑉 with 𝑖 ≠ 𝑗 in 𝐺 𝐷 , if there is a communication demand from node 𝑖 to node 𝑗. We assume that the demand graph is stored in an adjacency matrix 𝑀𝐷 , which we refer to as the demand matrix. Note that 𝑀𝐷 is not necessarily symmetric and satisfies 𝑀𝐷 (𝑖, 𝑖) = 0 for all 𝑖 ∈ 𝑉 . Nodes with outgoing demand are referred to as sources 𝑠 ∈ 𝑆, and nodes with incoming demand as destinations 𝑑 ∈ 𝐷; note that a node may play both roles. The communication infrastructure is induced by pigeons and can be viewed as a dynamic directed multigraph, called infrastructure graph. Let 𝑃 denote a set of pigeons (at a given time). Each pigeon 𝑝 ∈ 𝑃 is associated with two nodes: a home node ℎ(𝑝) ∈ 𝑉 , where the pigeon was bred and (only) to which it can fly, and a remote node 𝑟 (𝑝) ∈ 𝑉 , where the pigeon is initially placed. As we will see, our problems concern defining home and remote nodes so that a minimal number of pigeons can serve a given communication demand. Upon release from its remote location, pigeon 𝑝 flies directly from 𝑟 (𝑝) to ℎ(𝑝) without intermediate stops. A pigeon thus induces a directed edge (𝑟 (𝑝), ℎ(𝑝)) in the infrastructure graph. When 𝑝 flies, the edge is deleted. Multiple pigeons may induce parallel edges between the same pair of nodes, each used at a different time, to ensure that transportation demand is satisfied. The communication demand does not need to be carried directly from its source to the destination by a single pigeon. Instead, demand may be routed along directed paths in the infrastructure graph. A unit of demand originating at node 𝑖 and destined for node 𝑗 may traverse a sequence of intermediate nodes. At intermediate nodes, demand can be gathered from arriving pigeons and split to the corresponding departing pigeons. Similarly, demand from
Algorithms for Carrier Pigeons
multiple arriving pigeons can be batched together and sent using a single pigeon. We distinguish between singlehop, 2-hop, and multihop uses of pigeons. In the Singlehop problem variant, each unit of demand must be transported directly from its source to its destination by a single pigeon, without using intermediate nodes. Consequently, no aggregation or forwarding of demand is allowed, and a pigeon flying from node 𝑖 to node 𝑗 can only carry demand destined for 𝑗 that originates at 𝑖. In the 2-hop problem, the demand from node 𝑖 to node 𝑗 may either be transported directly or routed via a single intermediate node 𝑙, resulting in a path 𝑖 → 𝑙 → 𝑗 in the infrastructure graph. The Multihop problem is a generalization of the 2-hop , in which communication demand may be forwarded through multiple intermediate nodes via multiple pigeons sequentially. In this paper, we assume that pigeons can carry arbitrary amounts of information. When a pigeon 𝑝 arrives at its home node ℎ(𝑝), all the demand it carries is delivered to the home node. If ℎ(𝑝) is not the final destination of the demand, the information can be stored at that node and forwarded at a later time by pigeon 𝑝 ′ , which has ℎ(𝑝) as its remote node, i.e., ℎ(𝑝) = 𝑟 (𝑝 ′ ). In that case, ℎ(𝑝) is an intermediate node for the demand. Demand may wait arbitrarily long at nodes before being forwarded further. Nodes have unlimited storage capacity and may aggregate incoming demand without restriction. This part of the model actually follows from the Pigeon-Hole Principle: that is, if there are more pigeons than holes at pigeon house ℎ(𝑝), then some holes simply will need to accommodate multiple pigeons. Figure 1 illustrates a demand graph and a corresponding infrastructure graph induced by pigeons in a Multihop problem. The demand is delivered successfully if there exists an assignment of all demands to pigeon flights over time such that, for every demand pair (𝑖, 𝑗) ∈ 𝐺 𝐷 , the demand is routed from 𝑖 to 𝑗 along a directed path in the (dynamic) infrastructure graph. In general, for the three problems Singlehop - , 2-hop and Multihop , the pigeon post operates in two conceptual phases. In the first, offline planning phase, the complete demand matrix 𝑀𝐷 is known, and our objective is to breed pigeons (i.e., define their home nodes) and place them in their remote nodes according to our network design decisions. In the second phase, the execution phase, pigeons fly to their home nodes according to the required schedule (i.e., wait for the predecessor pigeon in multihop routing with intermediate nodes). The demand is routed along the established infrastructure graph following a predefined schedule. Our objective is to construct an infrastructure graph that routes all demands from the demand matrix while minimizing the total number of pigeons. Besides the minimization problems, we also consider decision versions of these problems (e.g., when studying hardness), where we ask whether a given demand can be satisfied with at most 𝑘 pigeons.
3
Theoretical Results
In this section, we present theoretical results for the three problem variants: Singlehop - , 2-hop - , and Multihop - . For all
Conference’17, July 2017, Washington, DC, USA Demand graph 𝐺 𝐷
Infrastructure graph 𝐺 𝐼
𝑠1
𝑑1
𝑠1
𝑑1
𝑠2
𝑑2
𝑠2
𝑑2
𝑠3
𝑑3
𝑠3
𝑑3
Figure 1: On the left side a demand graph 𝐺 𝐷 is depicted with 3 source and 3 destination nodes. The right side shows the corresponding infrastructure graph 𝐺 𝐼 induced by pigeons, illustrating an optimal placement and routing solution that satisfies all the demands while minimizing the total number of pigeons used. In this example, a pigeon 𝑝 flying from 𝑠 3 to 𝑠 1 has 𝑠 1 as its birthplace, i.e. ℎ(𝑝) = 𝑠 1 . The pigeon is brought to a remote node 𝑠 3 , i.e. 𝑟 (𝑝) = 𝑠 3 , and flies home directly to 𝑠1 .
three problems, we present a simple lower bound on the number of pigeons needed: Theorem 1 (Lower bound on the number of pigeons). The minimal amount of pigeons needed to transfer the entire demand is |𝑃 | ≥ max(|𝑆 |, |𝐷 |), where 𝑃 denotes the set of pigeons, 𝑆 and 𝐷 a set of demand sources and demand destinations, respectively. Proof. Observe that for each edge (𝑖, 𝑗) in the demand graph, there must be at least one pigeon starting in the remote node 𝑖. Similarly, there must be at least one pigeon arriving in its home 𝑗. The lower bound is achieved by summing over all remote nodes and home nodes, respectively, and choosing the maximum value. □
3.1
Singlehop -
Solution
We begin by considering the singlehop pigeons (Singlehop - ) problem, in which each unit of demand must be transported directly from its source to its destination by pigeons. In contrast to the multihop setting, intermediate nodes are not permitted, and demand cannot be aggregated or forwarded through other nodes. Consequently, each pigeon can only carry demand originating at its remote node and destined for its home node. Algorithm 1 shows a trivial solution in the Singlehop setting, in which each source node sends a pigeon directly to the corresponding destination. In particular, the problem reduces to selecting a pigeon for each edge in the demand graph. Observe that the optimal solution can be computed efficiently, as it only needs to consider all sources and destinations. In the worst case, however, all 𝑛 2 demand edges are present in the graph. These results are summarized in the following theorem: Theorem 2. Algorithm 1 computes the optimal amount of pigeons in 𝑂 (|𝑆 | + |𝐷 |) time. This algorithm uses Θ(𝑛 2 ) pigeons in the worst case.
Conference’17, July 2017, Washington, DC, USA
Algorithm 1 Singlehop -
Matthias Bentert, Shay Kutten, Darya Melnyk, Tijana Milentijević, and Stefan Schmid
Algorithm
Algorithm 2 2-hop -
Coordinator Algorithm
1: 𝑃 ← ∅
1: 𝑃 ← ∅
Offline Planning Phase 2: for all directed edges (𝑖, 𝑗) ∈ 𝑉 × 𝑉 with 𝑖 ≠ 𝑗 do 3: if (𝑖, 𝑗) ∈ 𝐺 𝐷 then 4: breed pigeon 𝑝 at node 𝑗 5: 𝑟 (𝑝) ← 𝑖, ℎ(𝑝) ← 𝑗 ⊲ set remote and home node 6: ship pigeon 𝑝 to node 𝑖 7: 𝑃 ← 𝑃 ∪ {𝑝} 8: end if 9: end for Flight Scheduling Phase 10: let all pigeons fly simultaneously to their respective homes
2: Execute the following algorithm for each connected component
3.2
2-hop -
Solution
We now move beyond direct communication and study the use of intermediate nodes. Allowing demand to be forwarded through other nodes significantly increases the capabilities of the pigeon post by enabling mail aggregation before it is delivered to its final destinations. We first focus on the 2-hop problem, in which each demand is routed using at most two pigeon flights. The 2-hop problem can be viewed as a restricted form of the general Multihop problem, in which all mail delivery paths are required to have a length of at most two. Algorithm 2 presents the 2-hop coordinator algorithm. The coordinator algorithm is based on gathering all the demand at one node, called the coordinator. Then, the coordinator spreads the demand and sends pigeons to the corresponding destinations. Note that we consider each weakly connected component separately in the algorithm, and pick the node with the largest degree in the connected component as the coordinator. Any demand in a connected component is then carried from one source to the coordinator (with one pigeon) and then from the coordinator to the destination (using a single pigeon for each destination). Theorem 3. Let 𝑐 denote the number of weakly connected components in 𝐺 𝐷 , and 𝐶 1, . . . , 𝐶𝑐 be the corresponding weakly connected components. We use Δ(𝐶𝑖 ) to denote the maximum degree of the weakly connected component 𝐶𝑖 . Algorithm 2 computes a solution with Í Í up to |𝑆 |+|𝐷 |− 𝑖 ∈ [𝑐 ] Δ(𝐶𝑖 ) pigeons. It is thus a (2− 𝑖 ∈ [𝑐 ] Δ(𝐶𝑖 )/𝑛)approximation of the optimal 2-hop in 𝑂 (𝑛 2 ) time.
solution. The algorithm runs
Proof. In each weakly connected component, Algorithm 2 selects a coordinator node and routes the whole demand in two phases: first, all sources send their entire demand to the coordinator, and second, the coordinator sends the accumulated demand to the corresponding destinations. In each weakly connected component, the algorithm correctly serves the demand. This solution requires at most one pigeon from each source in 𝑆 to the respective coordinator and at most one pigeon from the coordinator to each destination in 𝐷, resulting in a cost of at most |𝑆 | + |𝐷 | pigeons. Since the coordinator is chosen to be the highest degree node in the weakly connected component, i.e., it is a source and/or a destination, the solution saves at least as
of 𝐺 𝐷 3: coordinator 𝐾 ← highest degree node of the current connected
component Offline Planning Phase 4: for all nodes 𝑖 ∈ 𝑉 with 𝑖 ≠ 𝐾 do Í 5: if 𝑗 ∈𝑉 𝑀𝐷 [𝑖, 𝑗] > 0 then 6: breed pigeon 𝑝 7: 𝑟 (𝑝) ← 𝑖, ℎ(𝑝) ← 𝐾 ⊲ gather all outgoing demand of 𝑖 at coordinator 8: ship pigeon 𝑝 to node 𝑖 9: 𝑃 ← 𝑃 ∪ {𝑝} 10: end if 11: end for 12: for all nodes 𝑗 ∈ 𝑉 with 𝑗 ≠ 𝑐 do Í 13: if 𝑖 ∈𝑉 𝑀𝐷 [𝑖, 𝑗] > 0 then 14: breed pigeon 𝑝 15: 𝑟 (𝑝) ← 𝐾, ℎ(𝑝) ← 𝑗 ⊲ send all demand destined for 𝑗 from coordinator 16: ship pigeon 𝑝 to node 𝐾 17: 𝑃 ← 𝑃 ∪ {𝑝} 18: end if 19: end for Flight Scheduling Phase 20: let pigeons with a home in 𝐾 fly to 𝐾 21: let pigeons with a home not in 𝐾 fly from 𝐾 to their homes
many pigeons as Δ(𝐶𝑖 ) for each weakly connected component 𝐶𝑖 , 𝑖 ∈ [𝑐]. Let 𝐴𝐿𝐺 denote the total cost of the algorithm. Then, Í 𝐴𝐿𝐺 ≤ |𝑆 | + |𝐷 | − 𝑖 ∈ [𝑐 ] Δ(𝐶𝑖 ). In Theorem 1, we derived a lower bound of max(|𝑆 |, |𝐷 |) on the number of pigeons for an optimal solution 𝑂𝑃𝑇 . The approximation ratio of Algorithm 2 can be computed as ∑︁ ∑︁ 𝐴𝐿𝐺 ≤ |𝑆 | + |𝐷 | − Δ(𝐶𝑖 ) ≤ 2 · max(|𝑆 |, |𝐷 |) − Δ(𝐶𝑖 ) 𝑖 ∈ [𝑐 ]
𝑖 ∈ [𝑐 ]
≤ (2 −
∑︁
Δ(𝐶𝑖 )/𝑛) · 𝑂𝑃𝑇 .
𝑖 ∈ [𝑐 ]
Í Hence, the algorithm computes a (2− 𝑖 ∈ [𝑐 ] Δ(𝐶𝑖 )/𝑛)-approximation of the optimal solution. The computed approximation factor for Algorithm 2 is tight. Consider for example a cyclic demand instance on 𝑛 nodes, where each node has exactly one outgoing demand and exactly one incoming demand. There is only one connected component in the demand graph, and every node has degree 2. In this case, the optimal solution requires 𝑛 pigeons, while the Algorithm 2 uses 2 · 𝑛 − 2 pigeons, resulting in an approximation factor 2 − 2/𝑛. The runtime of the algorithm is dominated by the computation of the weakly connected components which can be done in 𝑂 (𝑛 2 ) time. □ In the following, we show that it is hard to compute an optimal solution for the 2-hop problem.
Algorithms for Carrier Pigeons
Theorem 4. The decision variant of 2-hop -
Conference’17, July 2017, Washington, DC, USA
is NP-hard. 𝐶1
Proof. We reduce from 3SAT. An instance of 3SAT consists of a Boolean formula 𝜑 in conjunctive normal form, where each clause contains exactly three literals. Given an instance 𝜑 of 3SAT, we construct an instance (𝐺 𝐷 , 𝑘) of 2-hop as follows. The demand graph 𝐺 𝐷 = (𝑉 , 𝐸) consists of one node for each clause 𝐶 1, . . . , 𝐶𝑚 ; one node for each positive literal 𝑥 1, . . . , 𝑥𝑛 and negative literal 𝑥 1, . . . , 𝑥 𝑛 ; one special node and additional (6𝑛 + 12)(2𝑛 + 3𝑚) nodes, which will be explained later. We set 𝑘 = 12𝑛 2 + 18𝑛𝑚 + 27𝑛 + 39𝑚. We place the demand edges as follows: from each clause 𝐶𝑖 to each literal 𝑥 𝑗 or 𝑥 𝑗 that appears in that clause; from each clause 𝐶𝑖 to the special node ; from each literal to ; from 𝑥 𝑗 to 𝑥 𝑗 and from 𝑥 𝑗 to 𝑥 𝑗 for each 𝑗 ∈ [𝑛]. Demand edges from each clause 𝐶𝑖 to each literal 𝑥 𝑗 or 𝑥 𝑗 that appears in that clause and between literals are called forced edges. In total, there are 2𝑛 + 3𝑚 forced edges. For 𝑒 each forced edge 𝑒 = (𝑎, 𝑏), we add (6𝑛 + 12) additional nodes 𝑢𝑖,𝑗 𝑒 , 𝑢 𝑒 ), with 𝑖 ∈ [2𝑛 + 4] and 𝑗 ∈ [3]. We also add demand edges (𝑢𝑖,1 𝑖,2 𝑒 , 𝑢 𝑒 ), (𝑢 𝑒 , 𝑢 𝑒 ), (𝑢 𝑒 , 𝑎), (𝑢 𝑒 , 𝑎), and (𝑢 𝑒 , 𝑏) for each forced (𝑢𝑖,1 𝑖,3 𝑖,2 𝑖,3 𝑖,2 𝑖,3 𝑖,3 edge 𝑒 = (𝑎, 𝑏) and each 𝑖 ∈ [2𝑛 + 4]. For each forced edge 𝑒 and 𝑒 , 𝑢 𝑒 , 𝑢 𝑒 } an arm of the forced each 𝑖 ∈ [2𝑛 + 4], we call the set {𝑢𝑖,1 𝑖,2 𝑖,𝑒 edge gadget for 𝑒. An example of the construction is shown in Figure 2 and the forced edge gadget is illustrated in Figure 3. Since the construction can clearly be computed in polynomial time, it remains to show correctness. (⇒) Assume that 𝜑 is a yes-instance, that is, there exists a truth assignment to the variables of 𝜑 such that all clauses are satisfied. Now, we build a solution for the constructed instance (𝐺 𝐷 , 𝑘) of 2hop - . We place the pigeons in the following way: three pigeons in each clause 𝐶𝑖 with home node literal 𝑥 𝑗 that appears in that clause (total 3𝑚 pigeons); one pigeon in literal 𝑥 𝑗 with home in 𝑥 𝑗 and one pigeon in 𝑥 𝑗 with home in 𝑥 𝑗 for all 𝑗 ∈ [𝑛] (total 2𝑛 pigeons); one pigeon in 𝑥 𝑗 or 𝑥 𝑗 with home node based on the truth assignment in 𝜑 for all 𝑗 ∈ [𝑛] (total 𝑛 pigeons). Additionally, for each forced edge 𝑒 = (𝑎, 𝑏) and each 𝑖 ∈ [2𝑛+4], we add a pigeon 𝑒 with home node 𝑢 𝑒 ; one pigeon in 𝑢 𝑒 with home node 𝑢 𝑒 ; in 𝑢𝑖,1 𝑖,2 𝑖,2 𝑖,3 𝑒 with home node 𝑎 (total 6𝑛 + 12 pigeons per one pigeon in 𝑢𝑖,3 forced edge). This construction is shown in Figure 3. Note that the total number of pigeons placed is 3𝑚 + 2𝑛 +𝑛 + (2𝑛 + 3𝑚)(6𝑛 + 12) = 12𝑛 2 + 18𝑚𝑛 + 27𝑛 + 39𝑚 = 𝑘. We next discuss how to schedule the pigeons. First, we let the 𝑒 to 𝑢 𝑒 , then 𝑢 𝑒 to 𝑢 𝑒 , and finally 𝑢 𝑒 to 𝑎 for pigeons fly from 𝑢𝑖,1 𝑖,2 𝑖,2 𝑖,3 𝑖,3 each forced edge 𝑒 = (𝑎, 𝑏) and each 𝑖 ∈ [2𝑛 + 4]. Next, pigeons fly from each clause 𝐶𝑖 to the literals appearing in that clause. Then, pigeons between the literals 𝑥 𝑗 and 𝑥 𝑗 for all 𝑗 ∈ [𝑛]. Finally, for every variable 𝑥 𝑗 , a pigeon is released from 𝑥 𝑗 to if 𝑥 𝑗 is assigned true and a pigeon is released from 𝑥 𝑗 to if it is assigned false. Now, we show that each demand is satisfied either directly or over two hops using an intermediate node in the constructed infrastructure graph. In particular, whenever a pigeon is placed on an edge (𝑢, 𝑣), the corresponding demand (𝑢, 𝑣) is satisfied by this direct flight. The only demands that are not satisfied in this way 𝑒 , 𝑢 𝑒 ), (𝑢 𝑒 , 𝑎), (𝑢 𝑒 , 𝑏) for each forced edge 𝑒 = (𝑎, 𝑏) and are (𝑢𝑖,1 𝑖,3 𝑖,2 𝑖,3 each 𝑖 ∈ [2𝑛 +4], (𝐶𝑖 , ) for each clause 𝐶𝑖 , and for each variable 𝑥 𝑗 either (𝑥 𝑗 , ) (if 𝑥 𝑗 is set to false) or (𝑥 𝑗 , ) (if 𝑥 𝑗 is set to true).
𝑥1
𝑥 1 𝑥2
𝑥 2 𝑥3
𝐶2
𝑥 3 𝑥4
𝐶1
𝑥1
𝑥 1 𝑥2
𝑥 2 𝑥3
𝑥 4 𝑥5
𝑥5
𝑥 4 𝑥5
𝑥5
𝐶2
𝑥 3 𝑥4
Figure 2: The constructed demand graph for 𝜑 = (𝑥 1 ∨𝑥 3 ∨𝑥 2 ) ∧ (𝑥 3 ∨ 𝑥 4 ∨ 𝑥 5 ) without forced edge gadgets is illustrated above. Demand edges are added from 𝐶 1 and 𝐶 2 to their three literal nodes and to the star, from 𝑥 𝑗 to 𝑥 𝑗 and from 𝑥 𝑗 to 𝑥 𝑗 for all 𝑗 ∈ [𝑛], and from each literal (𝑥 𝑗 or 𝑥 𝑗 ) to the star. Forced edges are depicted with thick lines. Below is the corresponding infrastructure graph for the assignment (𝑥 1, 𝑥 2, 𝑥 3, 𝑥 4, 𝑥 5 ) = (true, false, true, false, false).
𝑢 𝑒1,1
𝑢 𝑒1,2
𝑢 𝑒1,3
𝑢 𝑒2,1
𝑢 𝑒2,2
𝑢 𝑒2,3
𝑎
...
𝑢 𝑒1,1
𝑢 𝑒1,2
𝑢 𝑒1,3
𝑢 𝑒2,1
𝑢 𝑒2,2
𝑢 𝑒2,3
𝑎
... 𝑏
𝑏
Figure 3: Two arms of a forced edge gadget in the demand graph are illustrated on the left. Edge 𝑒 = (𝑎, 𝑏) is forced and depicted with a thick line. On the right, a corresponding infrastructure graph that satisfies the forced edge gadget from the demand graph with the forced edge and 3 pigeons per arm is shown.
The demands within each forced edge gadget are satisfied over 𝑒 → 𝑢 𝑒 → 𝑢 𝑒 ; 𝑢 𝑒 → 𝑢 𝑒 → 𝑎; 2-hop paths with pigeons flying 𝑢𝑖,1 𝑖,2 𝑖,3 𝑖,2 𝑖,3 𝑒 and 𝑢𝑖,3 → 𝑎 → 𝑏, respectively. The demand from each literal 𝑥 𝑗 assigned false (or 𝑥 𝑗 where 𝑥 𝑗 is set to true) to is satisfied over a path 𝑥 𝑗 → 𝑥 𝑗 → (or 𝑥 𝑗 → 𝑥 𝑗 → ). Finally, the demand (𝐶𝑖 , ) is satisfied with a 2-hop flight 𝐶𝑖 → 𝑥 𝑗 → where 𝑥 𝑗 is a variable appearing in 𝐶𝑖 that is assigned true (or 𝑥 𝑗 and 𝑥 𝑗 is set to
Conference’17, July 2017, Washington, DC, USA
false). Note that this variable must exist as otherwise 𝜑 would not be satisfied, which contradicts our assumption. (⇐) Now, assume that (𝐺 𝐷 , (11𝑛 + 15𝑚)) is a yes-instance of 2-hop . We will show that each forced edge gadget can be assigned a score of 6𝑛 + 13 in any solution where each pigeon gives a total score of at most 1. Hence, a total score of at most 𝑘 − (2𝑛 + 3𝑚) (6𝑛 + 13) = 𝑛 can be unassigned and no forced edge gadget can be assigned more than 7𝑛 + 13 as otherwise the solution contains more than 𝑘 pigeons. To define the score of a gadget, we 𝑒 for some distinguish between public and private nodes. A node 𝑢𝑖,𝑗 forced edge 𝑒 and any 𝑖, 𝑗 is called a private node and all remaining nodes (𝐶𝑖 , 𝑥 𝑗 , 𝑥 𝑗 , ) are called public. First, for each private node 𝑣, note that at least one pigeon has to leave from 𝑣 since 𝑣 is a source for some demand. We arbitrarily assign one of the pigeons leaving 𝑣 𝑒 is also (a score of 1) to 𝑣 and the score of any private node 𝑣 = 𝑢𝑖,𝑗 assigned the forced edge gadget for 𝑒. Afterwards, all unassigned pigeons are assigned as follows: If the pigeon flies from 𝑢 to 𝑣 where both 𝑢 and 𝑣 are public nodes, then no node is assigned a score, but if (𝑢, 𝑣) is a forced edge, then a score of one is added to the forced edge gadget for (𝑢, 𝑣). If exactly one of the nodes 𝑢 and 𝑣 is a public node and the other is a private node, then a score of one is assigned to the private node. Finally, if both are public nodes, then a score of 12 is added to each of the two nodes. Note that each pigeons gives a total score of at most one to all nodes and also a total score of at most one to each forced edge gadget. Moreover, since each private node is assigned a score of at least one, each forced edge gadget is assigned at least a score of 6𝑛 + 12. Let 𝑒 = (𝑎, 𝑏) be a forced edge, we show that if no pigeon flies from 𝑎 to 𝑏 in the solution, then each arm of the forced edge gadget is assigned a total score of at least 3.5. Since the number of arms is 2𝑛 + 4 ≥ 2, each forced edge gadget is thus assigned a score of at least 6𝑛 +13. Moreover, if no pigeon flies from 𝑎 to 𝑏, then the forced edge gadget for 𝑒 is assigned a score of at least 3.5(2𝑛 + 4) = 7𝑛 + 14. As argued above, this means that the number of pigeons in the solution is larger than 𝑘, a contradiction. So now assume towards a 𝑒 , 𝑢 𝑒 , 𝑢 𝑒 } is assigned a total score contradiction that any arm {𝑢𝑖,1 𝑖,2 𝑖,3 of less than 3.5 and no pigeon flies from 𝑎 to 𝑏. Since each pigeon assigns a score of 12 or 1 to a node and each node is assigned a score of at least one, the three nodes in the arm are assigned a score of exactly three and each node in the arm is assigned a score of exactly one. Note that this implies that each node has exactly one pigeon in the solution that leaves the respective node. No pigeon 𝑒 to 𝑎 as no pigeon flies from 𝑎 to 𝑏 in the solution and flies from 𝑢𝑖,3 𝑒 , 𝑏) cannot be satisfied by a 2-hop path. For the thus the demand (𝑢𝑖,3 𝑒 to 𝑢 𝑒 as the demand (𝑢 𝑒 , 𝑎) same reason, no pigeon flies from 𝑢𝑖,2 𝑖,3 𝑖,2 𝑒 to 𝑢 𝑒 as the could not be satisfied and no pigeon flies from 𝑢𝑖,1 𝑖,2 𝑒 , 𝑢 𝑒 ) could not be satisfied. Let 𝑐 be the node such demand (𝑢𝑖,1 𝑖,3 𝑒 to 𝑐 in the solution. We make a case that a pigeon flies from 𝑢𝑖,1 𝑒 or not. If 𝑐 ≠ 𝑢 𝑒 , then note that one distinction whether 𝑐 = 𝑢𝑖,3 𝑖,3 𝑒 and one pigeon has to fly from 𝑐 pigeon has to fly from 𝑐 to 𝑢𝑖,2 𝑒 . At most one of these pigeons is fully assigned to 𝑐 and the to 𝑢𝑖,3 other adds a score of at least 12 to the three nodes in the arm, raising 𝑒 . To satisfy the the total score to at least 3.5. So assume that 𝑐 = 𝑢𝑖,3 𝑒 , 𝑢 𝑒 ), one pigeon has to fly from 𝑢 𝑒 to 𝑢 𝑒 . Then, a demand (𝑢𝑖,1 𝑖,2 𝑖,3 𝑖,2 𝑒 to both 𝑎 and 𝑏, contradicting that exactly pigeon has to fly from 𝑢𝑖,2 one pigeon leaves each of the three nodes in the arm. This shows
Matthias Bentert, Shay Kutten, Darya Melnyk, Tijana Milentijević, and Stefan Schmid
that if no pigeon flies from 𝑎 to 𝑏, then the total score of each arm is at least 3.5 and the number of pigeons in the solution is larger than 𝑘. Finally, note that since we may assume that a pigeon flies from 𝑎 to 𝑏 for each forced edge 𝑒 = (𝑎, 𝑏), it holds that the score assigned to the forced edge gadget for 𝑒 is at least 6𝑛 + 13 and each pigeon that flies from a public node to a private node in the gadget increases the score by one. To conclude the proof, consider the set of all pigeons in a solution that do not fly from 𝑎 to 𝑏 for some forced edge (𝑎, 𝑏) and that do not start in a private node. These are all but at least (2𝑛 + 3𝑚) (6𝑛 + 13) = 𝑘 − 𝑛. Hence, these are at most 𝑛 pigeons. Assume towards a contradiction that for some variable 𝑥 𝑗 , none of these pigeons starts at 𝑥 𝑗 or 𝑥 𝑗 . Then, the only pigeons leaving 𝑥 𝑗 and 𝑥 𝑗 are the pigeons flying the forced edges (𝑥 𝑗 , 𝑥 𝑗 ) and (𝑥 𝑗 , 𝑥 𝑗 ). Thus, the demands (𝑥 𝑗 , ) and (𝑥 𝑗 , ) are not satisfied, a contradiction. Thus for each variable 𝑥 𝑗 , exactly one of the 𝑛 pigeons flies from 𝑥 𝑗 or from 𝑥 𝑗 . We define a truth assignment by setting 𝑥 𝑗 = true if 𝑥 𝑗 is the node that the additional pigeon flies from and to false otherwise. It remains to show that the constructed assignment satisfies 𝜑. To this end, consider any clause 𝐶𝑖 and the demand (𝐶𝑖 , ). As no pigeons are left to fly from 𝐶𝑖 to directly and the only pigeons flying from 𝐶𝑖 are to the three nodes representing literals that appear in 𝐶𝑖 (the three forced edges incident to 𝐶𝑖 ), it must hold that a pigeon flies from one of these three nodes to . These has to be one of the 𝑛 pigeons that do not fly forced edges and do not start in a private node. Hence, at least one of the three nodes is assigned an additional pigeon and by construction, the assignment of that variable satisfies 𝐶𝑖 . Since all variables are satisfied in this way be the assignment, 𝜑 is satisfied and the original instance of 3SAT is a yes-instance. This concludes the proof. □ In the following, we will present an ILP formulation of the 2hop problem. To simplify the formulation, we make use of the following lemma: Lemma 1. Any optimal solution for both Multihop 2-hop requires at most 2(𝑛 − 1) pigeons.
and
Proof. We show this statement by presenting a solution that uses 2(𝑛 − 1) pigeons for any demand graph. We build an infrastructure graph as a directed cycle, where the nodes along the cycle are following some arbitrary order. Assume WLOG that the nodes are ordered as 𝑣 1, 𝑣 2, . . . , 𝑣𝑛 along the cycle. We place pigeons at the nodes as follows: two pigeons at each node 𝑣𝑖 , 𝑖 ∈ [𝑛 − 2] with a home at 𝑣𝑖+1 , one pigeon at 𝑣𝑛−1 with a home at 𝑣𝑛 , and one pigeon at 𝑣𝑛 with a home at 𝑣 1 . We release the pigeons sequentially, one at a time, starting with node 𝑣 1 . This pigeon carries the demand from 𝑣 1 to all other nodes in the graph. Once the pigeon arrives at 𝑣 2 , the remaining demand from 𝑣 1 is forwarded with the next pigeon, together with the demand from 𝑣 2 to all other nodes. After making one cycle through all nodes, node 𝑣 1 will receive a pigeon with demands from nodes 𝑣 2, . . . , 𝑣𝑛 with destinations in 𝑣 1, . . . , 𝑣𝑛−1 . Observe that at this point, the demand of node 𝑣 1 has been delivered to all nodes. However, the demand of node 𝑣𝑛 has only been delivered to node 𝑣 1 so far. Therefore, we need to continue forwarding the remaining demand through the cycle, up to
Algorithms for Carrier Pigeons
∑︁
Conference’17, July 2017, Washington, DC, USA
𝑖 𝑥𝑢,𝑣 ≤1
∀𝑖 ∈ [2𝑛 − 2]
𝑢,𝑣 ∈𝑉
(1) ∑︁ 𝑖 ∈ [2𝑛−2]
𝑖 (𝑥𝑢,𝑣 +
∑︁
𝑖 𝑦𝑢,𝑤,𝑣 )≥1
∀(𝑢, 𝑣) ∈ 𝐸
𝑤 ∈𝑉
(2) 𝑖 𝑖 𝑦𝑢,𝑤,𝑣 ≤ 𝑥𝑢,𝑤
𝑖 𝑦𝑢,𝑤,𝑣 ≤
∑︁
∀(𝑢, 𝑣) ∈ 𝐸, 𝑖 ∈ [2𝑛 − 2] (3) 𝑗 𝑥 𝑤,𝑣
between 1 and 2𝑛 − 2). It now only remains to show that each demand is satisfied by the constructed solution. So consider any demand (𝑢, 𝑣). If some pigeon flies from 𝑢 to 𝑣 directly, then the 𝑖 demand is satisfied. Otherwise, 𝑥𝑢,𝑣 = 0 for all 𝑖 ∈ [2𝑛 − 2]. By 𝑖 constraint 2, at least one variable 𝑦𝑢,𝑤,𝑣 is set to true. By constraints 3 𝑗 𝑖 and 4, 𝑥𝑢,𝑤 and 𝑥 𝑤,𝑣 are set to 1 for at least one node 𝑤 and one value 𝑗 ∈ [2𝑛 − 2] with 𝑗 > 𝑖. Thus, the demand (𝑢, 𝑣) is satisfied by the pigeon flying from 𝑢 to 𝑤 at time 𝑖 and the pigeon flying from 𝑤 to 𝑣 at time 𝑗. Since the demand was chosen arbitrarily, all demands are satisfied in this way, and the ILP is therefore correct. □
∀(𝑢, 𝑣) ∈ 𝐸, 𝑖 ∈ [2𝑛 − 2]
𝑗 ∈ [2𝑛−2] 𝑗 >𝑖
3.3 (4)
Figure 4: The constraints of the ILP for 2-hop -
.
node 𝑣𝑛−1 . This construction always forwards all the demand with 2𝑛 − 2 pigeons. □ The following theorem establishes the properties of an ILP we present for the 2-hop problem. Theorem 5. There is an ILP with 𝑂 (𝑛 4 ) variables and 𝑂 (𝑛 3 ) constraints for 2-hop - , where all variables are binary. Proof. Let (𝐺 = (𝑉 , 𝐸), 𝑘) be an instance of 2-hop . We 𝑖 for each pair 𝑢, 𝑣 ∈ construct an ILP with a binary variable 𝑥𝑢,𝑣 𝑖 for each 𝑉 and each 𝑖 ∈ [2𝑛 − 2] and a binary variable 𝑦𝑢,𝑤,𝑣 edge (𝑢, 𝑣) ∈ 𝐸, each node 𝑤 ∈ 𝑉 , and each 𝑖 ∈ [2𝑛 − 2]. The 𝑖 is set to true if the 𝑖 th pigeon flies from 𝑢 to 𝑣. Note variable 𝑥𝑢,𝑣 that by Lemma 1, we may assume that at most 2𝑛 − 2 pigeons are required. The goal is to minimize the number of pigeons, that Í Í 𝑖 , and a solution with 𝑘 pigeons will exist if is, 𝑢,𝑣 ∈𝑉 𝑖 ∈ [2𝑛−2] 𝑥𝑢,𝑣 and only if the goal value is at most 𝑘. The constraints are listed in Figure 4. Since the number of variables is clearly in 𝑂 (𝑛 4 ) and the numbers of constraints is in 𝑂 (𝑛 3 ), it remains to show that the ILP is correct. 𝑖 The variable 𝑦𝑢,𝑤,𝑣 will be set to true if and only if the demand (𝑢, 𝑣) is routed via node 𝑤 and the 𝑖 th pigeon transports the message from 𝑢 to 𝑤. To show correctness, first assume that there is a solution with 𝑘 pigeons. We may assume without loss of generality that no two pigeons fly at the same time, and hence we can order all pigeons in 𝑖 = 1 if and only if the 𝑖 th pigeon the order they fly. Then, we set 𝑥𝑢,𝑣 flies from 𝑢 to 𝑣. For each demand (𝑢, 𝑣), if any pigeon flies from 𝑢 𝑖 to 𝑣 directly, then we set all variables 𝑦𝑢,𝑤,𝑣 = 0. Otherwise, there is at least one node 𝑤 such that a pigeon 𝑖 flies from 𝑢 to 𝑤 and a later pigeon 𝑗 that flies from 𝑤 to 𝑢. We arbitrarily chose one such 𝑖 pair 𝑤, 𝑖 and set 𝑦𝑢,𝑤,𝑣 to true. Note that requirements 1, 2, and 3 are now all satisfied by construction. Moreover, since we assume that for each chosen pair (𝑤, 𝑖) a later pigeon 𝑗 flies from 𝑤 to 𝑣, also constraint 4 is satisfied. In the other direction, assume that there is a solution to the ILP where the goal value is at most 𝑘. We will let a pigeon fly from 𝑖 a node 𝑢 to node 𝑣 in time step 𝑖 if and only if 𝑥𝑢,𝑣 = 1. Note that by construction at most 𝑘 pigeons fly (each at some time step
Multihop -
Solution
Observe that Algorithm 2 is also a (2−
𝑖 ∈ [𝑐 ] Δ(𝐶𝑖 ))-approximation
Í
for the Multihop problem. We next show that also the Multihop problem is NP-hard, and provide an ILP for this problem. The proof of NP-hardness is based on the following three lemmas: Lemma 2. If the demand graph 𝐺 = (𝑉 , 𝐸) is weakly disconnected, then each weakly connected component of 𝐺 can be solved independently for Multihop and the minimum number of pigeons required for 𝐺 is the sum of the minimum numbers of pigeons required for each connected component of 𝐺. Proof. Consider a graph 𝐺 = (𝑉 , 𝐸) with two weakly connected components, denoted 𝐶 1 and 𝐶 2 . Assume by means of contradiction that there is an optimal solution where a pigeon 𝑝 flies from 𝐶 1 to 𝐶 2 . Since 𝐶 1 and 𝐶 2 are weakly disconnected, the destination nodes in 𝐶 1 and 𝐶 2 are disjoint. Consider first the case where 𝑝 has not carried any demand, then the solution was not optimal because it wasted a pigeon. Thus, pigeon 𝑝 must have carried some demand. WLOG, assume that this demand was from sources in 𝐶 1 , and thus has destinations in 𝐶 1 . But then, there must exist at least one other pigeon that carries the demand back from 𝐶 2 to 𝐶 1 . In this case, however, we could have saved at least one pigeon by avoiding a detour over the nodes in 𝐶 2 . This is a contradiction to the fact that we had an optimal solution. □ Lemma 3. If the demand graph 𝐺 = (𝑉 , 𝐸) is weakly connected, then there is always an optimal solution for Multihop in which only one pigeon flies at a time and the pigeon starting at time 𝑖 starts at the same node that the pigeon flying at time 𝑖 − 1 ended their flight for all 𝑖 > 1. Proof. Let 𝑂𝑃𝑇 be an optimal solution. We assume without loss of generality that the pigeon flights in 𝑂𝑃𝑇 are strictly ordered. This is possible, as any two flights that happen at the same time cannot conflict each other and thus can be ordered arbitrarily. For simplicity, let 𝑒𝑖 = (𝑎𝑖 , 𝑏𝑖 ) denote the edge in the infrastructure graph that corresponds to the 𝑖-th pigeon flight in 𝑂𝑃𝑇 and let 𝑂𝑃𝑇𝑖 denote the partial solution only containing the first 𝑖 flights. For each 0 ≤ 𝑖 ≤ |𝑂𝑃𝑇 |, we build a sequence 𝜎𝑖 of pigeon flights satisfying the following two conditions. First, all pigeon flights in a weakly connected component of the infrastructure graph corresponding to 𝜎𝑖 occur consecutive and the starting node of each pigeon is the destination of the previous pigeon unless it is the first flight in a weakly connected component. Second, for each pair (𝑢, 𝑣)
Conference’17, July 2017, Washington, DC, USA
Matthias Bentert, Shay Kutten, Darya Melnyk, Tijana Milentijević, and Stefan Schmid
of nodes (not necessarily terminals), if a pigeon route from 𝑢 to 𝑣 exists in 𝑂𝑃𝑇𝑖 , then it also exists in 𝜎𝑖 , that is, each node has at least as much information after pigeons flew according to 𝜎𝑖 as for 𝑂𝑃𝑇𝑖 . Note that if we succeed with this construction for all 𝑖, then the final sequence 𝜎 |𝑂𝑃𝑇 | is an optimal solution satisfying the requirements of the lemma. Let 𝜎0 be the empty sequence. Note that 𝜎0 fulfills our requirements. Now assume that 𝜎𝑖 −1 fulfills our two requirements. We will show how to construct 𝜎𝑖 . Consider the 𝑖-th pigeon flight 𝑒𝑖 = (𝑎𝑖 , 𝑏𝑖 ). We consider two cases: either both 𝑎𝑖 and 𝑏𝑖 belong to the same weakly connected component of the infrastructure graph corresponding to 𝜎𝑖 −1 or not. If both belong to the same weakly connected component, then consider the subsequence of 𝜎𝑖 −1 of all flights in this component and let 𝑐 be the destination of the last edge in this sequence. Now insert the flight (𝑐, 𝑏𝑖 ) to the end of the subsequence (and shift all flights that appear later in 𝜎𝑖 −1 one time slot back). Note that the length of the sequence increased by exactly one. Moreover, the first requirement is met since 𝑒𝑖 only contains vertices from one weakly connected component and the new flight starts at the last node of the previous subsequence. For the second requirement, note that all nodes who have a pigeon tour to 𝑎𝑖 in 𝜎𝑖 −1 also have a pigeon route to 𝑐. Thus, the pigeon flight (𝑐, 𝑏𝑖 ) ensures that node 𝑏𝑖 learns at least as much information in 𝜎𝑖 as it does in 𝑂𝑃𝑇𝑖 . Now consider the case where 𝑒𝑖 = (𝑎𝑖 , 𝑏𝑖 ) connects two weakly connected components of the infrastructure graph corresponding to 𝜎𝑖 −1 . We build 𝜎𝑖 as follows. First, let 𝜋𝑎 and 𝜋𝑏 be the subsequences of 𝜎𝑖 −1 of all edges in the weakly connected components containing 𝑎𝑖 and 𝑏𝑖 , respectively. Let 𝑐 be the destination of the last edge in 𝜋𝑎 and let 𝑑 be the first starting point of an edge in 𝜋𝑏 . Now, we remove both 𝜋𝑎 and 𝜋𝑏 from 𝜎𝑖 −1 and instead add the sequence 𝜋𝑎 ◦ ((𝑐, 𝑑)) ◦ 𝜋𝑏 at the end. Note that 𝜎𝑖 is longer than 𝜎𝑖 −1 by exactly one and thus has size 𝑖 = |𝑂𝑃𝑇𝑖 |. The first requirement is met by construction and it remains to show that the second requirement is also met. To this end, note that 𝜋𝑎 and 𝜋𝑏 are disjoint and hence no node in either weakly connected component has received any message from a node in the other component. Adding 𝑒𝑖 in 𝑂𝑃𝑇 hence only gives 𝑏𝑖 information about all nodes that 𝑎𝑖 knows about. Note that 𝑐 has knowledge about all nodes appearing in 𝜋𝑎 in 𝜎𝑖 −1 and therefore also in 𝜏𝑎 . Moreover, there is a pigeon flight from 𝑑 to 𝑏𝑖 in 𝜏𝑏 and hence 𝑏𝑖 has full knowledge about all nodes in the component of 𝑎𝑖 in 𝜎𝑖 . Thus, the second requirement is met and this concludes the proof. □ Using these lemmas, we can now show the hardness of the Multihop problem. Note that this result is incomparable to Theorem 4 and neither result immediately implies the other. Theorem 6. The decision variant of Multihop -
is NP-hard.
Proof. We reduce from Vertex Cover. To this end, let (𝐺 = (𝑉 , 𝐸), 𝑘) be an instance of Vertex Cover and assume without loss of generality, that 𝐺 is connected and contains at least one edge. Note that this implies that each node in 𝑉 is incident to at least one edge in 𝐸. We will construct an equivalent instance (𝐺 ′ = (𝑉 , 𝐸 ′ ), 𝑘 ′ ) of Multihop on the same node set 𝑉 as follows. For each edge {𝑢, 𝑣 } ∈ 𝐸, we add the two edges (𝑢, 𝑣) and (𝑣, 𝑢) to 𝐸 ′ .
𝑤
𝑣
𝑢
𝑤
𝑣
𝑢 𝑘 =5
𝑘 =2 𝑥
𝑥
Figure 5: An example instance of Vertex Cover on the left and the corresponding equivalent instance of Multihop on the right.
To conclude the construction, we set 𝑘 ′ = 𝑛 + 𝑘 − 1, where 𝑛 = |𝑉 |. See Figure 5 for an example of the above construction. Since the construction can clearly be computed in polynomial time, it only remains to prove that the constructed instance of Multihop is a yes-instance if and only if the original instance of Vertex Cover is a yes-instance. For this, first assume that the original instance of Vertex Cover is a yes-instance and let 𝐾 be a vertex cover of size at most 𝑘 in 𝐺. Let 𝑠 ∈ 𝐾 be an arbitrary node and let 𝜋 = (𝑢 1, 𝑢 2, . . . , 𝑢 |𝐾 | ) be an arbitrary ordering of the nodes in 𝐾 where 𝑠 is the last node and let 𝜏 = (𝑣 1, 𝑣 2, . . . , 𝑣𝑛− |𝐾 | ) be an arbitrary ordering of the nodes in 𝑉 \ 𝐾. We now construct a solution for the constructed instance of Multihop - . First, we place one pigeon in each node 𝑣𝑖 whose home is node 𝑣𝑖+1 for all 𝑖 < 𝑛 − |𝐾 |. We also place one pigeon in 𝑠 = 𝑢 |𝐾 | whose home is 𝑣 1 and one pigeon in 𝑣𝑛− |𝐾 | whose home is 𝑢 1 . Finally, we place two pigeons in each node 𝑢𝑖 with 1 ≤ 𝑖 < |𝐾 | whose home is 𝑢𝑖+1 . Note that we placed exactly 𝑛 + |𝐾 | − 1 ≤ 𝑛 + 𝑘 − 1 = 𝑘 ′ pigeons. Next, we iteratively let one pigeon fly at a time as follows. We start with a pigeon flying from 𝑢 1 to 𝑢 2 . Then a pigeon flying from 𝑢 2 to 𝑢 3 and so on. Once a pigeon arrives at 𝑢 |𝐾 | = 𝑠, the next pigeon flies from 𝑠 to 𝑣 1 . Afterwards, a pigeon flies from 𝑣 1 to 𝑣 2 , then from 𝑣 2 to 𝑣 3 and so on until a pigeon arrives at 𝑣𝑛− |𝐾 | . Now, the pigeon starting in 𝑣𝑛− |𝐾 | flies to 𝑢 1 . From now on, the second pigeon in each node 𝑢𝑖 iteratively flies to 𝑢𝑖+1 for each 𝑖 < |𝐾 |. We will next show that each demand is satisfied by the above construction. To this end, we show that for each demand (𝑢, 𝑣), there is a subsequence in 𝜋 ◦ 𝜏 ◦ 𝜋 which starts in 𝑢 and ends in 𝑣, where ◦ is the concatenation operation. By construction, any subsequence corresponds to a sequence of pigeon flights that start and end at the respective nodes and are performed in the order given by the sequence. Thus, the information starting in node 𝑢 is moved via pigeons iteratively and finally reaches 𝑣. Note that each demand (𝑢, 𝑣) implies that there is an edge {𝑢, 𝑣 } in 𝐸 and hence at least one of the two nodes is contained in 𝐾. If 𝑢 is contained in 𝐾, then the sought-after subsequence starts in the first occurrence of 𝜋 and ends in either 𝜏 or the second occurrence of 𝜋 depending on whether 𝑣 is contained in 𝑉 \ 𝐾 or in 𝐾. If only 𝑣 is contained in 𝐾, then the subsequence starts in 𝜏 and ends in the second occurrence of 𝜋. Since each node in 𝐾 is contained in 𝜋 and each node in 𝑉 \ 𝐾 is contained in 𝜏 by definition, the subsequences exist and we have successfully constructed a solution. In the other direction, assume that the constructed instance of Multihop is a yes-instance. By Lemma 3, we may assume that a solution describes a walk through 𝐺 ′ as 𝐺 ′ is connected since 𝐺 is connected. Let 𝐾 be the set that includes all nodes in which at
Algorithms for Carrier Pigeons
∑︁
Conference’17, July 2017, Washington, DC, USA
𝑥 𝑣𝑖 ≤ 1
∀𝑖 ∈ [2𝑛]
(5)
𝑖,𝑗 =1 𝑦𝑢,𝑣
∀(𝑢, 𝑣) ∈ 𝐸
(6)
∀(𝑢, 𝑣) ∈ 𝐸 and 𝑖 < 𝑗 ∈ [2𝑛]
(7)
𝑣 ∈𝑉
∑︁ 𝑖< 𝑗 ∈ [2𝑛]
𝑖,𝑗 ≤ 𝑥𝑢𝑖 + 𝑥 𝑣𝑗 2𝑦𝑢,𝑣
Figure 6: The constraints of the ILP for Multihop -
.
least two pigeons are initially placed in a solution as well as the the destination of the last pigeon flight. We will show that 𝐾 is a vertex cover of size at most 𝑘. First, note that since each node in 𝑉 is incident to at least one edge in 𝐸, it also holds for each node 𝑢 that there is a demand of the form (𝑢, 𝑣) ∈ 𝐸 ′ . Hence, at least one pigeon needs to start in each node as otherwise this demand cannot be satisfied. Since the number of pigeons is at most 𝑘 ′ = 𝑛 + 𝑘 − 1, it holds that |𝐾 | ≤ 𝑘 −1+1 (the last +1 comes from the last destination added to 𝐾). Assume towards a contradiction that 𝐾 is not a vertex cover. Then, there is an edge (𝑢, 𝑣) such that neither 𝑢 nor 𝑣 is contained in 𝐾. Then, both of 𝑢 and 𝑣 appear once in the walk described by the assumed solution, as each node appearing twice either ends the walk or has two outgoing edges, which corresponds to two pigeons starting there initially. Since both 𝑢 and 𝑣 appear once, one of the two occurs earlier than the other. Let us assume without loss of generality that 𝑢 appears before 𝑣. Then, the constructed demand (𝑣, 𝑢) (recall that {𝑢, 𝑣 } ∈ 𝐸 and hence (𝑢, 𝑣) ∈ 𝐸 ′ and (𝑣, 𝑢) ∈ 𝐸 ′ ) cannot be satisfied as whenever a pigeon leaves from 𝑣, no pigeon arrives at 𝑢 to deliver the message, a contradiction to the assumption that we started with a solution. Thus, 𝐾 is a vertex cover of size at most 𝑘 and the original instance of Vertex Cover is a yes-instance. This concludes the proof. □ In the following theorem, we present an ILP formulation of the Multihop problem. Theorem 7. There is an ILP with 𝑂 (𝑛 4 ) variables and constraints for Multihop - , where all variables are binary. Proof. Let (𝐺 = (𝑉 , 𝐸), 𝑘) be an instance of Multihop - . By Lemma 2, we may assume that 𝐺 is connected as otherwise, we can solve each connected component independently. We construct an ILP with a binary variable 𝑥 𝑣𝑖 for each 𝑣 ∈ 𝑉 and each 𝑖 ∈ [2𝑛] and a 𝑖,𝑗 binary variable 𝑦𝑢,𝑣 for each edge (𝑢, 𝑣) ∈ 𝐴 and each pair 𝑖, 𝑗 ∈ [2𝑛] Í Í with 𝑖 < 𝑗. The goal is to minimize 𝑣 ∈𝑉 𝑖 ∈ [2𝑛] 𝑥 𝑣𝑖 and a solution with 𝑘 pigeons will exist if and only if there is a solution to the ILP where the goal value is at most 𝑘 + 1. The constraints are listed in Figure 6. Since the number of variables and constraints is clearly both in 𝑂 (𝑛 4 ), it remains to show that the ILP is correct. To this end, we use Lemma 3 and Lemma 1. We may assume that a solution is described by a walk of length at most 2𝑛−1. We simply represent this walk by its at most 2𝑛 nodes. We set 𝑥 𝑣𝑖 = 1 if and only if 𝑣 appears in position 𝑖 in this sequence. Note that Constraint 5 ensures that at most one node appears in each position, and the goal function describes the total number of nodes appearing in the sequence. This
number minus one is then the required number of pigeons as we claimed. So it only remains to show that each demand is satisfied by a 𝑖,𝑗 solution to the ILP. To this end, we use variable 𝑦𝑢,𝑣 to denote that demand (𝑢, 𝑣) is picked up at time step 𝑖 and delivered in time step 𝑗. Constraint 6 ensures that each demand is satisfied in this way, and Constraint 7 ensures that the solution walk is at node 𝑢 at time 𝑖 𝑖,𝑗 and at node 𝑣 at time 𝑗. Note that whenever 𝑦𝑢,𝑣 is set to 1, then in 𝑗 𝑖 order to satisfy Constraint 7, both 𝑥𝑢 and 𝑥 𝑣 have to be set to 1 as well. This concludes the proof. □
4
Future Work
We view this paper as an “Introduction to Pigeon Post Theory” because it opens the door to many research avenues. First, throughout the paper, we focused on unbounded capacity pigeons, and the algorithmic and hardness results were derived under this assumption. An immediate question is how these results change when pigeons have bounded capacities, that is, when each pigeon can carry only a limited amount of information. For the special case of unit capacities, our hardness results for the 2-hop and multihop models seem to remain similar. Whether tight approximation results persist for bounded capacities, or whether new phenomena arise, remains an interesting open problem. Second, while the present work focuses on minimizing the number of pigeons, other cost measures are equally natural. For instance, we could consider every pigeon hop as a time step and try to reduce the time needed to deliver all messages. Additionally, one may consider the cost of transporting pigeons to their remote nodes, possibly allowing batching of deliveries to multiple nodes. Studying such cost-aware variants would further connect the model to classical network design and facility-location problems. Another promising direction concerns the dynamic demand. In this work, demands are assumed to be known in advance. Instead it would be interesting to study settings in which demands arrive over time, either according to a known process, stochastically, or adversarially. This naturally leads to online and competitive variants of the problem. Finally, it would be interesting to investigate distributed algorithms in the pigeon model. Since sending a message consumes a pigeon and effectively removes a directed edge from the infrastructure, one may ask how to perform distributed computation while minimizing pigeon usage, or how to compute without disconnecting the network.
Acknowledgments This work was supported by the German Research Foundation (DFG), SPP 2378 (ReNO-2), 2025-2029.
References [1] Miklós Ajtai. 1994. The complexity of the pigeonhole principle. Combinatorica 14, 4 (1994), 417–433. [2] Chen Avin, Manya Ghobadi, Chen Griner, and Stefan Schmid. 2020. On the complexity of traffic traces and implications. Proceedings of the ACM on Measurement and Analysis of Computing Systems 4, 1 (2020), 1–29. [3] Chen Avin, Kaushik Mondal, and Stefan Schmid. 2020. Demand-aware network designs of bounded degree. Distributed Computing 33, 3 (2020), 311–325. [4] Chen Avin and Stefan Schmid. 2025. Revolutionizing Datacenter Networks via Reconfigurable Topologies. Commun. ACM 68, 6 (2025), 44–53. [5] BBC. 2011. SA pigeon ’faster than broadband’. https://web.archive.org/ web/20110414225332/http://news.bbc.co.uk/2/hi/africa/8248056.stm Accessed: 24/12/2025.
Conference’17, July 2017, Washington, DC, USA
[6] Martin J. Beckmann, C. B. McGuire, and Christopher B. Winsten. 1956. Studies in the Economics of Transportation. Yale University Press. [7] Yossi Ben-Bassat. 2025. A New Israeli test confirms: PEI (Pigeon Enabled Internet) is FASTER than ADSL. https://web.archive.org/web/20080713090722/http://www. notes.co.il/benbasat/5240.asp Accessed: 24/12/2025. [8] Samuel W Bent, Daniel D Sleator, and Robert E Tarjan. 1985. Biased search trees. SIAM J. Comput. 14, 3 (1985), 545–568. [9] Zhi Cao and Eric Masanet. 2022. Material efficiency to tackle the sand crisis. Nature Sustainability 5, 5 (2022), 370–371. [10] B. Carpenter and R. Hinden. [n. d.]. Adaptation of RFC 1149 for IPv6. RFC 6249. RFC Editor. doi:10.17487/RFC2549 [11] Benoit Crevier, Jean-François Cordeau, and Gilbert Laporte. 2007. The multidepot vehicle routing problem with inter-depot routes. European journal of operational research 176, 2 (2007), 756–773. [12] Erik D Demaine, Dion Harmon, John Iacono, and Mihai P a ˇ traşcu. 2007. Dynamic optimality—almost. SIAM J. Comput. 37, 1 (2007), 240–251. [13] Josep Díaz, Jordi Petit, and Maria Serna. 2002. A survey of graph layout problems. ACM Computing Surveys (CSUR) 34, 3 (2002), 313–356. [14] United Nations Environment Programme, Edgar E. Gutiérrez-Espeleta, Nyovani Madise, Ying Wang, Robert Watson, Tamiru A. Abiye, Ana Paula Aguiar, Peter Alexander, Barbara Amon, Apoorva Arya, Ghassem Asrar, Lindsay Beevers, Medani Bhandari, Meena Bohara, Gillian Bowser, David Broadstock, Monday Businge, Donovan Campbell, Kateřina Černý Pixová, Lynette Cheah Leila Dagher, Vassilis Daioglou, Jonathan Davies, Mark Elder, Parfait M. Eloundou-Enyegue, et al. 2025. Global Environment Outlook 7: A future we choose – Why investing in Earth now can lead to a trillion-dollar benefit for all. (2025). [15] Shimon Even, Alon Itai, and Adi Shamir. 1975. On the complexity of time table and multi-commodity flow problems. In 16th annual symposium on foundations of computer science (FOCS). IEEE, 184–193. [16] Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat. 2010. Helios: a hybrid electrical/optical switch architecture for modular data centers. In Proceedings of the ACM SIGCOMM 2010 Conference. 339–350. [17] Bernard Fortz and Mikkel Thorup. 2000. Internet traffic engineering by optimizing OSPF weights. In Proceedings IEEE INFOCOM 2000. conference on computer communications. Nineteenth annual joint conference of the IEEE computer and communications societies (Cat. No. 00CH37064), Vol. 2. IEEE, 519–528. [18] Monia Ghobadi, Ratul Mahajan, Amar Phanishayee, Nikhil Devanur, Janardhan Kulkarni, Gireeja Ranade, Pierre-Alexandre Blanche, Houman Rastegarfar, Madeleine Glick, and Daniel Kilper. 2016. Projector: Agile reconfigurable data center interconnect. In Proceedings of the 2016 ACM SIGCOMM Conference. 216– 229. [19] Graham Greene. 1958. Our Man in Havana. Heinemann. [20] Lacy M Greening, Santanu S Dey, and Alan L Erera. 2025. Strengthening Dual Bounds for Multicommodity Capacitated Network Design with Unsplittable Flow Constraints. arXiv preprint arXiv:2512.25018 (2025). [21] Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, and Harald Räcke. 2005. Oblivious routing in directed graphs with random demands. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC ’05). ACM, 193–201. doi:10.1145/1060590.1060619 [22] The highly unofficial CPIP WG. 2001. The highly unofficial CPIP WG. Technical Report. University of Bergen. https://web.archive.org/web/20140215072548/http: //www.blug.linux.no/rfc1149/ Retrieved 24/12/2025. [23] Frank L. Hitchcock. 1941. The Distribution of a Product from Several Sources to Numerous Localities. Journal of Mathematics and Physics 20, 1–4 (1941), 224–230. [24] Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V Le, Yonghui Wu, et al. 2019. Gpipe: Efficient training of giant neural networks using pipeline parallelism. Advances in neural information processing systems 32 (2019). [25] David A Huffman. 2007. A method for the construction of minimum-redundancy codes. Proceedings of the IRE 40, 9 (2007), 1098–1101. [26] UNICEF IFAD et al. 2017. The state of food security and nutrition in the world 2017. FAO;.
Matthias Bentert, Shay Kutten, Darya Melnyk, Tijana Milentijević, and Stefan Schmid
[27] Leonard Kleinrock. 1976. Queueing Systems, Volume II: Computer Applications. John Wiley & Sons. [28] Vanessa Lamb. 2023. Constructing the global sand crisis: Four reasons to interrogate crisis and scarcity in narrating extraction. The Extractive Industries and Society 15 (2023), 101282. [29] Jean-Pierre Luminet. 2021. Closed Timelike Curves, Singularities and Causality: A Survey from Gödel to Chronological Protection. Universe 7, 1 (Jan. 2021), 12. doi:10.3390/universe7010012 [30] Carolina Elisabet Masin, Alejandra Duran, Cristina Susana Zalazar, and Maria Emilia Fernandez. 2024. Composting-vermicomposting of pigeon dropping waste: A contribution to the reduction of urban contamination. (2024). [31] Alberto Medina, Nina Taft, Kavé Salamatian, Supratik Bhattacharyya, and Christophe Diot. 2002. Traffic matrix estimation: existing techniques and new directions. In Proceedings of the ACM SIGCOMM 2002 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM ’02). ACM, 161–174. doi:10.1145/633025.633041 [32] Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, et al. 2021. Efficient large-scale language model training on gpu clusters using megatron-lm. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–15. [33] Pascal Peduzzi, Josefine Reimer Lynggaard, and Stephanie Chuah. 2022. Sand and sustainability: 10 strategic recommendations to avert a crisis. (2022). [34] Leon Poutievski, Omid Mashayekhi, Joon Ong, Arjun Singh, Mukarram Tariq, Rui Wang, Jianan Zhang, Virginia Beauregard, Patrick Conner, Steve Gribble, et al. 2022. Jupiter evolving: transforming google’s datacenter network via optical circuit switches and software-defined networking. In Proceedings of the ACM SIGCOMM 2022 Conference. 66–85. [35] Hungry Beast Real Human Stories. 2010. Pigeons vs. Australian Internet. url: https://www.youtube.com/watch?v=ci2bFFGM8T8. Accessed: 24/12/2025. [36] Grégory Salle. 2022. On the ‘global sand crisis’: From capital accumulation to ecological planning. (2022). [37] Stefan Schmid, Chen Avin, Christian Scheideler, Michael Borokhovich, Bernhard Haeupler, and Zvi Lotker. 2015. Splaynet: Towards locally self-adjusting networks. IEEE/ACM Transactions on Networking 24, 3 (2015), 1421–1433. [38] Claude E Shannon. 1949. Communication theory of secrecy systems. The Bell system technical journal 28, 4 (1949), 656–715. [39] Sharanpreet Singh, Jaswinder Singh, Amandeep Kaur, Jagroop Kaur, Adarsh Pal Vig, and Sartaj Ahmad Bhat. 2019. Nutrient recovery from pigeon dropping by using exotic earthworm Eisenia fetida. Sustainable Chemistry and Pharmacy 12 (2019), 100126. [40] Daniel Dominic Sleator and Robert Endre Tarjan. 1985. Self-adjusting binary search trees. Journal of the ACM (JACM) 32, 3 (1985), 652–686. [41] Neal Stephenson. 1999. Criptonomicon. Avon. team. 2002. Google PigeonRank. url: [42] Google http://www.google.com/technology/pigeonrank.html. Accessed: 24/12/2025. [43] BBC News Technology. 2016. Pigeons vs. Australian Internet. url: Pigeon flies past broadband in data speed race. Accessed: 24/12/2025. [44] Niren Tolsi. 2009. Winston the homing pigeon draws tweets of support. url: https://mg.co.za/article/2009-09-10-winston-the-homing-pigeon-drawstweets-of-support/. Accessed: 24/12/2025. [45] Paolo Toth and Daniele Vigo. 2002. The vehicle routing problem. SIAM. [46] Gilbert S Vernam. 1926. Cipher printing telegraph systems: For secret wire and radio telegraphic communications. Journal of the AIEE 45, 2 (1926), 109–115. [47] D. Waitzman. 1990. A Standard for the Transmission of IP Datagrams on Avian Carriers. RFC 1149. RFC Editor. doi:10.17487/RFC1149 [48] Wikipedia contributors. 2014. Google Pigeon Protocol. https: //en.wikipedia.org/wiki/Google_Pigeon#:~:text=Google%20Pigeon%20is% 20the%20code,local%20listings%20in%20a%20search. [Online; accessed 24-December-2025]. [49] Wikipedia contributors. 2025. Pigeon post. https://en.wikipedia.org/wiki/ Pigeon_post?utm_source=chatgpt.com [Online; accessed 24-December-2025].