The Complexity Landscape of Dynamic Distributed Subgraph Finding

We consider four types of topological changes: node insertions, node deletions, edge insertions, and edge deletions. In the case of a node insertion, the adversary may connect the new node to an arbitrary subset of the existing nodes. Each node $u$ can only indirectly deduce that a topological change has occurred by comparing its list of neighbors $N_{G^i}(u)$ in the current round $i$ and its list of neighbors $N_{G^{i-1}}(u)$ in the previous round $i-1$. At most one topological change can occur in each round. Suppose at some round $i$, node $u$ detects that exactly one new node $v$ appears in its neighborhood list, then from this information only, node $u$ cannot distinguish whether edge $\{u,v\}$ is added or node $v$ is added in round $i$, if we are in the model where both edge insertions and node insertions are allowed. Similarly, suppose node $u$ detects that exactly one node $v$ disappears in its list. In that case, $u$ cannot distinguish whether edge $\{u,v\}$ is deleted or node $v$ is deleted, if we are in the model where both edge deletions and node deletions are allowed.

An algorithm can be designed to handle only one type of topological change or any combination of them. Throughout this paper, we only consider deterministic algorithms. We say an algorithm $𝒜$ is an $r$-round algorithm if $𝒜$ works in the following setting.

• $\mathrm{■}$

  Each topological change is followed with at least $r-1$ quiet rounds. Specifically, if a topological change occurs in round $i$, then we must have $G^i=G^{i+1}=\mathrm{\cdots }=G^{i+r-1}$. Rounds $i+1,\mathrm{\dots },i+r-1$ are quiet in the sense that no topological changes occur in these rounds.

• $\mathrm{■}$

  The output w.r.t. $G^i$ must be computed correctly by round $i+r-1$.

A one-round algorithm is not called a zero-round algorithm because, within each round, topological change occurs before any communication takes place. This setup allows the nodes to have one round of communication between the topological change and deciding the output within a single round. For example, if an edge $\{u,v\}$ is inserted in a round, then $u$ and $v$ can immediately communicate with each other along this edge within the same round.

We emphasize that all our algorithms and lower bounds in this paper are deterministic, although many of our lower bounds also extend to the randomized setting, as shown in the full version [15] of the paper.

The $r$-round bandwidth complexity of a problem is defined as the minimum bandwidth $B$ for which there exists an $r$-round algorithm solving that problem with bandwidth $B$. Fix a target subgraph $H$, a round number $r$, and some type of topological changes. Let $B_{\text{MemList}}$, $B_{\text{MemDetect}}$, $B_{\text{List}}$, and $B_{\text{Detect}}$ denote the $r$-round bandwidth complexities of $\text{MemList}(H)$, $\text{MemDetect}(H)$, $\text{List}(H)$, and $\text{Detect}(H)$, respectively. The following observations were made by Bonne and Censor-Hillel [6].

In this paper, we only focus on nontrivial target subgraphs $H$, meaning that we implicitly assume that $H$ is connected and contains at least three nodes:

• $\mathrm{■}$

  If $H$ is not connected, then all four problems are trivially impossible to solve, as we allow the network to be disconnected.

• $\mathrm{■}$

  If $H$ is connected with exactly two nodes, then all four problems are trivially solvable with zero communication.

For example, when we say that the one-round bandwidth complexity of $\text{MemDetect}(K_s)$ under edge insertions is $\mathrm{\Omega }(\log \log n)$, we implicitly assume that $s\ge 3$.

In [6, Open question 1] and [6, Open question 3], Bonne and Censor-Hillel asked for the tight bound on the one-round bandwidth complexity of membership-detection for triangles and larger cliques under edge insertions only. For triangles, they obtained two upper bounds $O(\log n)$ and $O(\sqrt{\mathrm{\Delta }\log n})$ [6]. For larger cliques, they obtained an upper bound $O(\sqrt{n})$ which works even for the membership-listing problem [6]. In this work, we show that these problems admit a bandwidth lower bound of $\mathrm{\Omega }(\log \log n)$, which holds even in bounded-degree networks.

Prior to our work, no lower bound was known for this problem. Moreover, we complement our lower bound with a new $O(\log \log n)$-bandwidth triangle finding algorithm in bounded-degree networks, which is capable of solving the more challenging problem of membership-listing.

Combining Theorem 1.3 and Theorem 1.4, we obtain a tight bound of membership-detection for triangles in bounded-degree dynamic networks.

The remaining two open questions of Bonne and Censor-Hillel [6] considered the model where two types of topological changes are allowed. Specifically, [6, Open question 2] and [6, Open question 5] asked for the tight bound on the one-round bandwidth complexity of the listing problem for triangles and larger cliques under both edge insertions and node insertions. Previously, these problems were known to have an upper bound of $O(\log n)$ [6]. In this work, we show that these problems admit a bandwidth lower bound of $\mathrm{\Omega }(\log \log \log n)$, which applies to the easier problem of detection and holds in bounded-degree networks.

Same as Theorem 1.3, prior to our work, no lower bound was known for this problem. Interestingly, we are also able to match this lower bound with a new $O(\log \log \log n)$-bandwidth algorithm for listing triangles in bounded-degree networks.

Combining Theorem 1.6 and Theorem 1.7, we obtain a tight bound for triangle detection in bounded-degree dynamic networks.

It appears to be a challenging task to extend the current results beyond cliques. In the static setting, while the round complexity for $k$-clique listing has been settled [9, 12, 16, 17, 22, 30], far less is known about target subgraphs that are not cliques. In the dynamic setting, Bonne and Censor-Hillel [6] highlighted that cliques are unique in that they can be found trivially in one round if bandwidth is unrestricted.

In this work, we demonstrate that it is possible to achieve meaningful results beyond cliques, despite the inherent difficulties. For subgraph finding beyond cliques, we present a complete characterization of the bandwidth complexity for the membership-listing problem across all target subgraphs, all numbers of rounds, and all four types of topological changes: node insertions, node deletions, edge insertions, and edge deletions (Table 1). Moreover, we show partial characterizations for one-round membership-detection (Table 2) and listing (Table 3).

Our contribution lies in finding structures in the apparent chaos: We identify relevant graph classes (e.g., complete multipartite graphs) and parameters (e.g., node-edge versions of distance, radius, and diameter) in the area of dynamic distributed subgraph finding. For the cases where a full characterization has yet to be achieved, we identify remaining challenging open problems and outline future research directions. Addressing these challenges will likely require developing novel techniques.

Since for any node $u$ and any edge $\{v,w\}$, $|{\mathrm{dist}}_H(u,w)-{\mathrm{dist}}_H(u,v)|\le 1$, the observation follows directly from the definition of $\mathrm{diam}$ and $\widetilde{\mathrm{diam}}$.

$◀$

The class of complete multipartite graphs plays a crucial role in the study of the complexity landscape of dynamic distributed subgraph finding, as it can be characterized in terms of node-edge diameter or node-edge independence.

In other words, a graph $G$ is node-edge independent if and only if it contains a co-$P_3$ (complement of a path with three nodes) as an induced subgraph. See Figure 1.

If every connected component of $G$ is a clique, then any three nodes selected cannot induce a $P_3$. Conversely, suppose a graph $G$ has no induced $P_3$ and there is a connected component that is not a clique, then there is a pair of disconnected nodes $u$ and $v$ in the same component. The two nodes $u$ and $v$ must be connected by some minimum-length path $P_{uv}$ whose length is at least $2$, since they are in the same connected component. Any three consecutive nodes on the path induce a $P_3$, which is a contradiction. $◀$

Observe that a graph is complete multipartite if and only if its complement is a disjoint union of cliques. Hence Lemma 2.7 implies that a graph $G$ is not node-edge independent $\iff$ $G$ does not contain a co-$P_3$ as an induced subgraph $\iff$ complement of $G$ is $P_3$-free $\iff$ $G$ is complete multipartite. $◀$

Now we characterize complete multipartite graphs in terms of node-edge diameter.

If $\widetilde{\mathrm{diam}}(H)=2$, then $H$ is not node-edge independent, since if node $w$ is independent of edge $e=\{u,v\}$, then ${\mathrm{dist}}_H(w,e)\ge 3$. Hence, $H$ is complete multipartite by Lemma 2.8. Conversely, suppose $H$ is complete multipartite, then it is not node-edge independent, and ${\mathrm{dist}}_H(w,e)\le 2$ for all $w\in V(H)$ and $e\in E(H)$. Hence, $\widetilde{\mathrm{diam}}(H)\le 2$. Since $H$ has at least three nodes, for any edge $e$, there is a node $w$ such that $w\notin e$. We have ${\mathrm{dist}}_H(w,e)\ge 2$ and $\widetilde{\mathrm{diam}}(H)\ge 2$. $◀$

Suppose ${\mathrm{dist}}_H(w,e)=\widetilde{\mathrm{diam}}(H)$, for a node $w\in V(H)$ and an edge $e=\{u,u^{\prime }\}\in E(H)$. Consider the following dynamic graph $𝒢$ under edge insertions:

1. 1.

   Initially, $G^0=H-e$.

2. 2.

   At round $1$, consider two cases:

   1. (a)

      The edge $\{u,u^{\prime }\}$ is inserted. Thus $G^1=H$.

   2. (b)

      There is no change. Thus $G^1$ does not contain any subgraph isomorphic to $H$.

Since , within $T$ rounds of communication, node $w$ must receive identical messages in both cases and cannot distinguish two cases, so any correct algorithm requires at least $r_H$ rounds.

A similar proof applies to the case of edge deletion. The only required modification is to start with $G^0=H$ and then replace the insertion of $e$ with the deletion of $e$. $◀$

Next, we define the threshold $r_H^{\prime }$ and show that $r_H^{\prime }$ is a lower bound on the number of rounds needed for $\text{MemList}(H)$ or $\text{MemDetect}(H)$ under node insertions or under node deletions.

Suppose ${\mathrm{dist}}_H(u,w)=\mathrm{diam}(H)$ for nodes $u,w\in V(H)$. For node insertions, we start with the graph $G^0=H-\{u\}$, the subgraph of $H$ induced by $V(H)\setminus \{u\}$. Consider two cases:

1. 1.

   Insert node $u$, along with all its incident edges in $H$. Thus $G^1=H$.

2. 2.

   No topological change.

Since , node $w$ receives the same information within $T$ rounds in both cases. Therefore, for any $T$-round algorithm, $w$ is unable to correctly decide whether $H$ appears. We can use a similar design to prove the case of node deletions: Start with graph $H$, and then at round $1$, either delete node $u$ or do nothing. Since , the same analysis shows that node $w$ cannot decide whether $H$ disappears. $◀$

We show a tighter bound in terms of $r_H$ for the case of node insertions. We remark that the same argument does work for node deletion since nodes are assumed to know the entire topology before any deletion and hence may decide based on one-sided information along the shortest path from $u$ to $x$ in the following example.

According to ˜2.4, we have either $r_H=\widetilde{\mathrm{diam}}(H)-1=\mathrm{diam}(H)-1=r_H^{\prime }$ or $r_H=\widetilde{\mathrm{diam}}(H)-1=\mathrm{diam}(H)=r_H^{\prime }+1$. If $r_H=r_H^{\prime }$, then the proof follows from Theorem 2.13. For the rest of the proof, we focus on the case where $r_H=\widetilde{\mathrm{diam}}(H)-1=\mathrm{diam}(H)=r_H^{\prime }+1$.

Suppose ${\mathrm{dist}}_H(x,e)=\widetilde{\mathrm{diam}}(H)=\mathrm{diam}(H)+1$ for node $x\in V(H)$ and edge $e=\{u,v\}\in E(H)$. We must have ${\mathrm{dist}}_H(x,u)={\mathrm{dist}}_H(x,v)=\mathrm{diam}(H)$. Otherwise, if ${\mathrm{dist}}_H(x,u)\le \mathrm{diam}(H)-1$, then ${\mathrm{dist}}_H(x,e)\le \mathrm{diam}(H)$, contradicting our assumption. Now, consider the following dynamic graph $𝒢$.

1. 1.

   Initially $G^0=H-\{u\}$.

2. 2.

   At round $1$, consider two cases:

   1. (a)

      Node $u$ is inserted with all its incident edges in $H$. Thus $G^1=H$.

   2. (b)

      Node $u$ is inserted with all its incident edges in $H$ excluding $\{u,v\}$. Thus $G^1=H-e$.

For any , node $x$ receives the same information within $T$ rounds in both cases. Therefore, for any $T$-round algorithm, $x$ cannot distinguish the two cases and cannot output correctly. $◀$

By Theorems 2.11 and 2.14 with $T=1$, we know that $r_H\le 1$, or equivalently $\widetilde{\mathrm{diam}}(H)\le 2$, characterizes the class of target subgraphs $H$ that permits one-round $\text{MemList}(H)$ and $\text{MemDetect}(H)$ algorithms for edge insertions, edge deletions, and node insertions. Observe that $\widetilde{\mathrm{diam}}(H)=1$ if and only if $H$ is a single edge, so all non-trivial target subgraphs $H$ satisfy $\widetilde{\mathrm{diam}}(H)\ge 2$. Therefore, ˜2.9 implies that, excluding trivial target subgraphs, complete multipartite graphs are exactly the class of graphs that permits one-round $\text{MemList}(H)$ and $\text{MemDetect}(H)$ algorithms for edge insertions, edge deletions, and node insertions.

We present the core idea underlying the $\mathrm{\Omega }(\log \log n)$ bandwidth lower bound for one-round $\text{MemDetect}(K_s)$ under edge insertions, as shown in Theorem 1.3. For simplicity and clarity, we focus on the case of membership-detecting triangles ($K_3$).

We start by describing the hard instance. Consider a set of $t={\log }^{0.1}n$ nodes $\{x_1,x_2,\mathrm{\dots },x_t\}$ and an independent set $I$. By connecting each $x_i$ to two distinct nodes from $I$, we form $t$ disjoint paths of length two, each resembling a triangle missing one edge. The graph is constructed by edge insertions over $2t$ rounds.

After constructing these paths, a single edge $e$ is inserted. Two scenarios are possible:

• $\mathrm{■}$

  Edge $e$ connects the two endpoints of one of the constructed paths, completing a triangle.

• $\mathrm{■}$

  Edge $e$ connects endpoints from two different paths, forming no triangle.

Let $(a,x_i,b)$ be one such path, and suppose $a$ is one endpoint of the newly inserted edge $e$. To correctly detect whether a triangle has been formed, node $a$ must determine whether the other endpoint of $e$ is node $b$. We show that if the bandwidth of the algorithm is $B=o(\log \log n)$, then no mechanism exists for $a$ to reliably make this distinction.

• $\mathrm{■}$

  Before the insertion of $e$, node $a$ might try to learn $\mathrm{ID}(b)$ through $x_i$ during the initial $2t$ rounds. However, due to bandwidth limitations, $a$ can receive only $O(Bt)=o(\log n)$ bits, which is far too little to uniquely identify $b$ from the space of possible identifiers $[n]$.

• $\mathrm{■}$

  After the insertion of $e$, the two endpoints of $e$ can exchange $B$-bit messages. However, distinguishing whether they are part of the same path among $t$ candidates requires $\mathrm{\Omega }(\log t)$ bits, while $B=o(\log \log n)=o(\log t)$ is again insufficient.

We now turn to the proof of Theorem 1.6, which establishes that the one-round bandwidth complexity of $\text{Detect}(K_s)$ under both node insertions and edge insertions is $\mathrm{\Omega }(\log \log \log n)$. For clarity, we again focus on the case of membership-detecting triangles.

The key reason this lower bound is exponentially smaller than the previous one is that $\text{Detect}(K_s)$ is inherently a much simpler problem than $\text{MemDetect}(K_s)$. In particular, if only edge insertions are allowed, then triangle detection is solvable with bandwidth $B=O(1)$: When an edge is inserted, its endpoints can simply broadcast a signal to their neighbors, and any node receiving two such signals can locally infer the existence of a triangle.

However, this strategy breaks down when node insertions are also permitted. Again, consider a path of the form $(a,x_i,b)$. Now, it is impossible to distinguish whether an edge $\{a,b\}$ has been inserted – completing a triangle – or whether a new node $c$ has been inserted with incident edges $\{a,c\}$ and $\{b,c\}$, where no triangle is created. The ambiguity arises because both scenarios lead to $x_i$ receiving signals from $a$ and $b$.

To formalize this, we use a construction similar to the one from the previous lower bound, but with a smaller parameter: $t={\log }^{0.1}\log n$. We show that distinguishing the two scenarios requires $\mathrm{\Omega }(\log \log \log n)$ bits of bandwidth.

Here is a brief sketch of the argument. We label each pair $(a,b)$, for $a,b\in I$, according to the messages transmitted across the edges $\{a,x_i\}$ and $\{b,x_i\}$ in the first $2t$ rounds, under the assumption that the path $(a,x_i,b)$ is formed. Since each message consists of $B$ bits and communication lasts $2t$ rounds, the total number of distinct labels is $s=2^{O(Bt)}$. Since node insertion is allowed, nodes in $I$ without incident edges are considered as not yet inserted.

A Ramsey-type argument then implies the existence of a subset $\{a,b,c\}\subseteq I$ such that all of $(a,b)$, $(a,c)$, $(c,b)$ receive the same label. This means that, from the perspective of node $x_i$, the insertion of an edge $e=\{a,b\}$ versus the insertion of a node $c$ with two incident edges $\{a,c\}$ and $\{b,c\}$ becomes indistinguishable.

For the proof to work, the set $I$ must be sufficiently large relative to the number of distinct labels, which is $s=2^{O(Bt)}$. This requirement is precisely why we set $t={\log }^{0.1}\log n$ instead of the larger value $t={\log }^{0.1}n$ used in the previous argument, resulting in a weaker lower bound of $\mathrm{\Omega }(\log \log \log n)$. The full proof of Theorem 1.6 is more intricate, as it involves analyzing not only the perspective of each $x_i$, but also the views of the endpoints of the newly inserted edge $e$. For instance, the actual labeling in the proof requires quantifying over all $i\in [t]$, which increases the number of distinct labels to $2^{O(B{t}^2)}$.

To prove Theorem 1.4, we extend the algorithm of Bonne and Censor-Hillel to design a one-round algorithm for $\text{MemList}(K_3)$ under edge insertions with a bandwidth complexity of $O({\mathrm{\Delta }}^2\log \log n)$. In their original algorithm for $\text{MemDetect}(K_3)$, each $d$-bit message is a binary string where the $i$th bit indicates whether an incident edge was inserted $i$ rounds ago. We observe that this binary string can be compactly represented using $O(\mathrm{\Delta }\log d)$ bits: For each recently inserted incident edge, use a number in $[d]$ to indicate its insertion time. Setting $d=\log n$ gives a bandwidth complexity of $O(\mathrm{\Delta }\log \log n)$ for $\text{MemDetect}(K_3)$.

To handle the more demanding $\text{MemList}(K_3)$ problem, we introduce several modifications to the algorithm. Most notably, we must account not only for the edges incident to a node but also for those incident to its neighbors. This additional layer of information increases the size of the message by a factor of $\mathrm{\Delta }$, resulting in a total bandwidth complexity of $O({\mathrm{\Delta }}^2\log \log n)$.

We now turn to the proof of Theorem 1.7, where we design a one-round algorithm for $\text{List}(K_3)$ that handles both edge and node insertions with bandwidth $O(\mathrm{\Delta }\log \log \log n)$. The exponential improvement stems from improving the size of the $O\left(\frac{\mathrm{\Delta }\log n}{d}\right)$-bit message in the algorithm of Bonne and Censor-Hillel [6] to $O\left(\frac{\mathrm{\Delta }\log \log n}{d}\right)$ bits. The purpose of this message is to transmit the list of neighborhood $\mathrm{ID}$s, which contains $O(\mathrm{\Delta }\log n)$ bits of information. As the transmission is done in $d$ rounds, the required message size is $O\left(\frac{\mathrm{\Delta }\log n}{d}\right)$.

Our key idea lies in a new method for identifying triangles. Recall that a core challenge in our $\mathrm{\Omega }(\log \log \log n)$ lower bound proof is to understand the inherent difficulty for a node $x$, with two non-adjacent neighbors $a$ and $b$, to distinguish between the insertion of an edge $\{a,b\}$ and the insertion of a node $c$ with two incident edges $\{a,c\}$ and $\{b,c\}$.

We develop a new algorithm to handle this instance. We let $x$ select an index $i$ such that the $i$th bits of $\mathrm{ID}(a)$ and $\mathrm{ID}(b)$ differ. Nodes $a$ and $b$ then report the $i$th bit of the identifier of their new neighbor. If an edge $\{a,b\}$ is inserted, then the reported bits will differ. If a node $c$, along with two incident edges $\{a,c\}$ and $\{b,c\}$, is inserted, then the bits will match. This comparison allows $x$ to distinguish between the two cases.

Sending an index requires only $O(\log \log n)$ bits, which is exponentially more efficient than sending the full identifier, which requires $O(\log n)$ bits. Consequently, the size of the $O\left(\frac{\mathrm{\Delta }\log n}{d}\right)$-bit message in the algorithm of Bonne and Censor-Hillel [6] is reduced to $O\left(\frac{\mathrm{\Delta }\log \log n}{d}\right)$ bits. Setting $d=\log \log n$ then yields the improved bandwidth complexity $O(\mathrm{\Delta }\log \log \log n)$.

The upper bounds follow from the observation that a node $v$ can list all subgraphs $H$ that contain it once it has an accurate view of its $r_H$-radius neighborhood. A brute-force approach would be to flood the entire graph topology using messages of size $O(n^2)$ after each topological change. Within $r_H$ rounds, this ensures all nodes acquire the required local view. If $r\ge r_H$, this communication can be spread over multiple rounds, reducing the bandwidth requirement to $O(n^2/r)$.

For the special case where $H$ is a complete multipartite graph, we have $r_H=1$. This allows a more efficient approach: Each node simply broadcasts its list of neighbors as a binary string of length $n$, leading to a reduced bandwidth complexity of $O(n/r)$.

We first discuss a general $\mathrm{\Omega }(n/r)$ lower bound for any non-clique subgraph $H$. Let $\{u,v\}$ be a non-edge in $H$. Consider the graph resulting from replacing $u$ with an independent set $U^{\prime }$, so each member of $U^{\prime }$ corresponds to a copy of $H$. We then construct the graph via edge insertions, ensuring that the edges incident to $v$ are added last, leaving $v$ only $O(r)$ rounds to gather information about the graph. For $v$ to list all copies of $H$, it must learn the set $U^{\prime }$, which requires $\mathrm{\Omega }(n)$ bits of information, yielding a lower bound of $\mathrm{\Omega }(n/r)$.

To strengthen the bound to $\mathrm{\Omega }(n^2/r)$ when $H$ is not a complete multipartite graph, we use the fact that such a graph $H$ must contain an edge $e$ and a node $v$ such that neither endpoint of $e$ is adjacent to $v$. Now we apply a similar construction where $e$ is replaced with a bipartite graph, forcing $v$ to learn the bipartite graph in order to list all copies of $H$, which requires $\mathrm{\Omega }(n^2)$ bits of information.

We now consider the case of edge deletions. As with insertions, we have an impossibility result for from Theorem 2.11. For $r\ge r_H$, the $r$-round bandwidth complexity is $\mathrm{\Theta }(n/r)$ whenever $H$ is not a clique.

A key difference between insertions and deletions is that edge insertions can merge disjoint components, potentially introducing many new subgraphs and requiring extensive information dissemination. In contrast, to handle deletions, it suffices to propagate the identifiers of the two endpoints of the deleted edge to a radius of $r_H$, which requires only $O(\log n)$ bits of information. This yields an upper bound of $O((\log n)/r)$.

To prove a matching lower bound, we reuse the construction from the $\mathrm{\Omega }(n/r)$ lower bound. Suppose an edge deletion causes one of the $|U^{\prime }|$ copies of $H$ to disappear. For a node $v$ to correctly identify which copy was affected, it must learn $\mathrm{\Omega }(\log |U^{\prime }|)$ bits. By letting $U^{\prime }$ contain a polynomial number of nodes, this yields the desired $\mathrm{\Omega }((\log n)/r)$ lower bound.

We show that the one-round bandwidth complexity of $\text{MemDetect}(H)$ under edge insertions is $\mathrm{\Omega }(n)$ for any complete multipartite graph $H$ that is neither a star nor a clique. While the corresponding $\mathrm{\Omega }(n/r)$ lower bound for $\text{MemList}(H)$ appears inherently tied to the listing requirement, we demonstrate that, with suitable modifications, the core idea can be adapted to the detection setting.

Since we cannot require a node $v$ to list all copies of $H$ in the constructed graph, we instead frame the argument in a preprocessing-plus-query model. We first build a graph that initially contains no copy of $H$, but is structured so that a copy can be formed in many different ways. The goal is to ensure that, in order for $v$ to detect the presence of $H$ following an edge insertion, it must have already learned a significant amount of information about the initial graph during the construction phase.

Specifically, we identify two non-adjacent nodes $u$ and $v$ in $H$ that share a common neighbor $w$. We construct a graph by removing the edge $\{u,w\}$ from $H$ and replacing node $u$ with an independent set $U^{\prime }$. The graph is built via edge insertions, with the edges incident to $v$ and $w$ added at the end, leaving them only $O(1)$ rounds to learn about $U^{\prime }$. We then insert a new edge $e$ incident to $w$, creating two possible scenarios: If the other endpoint of $e$ lies in $U^{\prime }$, a copy of $H$ is formed; otherwise, it is not. For $v$ to decide correctly, $v$ and $w$ must learn the set $U^{\prime }$ before the insertion of $e$, which requires $\mathrm{\Omega }(n)$ bits of information.

As in the case of $\text{MemList}(H)$, membership-detection becomes significantly easier when the allowed topological change is a deletion rather than an insertion. In particular, we present a one-round $O(1)$-bandwidth algorithm for $\text{MemDetect}(H)$ that applies to any complete multipartite graph $H$, improving upon the $O(\log n)$ bound required for $\text{MemList}(H)$ under the same conditions.

For clarity, we describe our algorithm for the special case $H=C_4$, which captures the key ideas behind the more general algorithm that works for an arbitrary complete multipartite graph $H$. The core observation is that to detect a $C_4$, it suffices for each node $w$ to maintain, for every pair of its neighbors $u$ and $v$, the number of common neighbors they share, excluding $w$. Each such shared neighbor corresponds to a distinct copy of $C_4$ containing $w$, $u$, and $v$.

Maintaining these counters requires only one-bit messages. When a node detects that one of its neighbors has been deleted, it sends a one-bit signal to all its remaining neighbors. If a node $w$ receives such a signal from two neighbors $u$ and $v$ in the same round, it decrements the counter for the pair $\{u,v\}$ by one.