text: This paper provides an in-depth study of the fundamental problems of finding small subgraphs in distributed dynamic networks. While some problems are trivially easy to handle, such as detecting a triangle that emerges after an edge insertion, we show that, perhaps somewhat surprisingly, other problems exhibit a wide range of complexities in terms of the trade-offs between their round and bandwidth complexities. In the case of triangles, which are only affected by the topology of the immediate neighborhood, some end results are: The bandwidth complexity of @math -round dynamic triangle detection or listing is @math . The bandwidth complexity of @math -round dynamic triangle membership listing is @math for node edge deletions, @math for edge insertions, and @math for node insertions. The bandwidth complexity of @math -round dynamic triangle membership detection is @math for node edge deletions, @math for edge insertions, and @math for node insertions. Most of our upper and lower bounds are . Additionally, we provide almost always tight upper and lower bounds for larger cliques.
  @cite_18: In this paper we present distributed property-testing algorithms for graph properties in the CONGEST model, with emphasis on testing subgraph-freeness. Testing a graph property P means distinguishing graphs G = (V,E) having property P from graphs that are epsilon-far from having it, meaning that epsilon|E| edges must be added or removed from G to obtain a graph satisfying P. We present a series of results, including: - Testing H-freeness in O(1 epsilon) rounds, for any constant-sized graph H containing an edge (u,v) such that any cycle in H contain either u or v (or both). This includes all connected graphs over five vertices except K_5. For triangles, we can do even better when epsilon is not too small. - A deterministic CONGEST protocol determining whether a graph contains a given tree as a subgraph in constant time. - For cliques K_s with s >= 5, we show that K_s-freeness can be tested in O(m^(1 2-1 (s-2)) epsilon^(-1 2-1 (s-2))) rounds, where m is the number of edges in the network graph. - We describe a general procedure for converting epsilon-testers with f(D) rounds, where D denotes the diameter of the graph, to work in O((log n) epsilon)+f((log n) epsilon) rounds, where n is the number of processors of the network. We then apply this procedure to obtain an epsilon-tester for testing whether a graph is bipartite and testing whether a graph is cycle-free. Moreover, for cycle-freeness, we obtain a corrector of the graph that locally corrects the graph so that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph in many places in the case that the graph is far from having the property. These protocols extend and improve previous results of [Censor- 2016] and [ 2016].
  @cite_14: We study property testing in the context of distributed computing, under the classical CONGEST model. It is known that testing whether a graph is triangle-free can be done in a constant number of rounds, where the constant depends on how far the input graph is from being triangle-free. We show that, for every connected 4-node graph H, testing whether a graph is H-free can be done in a constant number of rounds too. The constant also depends on how far the input graph is from being H-free, and the dependence is identical to the one in the case of testing triangle-freeness. Hence, in particular, testing whether a graph is (K_4 )-free, and testing whether a graph is (C_4 )-free can be done in a constant number of rounds (where (K_k ) denotes the k-node clique, and (C_k ) denotes the k-node cycle). On the other hand, we show that testing (K_k )-freeness and (C_k )-freeness for (k 5 ) appear to be much harder. Specifically, we investigate two natural types of generic algorithms for testing H-freeness, called DFS tester and BFS tester. The latter captures the previously known algorithm to test the presence of triangles, while the former captures our generic algorithm to test the presence of a 4-node graph pattern H. We prove that both DFS and BFS testers fail to test (K_k )-freeness and (C_k )-freeness in a constant number of rounds for (k 5 ).
  @cite_5: In the subgraph-freeness problem, we are given a constant-size graph @math , and wish to determine whether the network contains @math as a subgraph or not. The relaxation of the problem only requires us to distinguish graphs that are @math -free from graphs that are @math -far from @math -free, meaning an @math -fraction of their edges must be removed to obtain an @math -free graph. Recently, Censor-Hillel et. al. and showed that in the property-testing regime it is possible to test @math -freeness for any graph @math of size 4 in constant time, @math rounds, regardless of the network size. However, Fraigniaud et. al. also showed that their techniques for graphs @math of size 4 cannot test @math -cycle-freeness in constant time. In this paper we revisit the subgraph-freeness problem and show that @math -cycle-freeness, and indeed @math -freeness for many other graphs @math comprising more than 4 vertices, can be tested in constant time. We show that @math -freeness can be tested in @math rounds for any cycle @math , improving on the running time of @math of the previous algorithms for triangle-freeness and @math -freeness. In the special case of triangles, we show that triangle-freeness can be solved in @math rounds independently of @math , when @math is not too small with respect to the number of nodes and edges. We also show that @math -freeness for any constant-size tree @math can be tested in @math rounds, even without the property-testing relaxation. Building on these results, we define a general class of graphs for which we can test subgraph-freeness in @math rounds. This class includes all graphs over 5 vertices except the 5-clique, @math . For cliques @math over @math nodes, we show that @math -freeness can be tested in @math rounds, where @math is the number of edges.
  @cite_16: Given an undirected graph and 0 ≤ e ≤ 1, a set of nodes is called e-near clique if all but an e fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size e-near clique if there exists an e3-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n−Ω(1) in O(log n) time, and the algorithm also works if the graph contains a clique of size Ω(n logα log n) for some α ∈ (0,1). Our approach is based on a new idea of adapting property testing algorithms to the distributed setting.
  @cite_10: We provide a thorough study of distributed property testing – producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called dense graph testing model we emulate sequential tests for nearly all graph properties having 1-sided tests, while in the general and sparse models we obtain faster tests for triangle-freeness, cycle-freeness and bipartiteness, respectively. In addition, we show a logarithmic lower bound for testing bipartiteness and cycle-freeness, which holds even in the LOCAL model.
  @cite_17: 
summary: A related problem is property-testing of subgraphs, where the nodes need to determine, for a given subgraph @math , whether the graph is @math -free or from being @math -free @cite_10 @cite_18 @cite_17 @cite_5 @cite_14 @cite_16 .