Model-Agnostic Approximation of Constrained Forest Problems

Our basic notation is summarized in Table 3.

For a set $S$, we denote its cardinality by $|S|$, its power set by $2^S=\{X\mid X\subseteq S\}$, and the set of its $k$-element subsets by $\left(\genfrac{}{}{0pt}{}{S}{k}\right)$. We extend functions $f:S\to ℝ$ to subsets $X\subseteq S$ in the natural way by setting $f(X)={\sum }_{x\in X}f(x)$, and we write the sets of positive and nonnegative integers no greater than $k$ as $[k]=\{i\in \mathbb{N}\mid i\le k\}$ resp. ${[k]}_0=\{i\in {\mathbb{N}}_0\mid i\le k\}$.

We consider weighted graphs $G=(V,E)$ with $n=|V|$ nodes, $m=|E|$ edges, and edge weights (edge costs) $c:E\to {\mathbb{N}}_0$ polynomially bounded in $n$.⁶⁶6Assuming polynomially bounded edge weights allows us to encode polynomial sums of edge weights with $𝒪(\log n)$ bits, which means that we can encode edge weights in a single message (Congest) or memory word (PRAM and MPS). Zero-weight edges arise naturally when simulating contractions in the distributed setting. We can handle them by scaling all non-zero edge weights by $n/\epsilon$ (where w.l.o.g., $1/\epsilon$ is polynomially bounded as well), and assigning weight $1$ to all previously zero-weight edges. Each node is equipped with a unique identifier of $𝒪(\log n)$ bits, which is also used to break ties. An $\mathrm{\ell }$-hop path from $u\in V$ to $v\in V$, denoted $p(u,v)$, is a sequence of distinct edges $(e_1,\mathrm{\dots }{e}_{\mathrm{\ell }})$ arising from a sequence of distinct nodes $(v_1,\mathrm{\dots },v_{\mathrm{\ell }+1})$ such that $e_i=\{v_i,v_{i+1}\}\in E$ for $i\in [\mathrm{\ell }]$, $v_1=u$, and $v_{\mathrm{\ell }+1}=v$. The (unweighted) hop distance between $u$ and $v$ is the smallest number of hops needed to go from $u$ to $v$, i.e., $h(u,v)=\min \{i\mid \exists p(u,v)\text{with}|p(u,v)|=i\}$, and the hop diameter of $G$ is $D=\max \{h(u,v)\mid \{u,v\}\in \left(\genfrac{}{}{0pt}{}{V}{2}\right)\}$. The (weighted) shortest-path distance between $u$ and $v$ is $d(u,v)=\min \{i\mid \exists p(u,v)\text{with}c(p(u,v))=i\}$. A shortest path between $u$ and $v$, denoted $P(u,v)$, is a path from $u$ to $v$ of length $d(u,v)$. The shortest-path diameter $s$ of $G$ is the maximum over all $\{u,v\}\in \left(\genfrac{}{}{0pt}{}{V}{2}\right)$ of the minimum number of hops contained in a shortest path from $u$ to $v$, i.e., $s=\max \{\min \{|P(u,v)|\mid \{u,v\}\in \left(\genfrac{}{}{0pt}{}{V}{2}\right)\}\}$. Given a cut $(S,V\setminus S)$, the set of edges with exactly one endpoint in $S$ is denoted as $\delta (S)=\{e\in E\mid |e\cap S|=1\}$.

An event occurring with high probability (w.h.p.) has probability at least $1-1/n^c$ for a freely chosen constant $c\ge 1$.

We are interested in Constrained Forest Problems (CFPs) as introduced by Goemans and Williamson [16].⁷⁷7To simplify the technical exposition, like Goemans and Williamson [16], we disallow zero-weight edges. However, it is straightforward to extend our approach to zero-weight edges by scaling edge weights as discussed in Footnote 6. Given a graph $G=(V,E)$ with edge costs $c:E\to \mathbb{N}$ and a function $f:2^V\to \{0,1\}$, a CFP asks us to solve the integer program stated as Problem 1, whose dual relaxation is provided as Problem 2.

That is, a CFP is a minimization problem whose optimal solution is a forest⁸⁸8For any cycle and node set $S$, $\delta (S)$ cannot contain exactly one edge from the cycle. Hence, from any solution with a cycle, we can remove an edge. of edges from the input graph $G$ that meets the constraints imposed by the forest function $f$. Like Goemans and Williamson [16], we consider CFPs with proper functions $f$, which satisfy (1) zero, i.e., $f(V)=0$, (2) symmetry, i.e., $f(S)=f(V\setminus S)$, and (3) disjointness (also called maximality [17]), i.e., if $A\cap B=\mathrm{\varnothing }$ for two sets $A$ and $B$, then $f(A)=f(B)=0$ implies $f(A\cup B)=0$.⁹⁹9We also assume that $f$ is nontrivial, i.e., that there exists at least one $S\subset V$ such that $f(S)=1$.

For a CFP with forest function $f$, a node $v$ is called a terminal if $f(\{v\})=1$. Given a forest function $f$, we denote the set of terminals as $𝒯=\{\{v\}\mid v\in V,f(\{v\})=1\}$ and the number of terminals as $t=|𝒯|$.

To demonstrate the flexibility of our approach, we consider Survivable Network Design Problems (SNDPs) that originate from three different real-world challenges.

SF has practical relevance especially in infrastructure development [1], with MST ($𝒯=V_1=V$) and ST ($𝒯=V_1\subseteq V$) as special cases. It is NP-complete [29] and APX-hard [9].

PPC is motivated by challenges from circuit switching and VLSI design, and the problem is NP-complete [31].

Our last problem is Facility Placement and Connection (FPC), an NP-complete facility-location-type problem arising, e.g., in operations research. Intuitively, FPC can be stated as follows.

To turn this task into a CFP matching our framework, we add one additional node $s\notin V$ and, for each $v\in V$, an edge $\{v,s\}$ of weight $c(\{v,s\})=o_v$. The task then becomes to determine a (low-weight) Steiner Tree spanning $C\cup \{s\}$, i.e., the special case of SF with $k=1$.

Even in Congest, we can solve ordinary ST instances efficiently, regardless of the specific input representation. However, the virtual node $s$ and its incident edges need to be simulated in the chosen model of computation. This is trivial in PRAM (simply modify the input representation in parallel) and Multi-Pass Streaming (since we use $\mathrm{\Omega }(n\log n)$ bits of memory anyway) but nontrivial in Congest. For Congest, we show that we can simulate the virtual node efficiently using Partwise Aggregation.

Finally, we introduce a subroutine that we use as a black box to achieve near-universal optimality in cases where efficient solutions are known.

Haeupler et al. [27] show that $\tilde{\mathrm{\Omega }}(Q)$ is a lower bound for MST (i.e., SF and ST with $k=1$ and $V_1=V$) and shortest $s$-$t$ path (the special case of PPC with $|X|=|Y|=1$) – regardless of the approximation ratio and also for randomized Las Vegas algorithms, i.e., those that guarantee a feasible output. They further prove that PA can be solved in $\widetilde{𝒪}(Q)$ rounds in the Supported Congest model, which is Congest with the unweighted graph topology given as part of the input.

Our shell-decomposition algorithm, depicted in Figure 1, is based on the primal-dual formulation for general CFPs given by Goemans and Williamson [16] (GW algorithm), restated as Algorithm 1, which yields a $(2-2/t)$-approximation [16] for CFPs with proper forest functions. Our algorithm can also be seen as a model-agnostic generalization of the algorithm by Agrawal et al. [1], ported to the distributed setting by Lenzen and Patt-Shamir [30]. These algorithms have also been called moat-growing algorithms [18, 3, 30].

Intuitively, our algorithm operates as follows. We maintain connected components $𝒞$, initialized to the singletons $𝒞=\{\{v\}\mid v\in V\}$. A component $C\in 𝒞$ is active if $f(C)=1$. The algorithm concurrently grows balls around all active components, with respect to the metric induced by the then-current edge costs $c^{\prime }$. In the growth process, two balls can touch only when at least one of their associated components is active, and only when the balls of two active components $C$, $C^{\prime }$ touch, adding edges to merge the components can make the resulting component inactive – otherwise, i.e., assuming $f(C\cup C^{\prime })=f(C^{\prime })=0$, symmetry implies $f(V\setminus (C\cup C^{\prime }))=0$, disjointness implies $f(V\setminus C)=f((V\setminus (C\cup C^{\prime }))\cup C^{\prime })=0$, and using symmetry again we get $f(C)=0$, a contradiction.

As illustrated in Figure 2, until the balls around two components touch, they are disjoint, witnessing that the dual problem has a solution with weight larger than the product of the current radius times the number of currently active components. Accordingly, when merging active components, we can afford to connect the terminals by adding a shortest path between them to the primal solution, paying a cost of at most twice the radius at merge. Because each merge we perform reduces the number of active components by at least one, the ball growth always witnesses sufficient additional weight in a dual solution to pay for future merges up to an approximation factor of $2$. Upon termination, i.e., when all components are inactive, the set of edges we selected constitutes a feasible solution.

The intuition sketched above already suggests that the ball-growing process allows for substantial concurrency. To achieve high efficiency across the board in various models, our shell-decomposition algorithm performs several modifications to the centralized GW algorithm, which originally assumes a final filtering step to eliminate unneeded edges from the solution, as well as exact distances and immediate forest-function evaluation.

1. (A)

   Incremental Solution-Set Construction. We merge active components that touch regardless of whether this ultimately turns out to be necessary to satisfy connectivity requirements. This does not impact the approximation guarantee, which was implicit already in the contribution by Agrawal et al. [1] and is now made explicit in our reformulation of the GW framework [16]. As a result, we need to determine if $f$ imposes further connectivity requirements only as often as we iterate through the loop in Figure 1.

2. (B)

   Approximate Distance Computations. At the cost of a factor of $1+\epsilon$ in the approximation ratio, we replace exact distance computations with $(1+\epsilon )$-approximate distance computations. The challenge here is to ensure that we do not violate the dual constraints when charging dual variables (corresponding to cuts) based on the progress of the primal solution. This can be achieved by constructing the dual solution in the true metric space, rather than reusing the approximate distances leveraged by the primal solution. In contrast to the other modifications, this requires a comparatively involved argument, and it is the main technical novelty and contribution in this part of our work.

3. (C)

   Deferred Forest-Function Evaluation. Again at the cost of a factor of $1+\epsilon$ in the approximation ratio, we let components grow to radii that are integer powers of $1+\epsilon$ before reevaluating our forest function to update their activity status. This technique was introduced by Lenzen and Patt-Shamir [30] for the Steiner Forest problem specifically; we show its general correctness in the context of the GW algorithm. Using this technique, we can limit the number of loop iterations in Figure 1 to $𝒪({\epsilon }^{-1}\log n)$ (assuming polynomially bounded edge weights).

The pseudocode of the resulting model-agnostic shell-decomposition algorithm is given as Algorithm 2. Here, to increase clarity and highlight the primal-dual nature of our algorithm, we also compute and output the lower bound LB on the cost of an optimal solution, which is not required to determine the output forest $F$. An example execution of Algorithm 2 is depicted in Figure 3. In Appendix A, we prove that the algorithm maintains an approximation ratio of $2+\epsilon$.

Leveraging the modifications specified in Items B, C, and A, to derive concrete algorithms in specific models of computation, what remains is to implement the individual steps in Figure 1. Up to simple book-keeping operations, this entails four main tasks (colored boxes in Figure 1):

1. (1)

   (Approximate) Set-Source Shortest-Path Forest (aSSSP). This is essentially computing a single-source shortest-path tree with a virtual source node, so we can plug in state-of-the-art algorithms for each model of interest [4, 35].

1. (2)

   Minimum Spanning Tree (MST). This is another well-studied task for which near-optimal solutions are known in all prominent models [33, 27, 34, 12].

2. (3)

   Root-Path Selection (RPS). Here, we are given a forest rooted at sources (where each node knows its parent in its tree and its closest source), along with a number of marked nodes. Our goal is to select the edges on the path from each marked node to its closest source. This problem can be straightforwardly addressed by solving a much more general flow problem: (Approximate) Transshipment, in which flow demands are to be satisfied at minimum cost. Again, we can plug in state-of-the-art algorithms for each model of interest [4, 35]. Note that in our case, the solution is restricted to containing the edges of a predetermined forest, such that the solution is unique, edge weights play no role, and the challenge becomes to determine the feasible flow quickly.

3. (4)

   Forest-Function Evaluation (FFE). The remaining subtask is to assess if $f(C)=1$, for each component $C\subset V$ in a set of disjoint, internally connected components $𝒞$– i.e., to determine which of the components still need to be connected to others. This is the only step that depends on $f$, requiring an implementation of $f$ matching the given model of computation.

Note that $f$ is an arbitrary proper function, so evaluating it can be arbitrarily hard. Thus, our algorithm confines the hardness of the task that comes from the choice of $f$ to $O({\epsilon }^{-1}\log n)$ evaluations of $f(C)$ for disjoint connected components $C\in 𝒞$ (cf. Item A). In contrast, the other three subtasks can be solved by state-of-the-art algorithms from the literature in a black-box fashion.

To illustrate the power of our result, we apply our machinery in three models of computation – Congest, Parallel Random-Access Machine (PRAM), and Multi-Pass Streaming (MPS) – to three Constrained Forest Problems. Our results follow from Theorem 1 with (1) the referenced results on aSSSP, MST, and RPS, (2) model- and problem-specific subroutines for FFE, and (3) model-specific subroutines for book-keeping operations.

In Footnote˜5, we highlight the improvements over the state of the art achieved for our example problems by instantiating the shell-decomposition algorithm in the Congest model.

1. (I)

   Steiner Forest (SF). From $\widetilde{𝒪}({\epsilon }^{-1}(sk+\sqrt{\min \{st,n\}}))$ time¹⁰¹⁰10Recall that $n$ denotes the number of nodes, $k$ the number of input components, $t$ the number of terminals, $D$ the unweighted (hop) diameter, and $s$ the shortest-path diameter. Both $t$ and $s$ can be up to $\mathrm{\Omega }(n)$, regardless of $k$ or $D$. for a $(2+\epsilon )$-approximation and $\widetilde{𝒪}(\min \{s,\sqrt{n}\}+D+k)$ time for an $𝒪(\log n)$-approximation to SF–IC obtained by Lenzen and Patt-Shamir [30] to $(2+\epsilon )$-approximations in time (1) $\widetilde{𝒪}({\epsilon }^{-3}(\sqrt{n}+D)+{\epsilon }^{-1}k)$ for SF–IC, (2) $\widetilde{𝒪}({\epsilon }^{-3}(\sqrt{n}+D))$ for SF–SCR, and (3) $\widetilde{𝒪}({\epsilon }^{-3}(\sqrt{n}+D)+{\epsilon }^{-1}\min \{n^{2/3},k\})$ for SF–CIC. For SF–CR, we incur the same additive running-time overhead of $𝒪(t)$ as Lenzen and Patt-Shamir [30], matching the existential lower bound they showed.

2. (II)

   Point-to-Point Connection (PPC). We are not aware of prior work providing Congest algorithms for the PPC problem. Here, we obtain a $(2+\epsilon )$-approximation in $\widetilde{𝒪}({\epsilon }^{-3}(\sqrt{n}+D))$ time.

3. (III)

   Facility Placement and Connection (FPC). We do not know of any existing Congest algorithms for the FPC problem, and we realize a $(2+\epsilon )$-approximation in $\widetilde{𝒪}({\epsilon }^{-3}(\sqrt{n}+D))$ time.

We also derive algorithms for SF, PPC, and FPC in the PRAM and Multi-Pass Streaming models, taking $\widetilde{𝒪}({\epsilon }^{-3}m)$ work and $\widetilde{𝒪}({\epsilon }^{-3})$ depth in the PRAM model, as well as $\widetilde{𝒪}({\epsilon }^{-3})$ passes and $\widetilde{𝒪}(n)$ space in the Multi-Pass Streaming model. To the best of our knowledge, these algorithms are either the first ones to perform these tasks in their respective models or they cover more general classes of instances than the state of the art (see extended version). Notably, we obtain our diverse results with relative ease once the analysis of our model-agnostic shell-decomposition algorithm is in place – which contrasts with the challenges of directly designing specific algorithms for specific problems in specific models.

In the Congest model, the $\sqrt{n}$ term in the complexity is due to the fact that, in general, it is not possible to solve Partwise Aggregation (PA) in $\tilde{o}(\sqrt{n})$ rounds. As formalized in Definition 6, PA denotes the task of performing an aggregation and broadcast operation on each subset in a partition of $V$ that induces connected components [14]. We can leverage PA, inter alia, to determine a leader and distribute its ID, or to find and make known a heaviest outgoing edge, for each component (a.k.a. part) in parallel. PA-type operations are key to efficient MST construction, and any $T^{PA}$-round solution to Partwise Aggregation lets us solve MST in $\widetilde{𝒪}(T^{PA}+D)=\widetilde{𝒪}(T^{PA})$ rounds [13, 14].

As MST computation is a CFP, it might not surprise that Partwise Aggregation can serve as a key subroutine for other CFPs in the Congest model as well. We show that the $\sqrt{n}$ term in the complexity of CFPs can be replaced by $T^{PA}$. Since this is already known for $(1+\epsilon )$-approximate Set-Source Shortest-Path Forest [35], Minimum Spanning Tree [13], and $(1+\epsilon )$-approximate Transshipment [35] (which can be used to solve Root-Path Selection),¹¹¹¹11The results for approximate Set-Source Shortest-Path Forest and approximate Transshipment are conditional on the existence of fast $(\widetilde{𝒪}(1),\widetilde{𝒪}(1))$-cycle-cover algorithms; otherwise, we incur an $n^{o(1)}$ overhead (see Footnote 5). again we need to show this for Forest-Function Evaluation only. This is straightforward for PPC and FPC, and simple algorithms evaluate the forest function for SF-IC and SF-CR in $𝒪(T^{PA}+k)$ and $𝒪(T^{PA}+t)$ rounds, respectively.

The substantial literature on low-congestion shortcuts provides a large array of results on solving Partwise Aggregation in time comparable to the shortcut quality of the input graph, i.e., the best possible running time $T^{PA}$ for Partwise Aggregation [37, 35, 27, 26, 15, 14, 22, 23, 2]. In particular, $T^{PA}\in \widetilde{𝒪}(D)$ if the input graph does not contain a fixed $\widetilde{𝒪}(1)$-dense minor, without precomputations or further knowledge of $G$ [14]. Examples of graphs without $\widetilde{𝒪}(1)$-dense minors are planar graphs and, more generally, graphs of bounded genus. Moreover, in Supported Congest (where $(V,E)$ is known – or rather, can be preprocessed), $T^{PA}\in \widetilde{𝒪}(Q)$, i.e., within a polylogarithmic factor of the optimum. Due to the modular structure of our results, any future results on Partwise Aggregation and low-congestion shortcuts will automatically improve the state of the art for CFPs in the Congest model.

In the Congest model, it is known that even on a fixed network topology, $\tilde{\mathrm{\Omega }}(T^{PA})$ rounds are required to obtain any non-trivial approximation for a large class of problems. This class includes MST, a special case of ST, which reduces to FPC by making all but the opening cost of a single node very high, and shortest $s$-$t$-path [27], a special case of PPC. Thus, this universal lower bound applies to our example tasks as well. In particular, our results on PPC and FPC have almost universally tight running times.

In contrast, the additive terms of $k$ and $t$ in the running times of our algorithms for SF-IC and SF-CR, respectively, are only existentially optimal [30]: The lower-bound graph – a double star – has shortcut quality $𝒪(1)$, but in a fully connected graph, it is trivial to evaluate $f$ for all current components in two rounds. This motivates us to split Forest-Function Evaluation for Steiner Forest into two parts: (1) determining, for each input component $V_i\subseteq V$ or connection request $r\in ℛ$, respectively, whether the specified connectivity requirements are met, and (2) determining, for each current component $C\in 𝒞$, whether it contains a terminal whose connectivity requirements are not met. While the second part can be solved via standard Partwise Aggregation, the first part requires aggregating information within $k$ (or $t$) disjoint components that may be internally disconnected. We call this task Disjoint Aggregation on $p$ parts, $\mathrm{DA}(p)$, achieve the trivial bound $T^{DA(p)}\in 𝒪(D+p)$ via pipelining over a BFS tree, and hypothesize that the universal complexity of $\mathrm{DA}(p)$ merits further investigation in future work.

As an orthogonal approach, we explore the effect of the input specification on our SF results. The assumptions that (1) pairs of terminals know that they need to be connected (SF–SCR), or (2) the size of each input component is known to its constituent terminals (SF–CIC) both are plausible, and they change the basis of the applicable existential lower bounds from $2$-party set disjointness [30] to $2$-party equality, as depicted in Figure 4. We provide the details in the extended version.

Assuming SF–SCR, we show how to achieve a running time of $\widetilde{𝒪}(\min \{T^{PA}{n}^{o(1)},\sqrt{n}+D\})$ using efficient randomized $2$-party equality testing. We sketch a solution assuming shared randomness here; standard techniques achieve the same without shared randomness. For each terminal-request pair $\{u,v\}$, we flip a fair independent coin and denote the result by $c_{\{u,v\}}\in \{0,1\}$. Now each component $C$ aggregates ${\sum }_{u\in C}{\sum }_{v\in {ℛ}_v}{c}_{\{u,v\}}mod2$. Observe that if $u,v\in C$ for request pair $\{u,v\}$, then for SF–SCR, it holds that $v\in {ℛ}_u$ and $u\in {ℛ}_v$. Hence, if $C$ contains, for each request pair, either both terminals or none of the terminals, then the sum is guaranteed to be $0$ modulo $2$. Otherwise, fix a request pair $\{u,v\}$ with $u\in C$ and $v\in V\setminus C$. After evaluating the sum up to coin $c_{u,v}$, it is either $0$ or $1$, and hence, by independence of $c_{u,v}$, with probability $1/2$, the sum is $1$ modulo $2$. Therefore, performing the process $𝒪(\log n)$ times in parallel, we can distinguish between $f(C)=0$ and $f(C)=1$ with high probability. This computation can be performed by a single aggregation, where the aggregation operator $⨁$ is given by bit-wise addition modulo $2$.

Our strategy for SF–CIC is similar, but results in a much weaker bound of $\widetilde{𝒪}(n^{2/3}+D)$; our main point here is to demonstrate that the $\tilde{\mathrm{\Omega }}(k)$ can be beaten. We distinguish three cases. (1) Components $C$ of size at most $n^{2/3}$ are spanned by a rooted tree of size $n^{2/3}$. Here, we can aggregate the terminal counts, for all input components, within $C$ at $C$’s root in $𝒪(n^{2/3})$ rounds to determine activity status. (2) For each input component of size at least $n^{1/3}$, we globally aggregate if there are two distinct component IDs with a terminal from that input component. This requires one aggregation for each such input component, all of which can be completed within $𝒪(n^{2/3}+D)$ rounds via a BFS tree, as there can be at most $n^{2/3}$ input components of this size. (3) For input components of size , each component $C$ of size larger than $n^{2/3}$ uses the same strategy as for SF–SCR. However, only input components of the same size can be handled in a single aggregation, as the summation is now modulo $s$. Hence, $\widetilde{𝒪}(n^{1/3})$ aggregations by at most $n^{1/3}$ components of size larger than $n^{2/3}$ are required, which can again be performed in $\widetilde{𝒪}(n^{2/3}+D)$ rounds.