We initiate a thorough study of -- producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called testing model we emulate sequential tests for nearly all graph properties having @math -sided tests, while in the and models we obtain faster tests for triangle-freeness and bipartiteness respectively. In most cases, aided by parallelism, the distributed algorithms have a much shorter running time as compared to their counterparts from the sequential querying model of traditional property testing. The simplest property testing algorithms allow a relatively smooth transitioning to the distributed model. For the more complex tasks we develop new machinery that is of independent interest. This includes a method for distributed maintenance of multiple random walks.
Finding induced subgraphs is a crucial task and has been studied in several different distributed models (see, e.g., @cite_25 @cite_12 @cite_3 @cite_7 ). Notice that for subgraphs, having instances of the desired subgraph can help speedup the computation, as in @cite_7 . This is in contrast to algorithms that perform faster if there are or only instances, as explained above, which is why we test for, e.g., the property of being , rather for the property of triangles. (Notice that these are not the same, and in fact every graph with @math or more vertices is @math -close to having a triangle.)
@cite_7 @cite_3 @cite_25 @cite_12
2949944845 2950813619 2295809089 2045760791
Let G = (V,E) be an n-vertex graph and M_d a d-vertex graph, for some constant d. Is M_d a subgraph of G? We consider this problem in a model where all n processes are connected to all other processes, and each message contains up to O(log n) bits. A simple deterministic algorithm that requires O(n^((d-2) d) log n) communication rounds is presented. For the special case that M_d is a triangle, we present a probabilistic algorithm that requires an expected O(ceil(n^(1 3) (t^(2 3) + 1))) rounds of communication, where t is the number of triangles in the graph, and O(min n^(1 3) log^(2 3) n (t^(2 3) + 1), n^(1 3) ) with high probability. We also present deterministic algorithms specially suited for sparse graphs. In any graph of maximum degree Delta, we can test for arbitrary subgraphs of diameter D in O(ceil(Delta^(D+1) n)) rounds. For triangles, we devise an algorithm featuring a round complexity of O(A^2 n + log_(2+n A^2) n), where A denotes the arboricity of G. In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an @math round matrix multiplication algorithm, where @math is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include: -- triangle and 4-cycle counting in @math rounds, improving upon the @math triangle detection algorithm of [DISC 2012], -- a @math -approximation of all-pairs shortest paths in @math rounds, improving upon the @math -round @math -approximation algorithm of Nanongkai [STOC 2014], and -- computing the girth in @math rounds, which is the first non-trivial solution in this model. In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles. We study the message size complexity of recognizing, under the broadcast congested clique model, whether a fixed graph H appears in a given graph G as a minor, as a subgraph or as an induced subgraph. The n nodes of the input graph G are the players, and each player only knows the identities of its immediate neighbors. We are mostly interested in the one-round, simultaneous setup where each player sends a message of size @math to a referee that should be able then to determine whether H appears in G. We consider randomized protocols where the players have access to a common random sequence. We completely characterize which graphs H admit such a protocol. For the particular case where H is the path of 4 nodes, we present a new notion called twin ordering, which may be of independent interest. We consider a distributed task allocation problem in which m players must divide a set of n tasks between them. Each player i receives as input a set Xi of tasks such that the union of all input sets covers the task set. The goal is for each player to output a subset Yi ⊆ Xi, such that the outputs (Y1,...,Ym) form a partition of the set of tasks. The problem can be viewed as a distributed one-shot variant of the well-known k-server problem, and we also show that it is closely related to the problem of finding a rooted spanning tree in directed broadcast networks. We study the communication complexity and round complexity of the task allocation problem. We begin with the classical two-player communication model, and show that the randomized communication complexity of task allocation is Ω(n), even when the set of tasks is known to the players in advance. For the multi-player setting with m = O(n) we give two upper bounds in the shared-blackboard model of communication. We show that the problem can be solved in O(log n) rounds and O(n log n) total bits for arbitrary inputs; moreover, if for any set X of tasks, there are at least α|X| players that have at least one task from X in their inputs, then O((1 α + log m)log n) rounds suffice even if each player can only write O(log n) bits on the blackboard in each round. Finally, we extend our results to the case where the players communicate over an arbitrary directed communication graph instead of a shared blackboard. As an application of these results, we also consider the related problem of constructing a directed spanning tree in strongly-connected directed networks and we show lower and upper bounds for that problem.