The Central Spanning Tree Problem

We would like to thank the reviewer for pointing out that our work is theoretically interesting. Next, we will address the concerns that were not covered in the main response.

• Advantages of CST over MRCT: The consistent performance of mSTreg across diverse $\alpha$ values stands out as a significant strength, aligning with our goal of creating a useful heuristic. Therefore, the point that the CST is as difficult to solve as the MRCT is secondary, as the CST has still valuable advantages over the MRCT. While MRCT's higher star-shape tendency enhances stability, it risks information loss, especially in higher dimensions, as depicted in Figure 12. The parameterized nature of $\alpha$ in CST mitigates this, allowing for a tailored balance between robustness and data fidelity. This flexibility is particularly crucial in higher dimensions, where the CST's interpolation surpasses the limitations of MRCT. These observations underscore the superiority of the more general CST and its branched version, emphasizing their real-world applicability, specifically in higher dimensions.

• Increased number of iterations: Adding more iterations to mSTreg may lower the tree cost. While our heuristic converges quickly, its inherent randomness permits additional exploration. As explained in Section 3, the same CST "type" topology can yield multiple full tree topologies. Consequently, when transforming the mST into a full tree topology, variations can emerge. Despite convergence, the randomness in this step may explore new topologies, further reducing the overall cost.

We express our gratitude to the reviewer for their feedback.

Concerning the level of difficulty in solving the more general CST/BCST compared to the MRCT, it is important to clarify that we are not asserting that our proposal is inherently easier to solve. Rather, our argument centers on the observation that the parameterized CST/BCST exhibits more appealing properties than the MRCT. As a result, opting for the CST/BCST might be justified even if both are equally challenging to solve.

Regarding the 5-minute time limit, we aimed to demonstrate that mSTreg can outperform the MRCT in terms of efficiency, while yielding satisfactory solutions. Notably, mSTreg, executed with just 20 iterations, produced a solution within seconds. In contrast, GRASP_PR did not consistently enhance this solution within the specified 5-minute timeframe. Extending the runtime of GRASP_PR would likely result in further improvements, as it would explore the solution space more extensively. It is important to emphasize that GRASP_PR, initialized with mSTreg, also adhered to the 5-minute time limit, surpassing the other two alternatives. This demonstrates the clear benefit of the combined approach and highlights how initializing with mSTreg can enhance GRASP_PR.

We would like to thank the reviewer for the thorough examination of our work. Next, we will address the concerns not covered in the main response.

• (Q2) CST on single cell data: While CST may not fully capture the bifurcation, it does exhibit a discernible split, indicated by two wide edges. The fact that the mST is not able to detect the bifurcation, does not diminish the value of the robustness argument as the mST undergoes drastic changes post-perturbation, in contrast to the CST. This highlights the CST's superiority in terms of robustness, even if not optimal. Nevertheless, we acknowledge that BCST might be more suitable for such applications due to better trajectory representation and preservation. We remark, that this is not the only example we show; the Appendix illustrates another instance leading to the same conclusions.

• (Q4) Guarantees of the heuristic: Currently, our heuristic lacks theoretical guarantees regarding the cost of the solutions it provides. However, through empirical evaluation, we have demonstrated that our heuristic consistently produces competitive solutions. It is worth noting that many algorithms employed for this class of problems rely on genetic algorithms or local search strategies, neither of which inherently provide any formal guarantee. While some algorithms may offer worst-case scenario bounds, they often struggle to scale effectively for large instance problems [1,2].

[1] Ravelo et al., "A PTAS for the metric case of the optimum weighted source–destination communication spanning tree problem", (2019).

[2] Wu et al., "Approximation algorithms for some optimum communication spanning tree problems", (2000).

We would like to express our gratitude to the reviewer for their conscientious review.

• Presentation: While we acknowledge the length of our Appendix, we believe it serves the purpose of providing comprehensive details for readers interested in a deeper understanding of our work. Our intention is to strike a balance between clarity in the main paper and the availability of detailed information in the Appendix. We contend that our manuscript does its best at conveying the most relevant information in the main part. Regarding the comprehension of our heuristic, we would value specific feedback on the aspects that may have been challenging, enabling us to make targeted improvements in the clarity of the section.

• Robustness discussion: To the best of our knowledge, we are the first ones to delve into the robustness of the geometrical structure of a spanning tree in response to data perturbations, such as noise. We thank the reviewer for providing additional references. However, it's crucial to highlight that the robustness treated by these papers differs from ours. Bezrukov et al.'s paper, although related by name, focuses on computing a Frechet mean among all spanning trees of a graph using the symmetric difference of edge sets as a metric. The paper by Kasperski and Zielinski studies the mST with uncertain edge costs. Thus, they aim to find a tree whose cost is robust under different realizations of the edge costs. Thus, both papers neglect the geometrical stability of the tree. Consequently, our comparison only included the mST and the MRCT, as these are natural limits of our CST proposal. Note that, though the MRCT already existed previously in the literature, its robustness, as explained here, had not been mentioned before. Moreover, as discussed in "Advantages of CST over MRCT" (see response to H47r), the MRCT's robustness may cause an information loss in contrast to the parameterized CST. In light of this, we contend that our study effectively addresses the specific robustness considerations within our scope. Simultaneously, we acknowledge that our related work did not mention alternative robustness criteria, and we will amend this in the final version.

• Role of Steiner points (SPs): Indeed, your understanding of the SPs is right. Regarding the formulation of the optimization problem in (2), we posit that it is appropriately formulated. While (1) only minimizes over the set of spanning trees, (2) jointly minimizes both the trees and the SPs' positions, what from our perspective does not pose a conflict. (2) is equivalent to minimizing the SPs' positions given a fixed topology and subsequently selecting the topology that achieves the minimum cost. If there are specific aspects of (2) that are unclear or concerning, we would appreciate additional details to address them comprehensively.

  Regarding the relevance of the Steiner points to model the structure, we acknowledge your valid point. Although SPs are not inherent to the original data, there are scenarios, where abstracting the data requires points that are not necessarily part of the raw data. For example, in many single-cell trajectory inference methods, it is common to define cluster centers (which are not part of the actual data) to describe the trajectory. Also in skeletonization the SPs become relevant as argued below in response "CST and Skeleton". We will emphasize these aspects in the final manuscript to provide a more comprehensive understanding of the applicability of the SPs.

• CST and Skeleton: We exclusively utilized the BCST for skeletonization, primarily because it is often desired that the skeleton goes through the "middle" of the volume. The SPs in the BCST offer the flexibility to be situated in the volume's center, ensuring that the BCST skeleton traverses this central region. In contrast, the CST lacks this flexibility and would, at best, zigzag over surface points. Hence, the CST was not considered for this particular application.

• Case $\alpha>1$: Apart from the limit case detailed in Appendix D.1, we refrained from further exploration due to practical observations indicating an excessive star-shaped tree, even in low dimensions. For instance, the toy dataset in Figure 2 became a star tree for $\alpha=1.15$. Regarding NP-hardness, it remains unproven in this regime as the strictly concavity argument applicable for $0<\alpha\leq1$ loses its validity. We hypothesize that in practice the problem might be generally easier to solve for higher $\alpha$ values, especially considering that, for the BCST problem, the SPs tend to collapse into a single point.

We would like to thank the reviewer for pointing out that our work is very natural and interesting.

• Section 2.1: This section aimed to empirically assess the stability of the (B)CST against noise. We started with an initial sample, denoted as $P_0$, consisting of n=1000 points uniformly drawn from a rectangle. To investigate the impact of noise, we generated five perturbed samples $P_i$ by introducing zero-centered Gaussian noise, defined as $P_i = P_0 + \Sigma_i$, where $i$ ranges from 1 to 5, and $\Sigma_i \in \mathbb{R}^{1000\times2}$ is a matrix with entries sampled independently from $\mathcal{N}(0,0.005)$. Using the Frobenius norm $||\cdot||_F$, we assessed robustness by comparing the shortest path distance matrices between trees computed by (B)CST at different $\alpha$ values over original and perturbed samples. In other words, for each $i\in {1,...,5}$, we computed the norm $||D_0^{\alpha}-D_i^{\alpha}||_F$, where $D_i^{\alpha}$ is the shortest path distance matrix of the (B)CST applied to $P_i$ at a certain $\alpha$ value. Figure 2a) presents the average Frobenius norm across $\alpha$ along with the average total length of the trees. The plot illustrates a decrease in the Frobenius norm, indicating increased similarity and greater robustness to perturbations with rising $\alpha$, albeit at the cost of longer edges. We hope this clarifies the experiment's setup.
• (B)CST for more general graphs: The CST easily generalizes to non-complete Euclidean graphs by considering their spanning trees. Analogously, the BCST could be generalized by considering full topologies derivable from the non-complete graph spanning trees. Yet, our heuristic faces challenges in this extension, as the mST step might yield a spanning tree, which is not a subgraph of the original graph. Ensuring the topology's validity in each iteration is non-trivial and therefore is left for future work. Additionally, our work briefly explores extending the (B)CST to Riemannian manifolds, addressing in Appendix H.4 the degree four Steiner points infeasibility on 2-dimensional manifolds. We recognize the heuristic's potential extension to arbitrary Riemannian manifolds pending efficient computation of Steiner points. Notably, CST, unlike BCST, can be defined over weighted graphs withtout requiring embedding in a metric space. However, our heuristic is irrelevant in this context, as the relation with BCST cannot be exploited.

• mSTreg vs GRASP_PR: In Section 4, we evaluated the effectiveness of the proposed mSTreg heuristic on solving large problems of the (B)CST particular problem instances with $\alpha=0$ and $\alpha=1$, namely the Steiner and Minimum Routing Cost Tree (MRCT) problems. It's important to note that our goal wasn't to achieve state-of-the-art performance, but to asses how competent can the mSTreg be. The Steiner problem, being an established problem, has specialized algorithms that may outperform our heuristic. Therefore, we only compared against the optimum cost. For the MRCT problem, lacking access to the optimum solution, we compared against other methods, including the GRASP_PR by Sattari et al. While the GRASP_PR method yielded a lower cost than our heuristic, we argued that mSTreg is more efficient and can enhance GRASP_PR's performance. In the following, we will clarify our claims:
  • Efficiency: GRASP_PR follows a two-phase approach. In the first one, it constructs a random solution and enhances it through local search. Each iteration of the local search replaces an edge of the tree, by the one that most decreases the cost. The second phase, explores paths between high-quality solutions to enhance the search. The overall complexity is dominated by the local search. A single iteration of it has a complexity of $\mathcal{O}(n^2)$, with $n$ being the number of nodes. In contrast, the mSTreg complexity per iteration is $\mathcal{O}(dn\log(n)^2$) (see Appendix K), where $d$ is the dimensionality of the data. Thus, mSTreg is more efficient.
  • mSTreg can enhance GRASP_PR performance: The effectiveness of GRASP_PR is influenced by the quality of its initial random guess, as it impacts the number of iterations needed for the the local search to converge. Next, we show that initializing the local search with a solution generated by mSTreg allows for initializations that enhance the performance of GRASP_PR. In our original report, we relied on the reported costs from the original GRASP_PR's paper, as we couldn't find an existing implementation. Now, we implemented it to validate our claims. Given that GRASP_PR is a versatile algorithm, we have used it also to compute the CST with other $\alpha$ values in addition to the $\alpha=1$ case reported in the main paper. Due to the slowness of the GRASP_PR algorithm we set a 5-minute time threshold. If exceeded, the algorithm returns the current best solution at the end of its second phase. We conducted tests using GRASP_PR, GRASP_PR initialized with mSTreg (GRASP_PR_mSTreg), and the mSTreg algorithms on the OR library datasets for problems with 50 and 100 nodes. The table below displays the average cost over three instances for different $\alpha$ values in the set {0.2, 0.4, 0.6, 0.8, 1}. Notably, the combination of the mSTreg heuristic with GRASP_PR consistently achieved the lowest cost. Across 30 runs (combining 5 $\alpha$ values, 2 problem sizes, and 3 instances), GRASP_PR outperformed mSTreg in only 12 instances. Moreover, achieving a lower cost took minutes for GRASP_PR, while mSTreg run in the order of seconds. Consequently, mSTreg emerges as a favorable alternative, delivering a decent solution quickly.