ﻻ يوجد ملخص باللغة العربية
In the subgraph-freeness problem, we are given a constant-size graph $H$, and wish to determine whether the network contains $H$ as a subgraph or not. The emph{property-testing} relaxation of the problem only requires us to distinguish graphs that are $H$-free from graphs that are $epsilon$-far from $H$-free, meaning an $epsilon$-fraction of their edges must be removed to obtain an $H$-free graph. Recently, Censor-Hillel et. al. and Fraigniaud et al. showed that in the property-testing regime it is possible to test $H$-freeness for any graph $H$ of size 4 in constant time, $O(1/epsilon^2)$ rounds, regardless of the network size. However, Fraigniaud et. al. also showed that their techniques for graphs $H$ of size 4 cannot test $5$-cycle-freeness in constant time. In this paper we revisit the subgraph-freeness problem and show that $5$-cycle-freeness, and indeed $H$-freeness for many other graphs $H$ comprising more than 4 vertices, can be tested in constant time. We show that $C_k$-freeness can be tested in $O(1/epsilon)$ rounds for any cycle $C_k$, improving on the running time of $O(1/epsilon^2)$ of the previous algorithms for triangle-freeness and $C_4$-freeness. In the special case of triangles, we show that triangle-freeness can be solved in $O(1)$ rounds independently of $epsilon$, when $epsilon$ is not too small with respect to the number of nodes and edges. We also show that $T$-freeness for any constant-size tree $T$ can be tested in $O(1)$ 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 $O(1/epsilon)$ rounds. This class includes all graphs over 5 vertices except the 5-clique, $K_5$. For cliques $K_s$ over $s geq 3$ nodes, 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 distributed subgraph-freeness problem, we are given a graph $H$, and asked to determine whether the network graph contains $H$ as a subgraph or not. Subgraph-freeness is an extremely local problem: if the network had no bandwidth constraints,
In this paper we initiate the study of property testing in simultaneous and non-simultaneous multi-party communication complexity, focusing on testing triangle-freeness in graphs. We consider the $textit{coordinator}$ model, where we have $k$ players
The minimum-weight $2$-edge-connected spanning subgraph (2-ECSS) problem is a natural generalization of the well-studied minimum-weight spanning tree (MST) problem, and it has received considerable attention in the area of network design. The latter
We present algorithms for testing if a $(0,1)$-matrix $M$ has Boolean/binary rank at most $d$, or is $epsilon$-far from Boolean/binary rank $d$ (i.e., at least an $epsilon$-fraction of the entries in $M$ must be modified so that it has rank at most $
Subgraph counting is a fundamental problem in analyzing massive graphs, often studied in the context of social and complex networks. There is a rich literature on designing efficient, accurate, and scalable algorithms for this problem. In this work,