New Parallel and Streaming Algorithms for Directed Densest Subgraph

Thank you for your feedback. For the introduction about the MPC algorithm, we will mention that the total number of machines is $n$, the number of vertices in the graph, and the edges are arbitrarily partitioned across the machines. As for your suggestion on the tables, we agree that it would make comparisons with previous works more clear and will add them in the final version of our paper.

Thank you for your comments. We address the questions provided below:

1. The factor of 2 in the approximation purely comes from the subgraph condition and is not related to the duplication of vertices to produce an undirected bipartite graph. The existing $(1+\epsilon)$-approximation algorithms do not use a similar subgraph condition. [EHW15] entirely uses one large uniform sample of the graph in order to approximate the directed DS. [BGM14] uses a technique called the multiplicative weights update method to approximately solve the directed DS LP. Both of these $(1+\epsilon)$-approximation algorithms use different techniques than our subgraph condition.

2. Yes, our approximation factor would be $O(\log n)$ compared to their $(1+\epsilon)$. However, their algorithm uses $\tilde{\Theta}(n^{1.5})$ memory, which is more than our $\tilde{O}(n)$ memory. So, their algorithm doesn’t fit within the memory constraints of the semi-streaming setting. Additionally, as mentioned in the paper, our algorithm is the first deterministic single-pass algorithm for approximating the undirected or directed DS as far as we know. These are the main advantages over [EHW15].

Thank you for the helpful suggestions. We address the suggestions provided below:

Q1: We have executed additional experiments for MPC. Our additional experiments show that using less memory per machine slightly increases the number of rounds for our algorithm -- as expected -- but it is still significantly less than the number of rounds used by [BKV12]. The conference rules suggest we do not send a link to those plots, but we will include the plots in our final version.

Q2: We do realize that Algorithm 2 involves technical tools, and we will add more intuitive explanations of these tools in the final version of the paper. In particular, we will expand more on the idea of “freezing” high-degree vertices and how that goes hand in hand with our sampling scheme.

Thank you for the helpful suggestions. After receiving your feedback, we have executed additional experiments for MPC. Our additional experiments show that using less memory per machine slightly increases the number of rounds for our algorithm -- as expected -- but it is still significantly less than the number of rounds used by [BKV12]. The conference rules suggest we do not send a link to those plots, but we will include the plots in our revised version. Additionally, we will add a table of previous results to our final paper in order to allow for clearer comparisons. We also address the questions provided below:

Q1: If the stream arrives in a random order, we would be able to leverage how sets of edges in the stream are uniform samples of the entire graph. MP24 already provides a result for this setting, though, attaining a $(2+\epsilon)$-approximation using this random order stream property.

Q2: Thank you for this excellent question! That is something we considered, but the ways of extending our algorithm to allow edge deletions makes it difficult to prove that the $O(\log n)$-approximation still holds. For example, edge deletions should be able to decrease the level of a vertex, but then it is unclear how to set its degree within this lower level. Handling this by resetting the degree back to 0 would result in losing too much information about vertex’s neighbors. So, a different idea is necessary. This is one of the many complications that arise if we still want to maintain the simplicity of our semi-streaming algorithm. Nevertheless, we find this to be a fantastic direction for future work!

Thank you for the feedback and detailed reading of our paper. We address the questions/suggestions provided below:

• The value of $\delta$ provided to Algorithm 2 specifies that each machine will use $O(n^\delta)$ memory, which is then shown in the proof of Theorem 4.2. We will make this more clear by adding it to our result and theorem statements; thanks for pointing that out.

• The main technical comparison, which is discussed in Section 3.1, is that our algorithm uses new stopping rules compared to other peeling algorithms (BKV12, GLM19, MP24). These rules give us an efficient, simple peeling algorithm, which enables us to improve existing results for MPC and semi-streaming. As for EHW15, their work is limited to a single uniform sample of the entire graph, while our MPC algorithm takes many samples in order to approximate degrees for our base peeling algorithm. This is not exactly novel but combined with our new base algorithm, it gives us the new results presented in our paper.

• From our understanding, Bhattacharya et al. (STOC 2015) is a dynamic algorithm that outputs an $(8+\epsilon)$-approximation of the density value and does not provide vertex sets for the approximate directed DS. Additionally, it has an amortized update time of $\tilde{O}(1)$, the worst-case update time that is polynomial in $n$, and uses linear memory $O(m)$, so it does not fit within the memory of the semi-streaming model. Sawlani & Wang (STOC 2020), which we cite in our submission, provides a dynamic algorithm that outputs a $(1+\epsilon)$-approximation including the vertex sets of the approximate directed DS. Nevertheless, we agree that we should cite and discuss Bhattacharya et al. (STOC 2015); we will do so in our final version by including a refined version of the following paragraph.

• As for the techniques, the $(\alpha, \delta, L)$-decomposition introduced by Bhattacharya et al. (STOC 2015) is an extension of a fixed d-core which is a classical idea for approximating the DS. Our paper revolves around calculating something similar, as reflected in Lemma 3.2, but the way we compute it using peeling is novel because of the stopping conditions described in Section 3.1; in short, it allows us to keep a fixed threshold of peeling while guaranteeing an approximation in a small number of iterations. Bhattacharya et al. (STOC 2015) does not maintain this fixed threshold and actually allows relaxations in the threshold, specified by the $\alpha$ parameter, in order to keep the number of iterations small. Additionally, our algorithm outputs an approximate DS by comparing vertex set sizes, while Bhattacharya et al. (STOC 2015) only proves an existence of some vertex sets that attain their approximation (their result presented in Corollary 6.7). These reflect some of the major differences between the algorithms that allow us to attain the new results in our paper.

Thank you for the additional comments.

Space per machine:

We agree that this could be made more explicit. Our theorems and preliminaries state that we work in the sublinear MPC regime, which by standard definition means that each machine has $O(n^\delta)$ space for an arbitrarily small constant $\delta > 0$. In this model, $\delta$ is a system parameter rather than something fixed by the algorithm, which is why we did not commit to a specific value. That said, we understand that not all readers may be familiar with this convention, and we will revise the theorem statement to explicitly include that each machine has $O(n^\delta)$ memory for some constant $\delta > 0$.

Why didn't you include ... total space and total work time in theorems?

There is no specific reason—this was purely an omission on our side. As a direct consequence of the design, the total number of machines used is $O(n + m / n^\delta)$, so the total space is $O(n^{1+\delta} + m)$. We will include this in the theorem statement.

As for the total work/time, each round of our algorithm performs near-linear work. In the literature on sublinear MPC algorithms, round complexity is the main bottleneck and is typically the focus; total time per round is rarely spelled out unless it is superlinear. Nonetheless, to avoid ambiguity, we will include a line in the preliminaries explicitly stating: "Even though the running time in definition of the MPC model is allowed to be arbitrarily large, the running time of our MPC algorithm is near-linear per round."

Additionally, could you clarify the space usage of the streaming algorithm presented in [MP24] for random order streams? Also, what would be the approximation factor and space usage of your algorithm for random order streams?

The space usage in [MP24] is $O(n \log^2 n)$. Our semi-streaming algorithm has the same space complexity and does not change when applied to random-order streams; however, unlike [MP24], it is designed to work even under adversarial edge arrival. As a result, when run on a random-order stream, our algorithm still achieves an $O(\log n)$-approximation while using $O(n \log^2 n)$ memory.

Beyond random vs adversarial order, an important distinction lies in the worst-case update time. The algorithm in [MP24] relies on global peeling phases, which can lead to high and unpredictable update times. In contrast, our algorithm guarantees worst-case update time of $O(\log^2 n)$ per edge. This difference is evident in practice, as shown in Figure 3 of our submission.