Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistributed Property Testing for Subgraph-Freeness Revisited
122
0
0.0
(
0
)
Added by
Orr Fischer
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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, we could detect any subgraph $H$ in $|H|$ rounds, by having each node of the network learn its entire $|H|$-neighborhood. However, when bandwidth is limited, the problem becomes harder. Upper and lower bounds in the presence of congestion have been established for several classes of subgraphs, including cycles, trees, and more complicated subgraphs. All bounds shown so far have been linear or sublinear. We show that the subgraph-freeness problem is not, in general, solvable in linear time: for any $k geq 2$, there exists a subgraph $H_k$ such that $H_k$-freeness requires $Omega( n^{2-1/k} / (Bk) )$ rounds to solve. Here $B$ is the bandwidth of each communication link. The lower bound holds even for diameter-3 subgraphs and diameter-3 network graphs. In particular, taking $k = Theta(log n)$, we obtain a lower bound of $Omega(n^2 / (B log n))$.
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 receiving private inputs, and a coordinator who receives no input; the coordinator can communicate with all the players, but the players cannot communicate with each other. In this model, we ask: if an input graph is divided between the players, with each player receiving some of the edges, how many bits do the players and the coordinator need to exchange to determine if the graph is triangle-free, or $textit{far}$ from triangle-free? For general communication protocols, we show that $tilde{O}(k(nd)^{1/4}+k^2)$ bits are sufficient to test triangle-freeness in graphs of size $n$ with average degree $d$ (the degree need not be known in advance). For $textit{simultaneous}$ protocols, where there is only one communication round, we give a protocol that uses $tilde{O}(k sqrt{n})$ bits when $d = O(sqrt{n})$ and $tilde{O}(k (nd)^{1/3})$ when $d = Omega(sqrt{n})$; here, again, the average degree $d$ does not need to be known in advance. We show that for average degree $d = O(1)$, our simultaneous protocol is asymptotically optimal up to logarithmic factors. For higher degrees, we are not able to give lower bounds on testing triangle-freeness, but we give evidence that the problem is hard by showing that finding an edge that participates in a triangle is hard, even when promised that at least a constant fraction of the edges must be removed in order to make the graph triangle-free.
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 problem asks for a minimum-weight subgraph with an edge connectivity of $1$ between each pair of vertices while the former strengthens this edge-connectivity requirement to $2$. Despite this resemblance, the 2-ECSS problem is considerably more complex than MST. While MST admits a linear-time centralized exact algorithm, 2-ECSS is NP-hard and the best known centralized approximation algorithm for it (that runs in polynomial time) gives a $2$-approximation. In this paper, we give a deterministic distributed algorithm with round complexity of $widetilde{O}(D+sqrt{n})$ that computes a $(5+epsilon)$-approximation of 2-ECSS, for any constant $epsilon>0$. Up to logarithmic factors, this complexity matches the $widetilde{Omega}(D+sqrt{n})$ lower bound that can be derived from Das Sarma et al. [STOC11], as shown by Censor-Hillel and Dory [OPODIS17]. Our result is the first distributed constant approximation for 2-ECSS in the nearly optimal time and it improves on a recent randomized algorithm of Dory [PODC18], which achieved an $O(log n)$-approximation in $widetilde{O}(D+sqrt{n})$ rounds. We also present an alternative algorithm for $O(log n)$-approximation, whose round complexity is linear in the low-congestion shortcut parameter of the network, following a framework introduced by Ghaffari and Haeupler [SODA16]. This algorithm has round complexity $widetilde{O}(D+sqrt{n})$ in worst-case networks but it provably runs much faster in many well-behaved graph families of interest. For instance, it runs in $widetilde{O}(D)$ time in planar networks and those with bounded genus, bounded path-width or bounded tree-width.
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 $d$). The query complexity of our testing algorithm for the Boolean rank is $tilde{O}left(d^4/ epsilon^6right)$. For the binary rank we present a testing algorithm whose query complexity is $O(2^{2d}/epsilon)$. Both algorithms are $1$-sided error algorithms that always accept $M$ if it has Boolean/binary rank at most $d$, and reject with probability at least $2/3$ if $M$ is $epsilon$-far from Boolean/binary rank $d$.
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, we tackle this challenge and design several new algorithms for subgraph counting in the Massively Parallel Computation (MPC) model: Given a graph $G$ over $n$ vertices, $m$ edges and $T$ triangles, our first main result is an algorithm that, with high probability, outputs a $(1+varepsilon)$-approximation to $T$, with optimal round and space complexity provided any $S geq max{(sqrt m, n^2/m)}$ space per machine, assuming $T=Omega(sqrt{m/n})$. Our second main result is an $tilde{O}_{delta}(log log n)$-rounds algorithm for exactly counting the number of triangles, parametrized by the arboricity $alpha$ of the input graph. The space per machine is $O(n^{delta})$ for any constant $delta$, and the total space is $O(malpha)$, which matches the time complexity of (combinatorial) triangle counting in the sequential model. We also prove that this result can be extended to exactly counting $k$-cliques for any constant $k$, with the same round complexity and total space $O(malpha^{k-2})$. Alternatively, allowing $O(alpha^2)$ space per machine, the total space requirement reduces to $O(nalpha^2)$. Finally, we prove that a recent result of Bera, Pashanasangi and Seshadhri (ITCS 2020) for exactly counting all subgraphs of size at most $5$, can be implemented in the MPC model in $tilde{O}_{delta}(sqrt{log n})$ rounds, $O(n^{delta})$ space per machine and $O(malpha^3)$ total space. Therefore, this result also exhibits the phenomenon that a time bound in the sequential model translates to a space bound in the MPC model.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
