# Messy Broadcasting in Grid
## 2 Related Work  
Refs. [7; 8] offer a comprehensive analysis of general upper and lower bounds on messy broadcasting, making them an excellent resource for gaining a foundational understanding of the subject. For simpler graph structures like path, cycle, and complete graphs, the average (expected) messy broadcast time has been studied instead of the worst-case scenario, as explored in [9]. Table 1 is an excerpt from a table presented in [7], highlighting a comparison between known broadcast time bounds for classical and messy models in various simple graph structures. It turns out that finding the broadcast time in both classical and messy models is a very difficult task, in terms of NP-hardness, lower bounds of approximation algorithms, and the extremely limited classes of graphs for which the broadcast time is known. Ref. [1] \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Graph**} & \(\mathbf{M_{3}}\) & \(\mathbf{M_{1}}\) **and \(\mathbf{M_{2}}\)** & **Classical** & **Classical** \\  & **Upper Bound** & **Upper Bound** & **Lower Bound** & **Upper Bound** \\ \hline \(K_{n}\) & \(n-1\) & \(n-1\) & \(\lceil\log n\rceil\) & \(\lceil\log n\rceil\) \\ \(P_{n}\) & \(2n-3\) & \(n-1\) & \(n-1\) & \(n-1\) \\ \(C_{n}\) & \(n-1\) & \(\lceil\frac{n}{2}\rceil\) & \(\lceil\frac{n}{2}\rceil\) & \(\lceil\frac{n}{2}\rceil\) \\ \(Q_{d}\) & \(\frac{d(d+1)}{2}\) & \(\frac{d(d-1)}{2}+1\) & \(d\) & \(d\) \\ \(T_{d,h}\) & \((d+1)(2h-3)\) & \(d(2h-3)\) & \((d+1)(h-1)-1\) & \((d+1)(h-1)-1\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of messy and classical broadcast time bounds, as illustrated by a partial table adapted from [7]. Figure 2: Grid graphs \(G[4\times 5]\) and \(G[3\times 4\times 3]\). summarizes these difficulties for classical models, providing the classes of graphs whose broadcast time is known, though it might not be absolutely complete. Refs. [10; 11] offer new contributions to the study of complexity in finding broadcast time; the former investigates parameterized complexity, while the latter proves a double exponential lower bound when parameterized by the solution size. As a result, there are papers like [12; 13; 14; 15; 16; 17] that focus on providing good heuristic algorithms. Meanwhile, messy models remain less studied, highlighting the need for further research in this area. Assumptions similar to those in messy broadcasting are made in [18], in the context of hot-potato routing; in [19; 20; 21], where a similar broadcasting in a particular type of network called _radio networks_ is studied, and in [22; 23; 24], where the additional assumption that the vertices _know_ the topology of the network is assumed, for example, a vertex would know that it is in a hypercube. _Blind broadcasting_, which is similar to messy broadcasting under model \(M_{2}\), is studied in [25]. In \(M_{2}\), the process ends when all the vertices are informed. In blind broadcasting, the process continues until all of the edges are used. A related probabilistic problem is studied in [26]. In this model, each informed vertex forwards the message to a randomly chosen neighbor in a similar fashion. The goal is to determine the time by which all the vertices of an \(n\) vertex graph would know the message with the probability of \(1-\frac{1}{n}\). A list-based random model called \"_quasirandom rumor spreading_\" is first defined in [27], which is close to the messy model \(M_{3}\). For this model, Ref. [28] has proved that if the vertices do not know the status of their neighbors, the worst broadcast time is computable from originator \(v\) to destination \(u\) in \(O(m+n\lg n)\)-time, where \(n\) is the number of vertices and \(m\) is the number of edges. Otherwise, if the status of the neighbors is known, the problem is inapproximable within a \((\frac{1}{n})^{0.5-\epsilon}\) multiplicative factor, for any \(\epsilon>0\). Ref. [29] provides a heuristic algorithm for computing universal list broadcast time using a genetic algorithm.