Response to Reviewer z95E

Thank you for the detailed and thoughtful review. We are grateful for your recognition of the paper’s contributions. Below we respond to your helpful suggestions and questions:

Presentation and Writing

We appreciate your suggestions regarding the structure and clarity of the introduction and abstract. In particular:

• We agree that beginning with the main problems (USSS, UDSS, DSS, SFM, MNP) and then introducing known special cases such as HNSN, ADS, and DSG as motivating applications could enhance readability; in fact, this was our original structure for the introduction. However, we found that starting with concrete problems first offered stronger motivation than beginning with the more abstract formulations. That said, we will revise the text to smooth the transition and introduce the broader abstract problems earlier to better guide the reader.
• We also acknowledge that proof sketches in the main body would help with intuitions. Unfortunately, because of the page limit, we had to completely skip this for the submission. In the final version (when we get 1 additional page), we plan to include brief sketches for key reductions (e.g., DSS $\iff$ SFM, USSS $\Rightarrow$ MNP) and reference the full proofs in the appendix.
• We will clarify the purpose of each experimental result more explicitly. Specifically, as you noted: (1) the HNSN results demonstrate the relevance of classic MNP methods for new problems, and (2) the s-t cut experiments show that recent heuristics like SUPERGREEDY++ can compete with classical max-flow algorithms. We’ll make this motivation more clear near Figures 1a–1d.

Missing References and Attribution

Thank you for catching this, we will correct the following:

• Anchored Densest Subgraph (ADS): We will cite the original work by Dai et al., SIGMOD 2022 as the correct source for ADS.
• Nagano et al., ICML 2011: This is indeed highly relevant. We will cite and discuss it in the revised related work section.

Notation, Typos, and Clarifications

We will address all the specific issues you noted, including undefined notations, missing periods, and inconsistencies in phrasing. These are extremely helpful. In particular:

• Theorem 14: We will clean up the expression for the number of iterations (it should be $s-d$, not $s-x$) and fix the undefined operations.

Response to Questions

Q1: Can you summarize the time complexities of the algorithms, especially SUPERGREEDY++ for SFM?

• For SFM, SUPERGREEDY++ converges to a solution $S$ such that $f(S) \leq \text{OPT} + 2n\varepsilon$ in

  $$\widetilde{O}\left(\frac{\alpha_f }{\epsilon^2}\right)$$

  iterations, where $\alpha_f$ depends on the function $f$ (From Theorem 14).

Its runtime is still pseudo-polynomial due to the function-dependent terms. Empirically, it performs extremely well, but we agree the theoretical runtime should be compared with classical polynomial time algorithms like Iwata-Fleischer-Fujishige or Orlin’s algorithm.

We will add a small table or section summarizing these complexities in the final version.

Q2: Is it worth studying restricted versions of USSS, like SSS?

Absolutely. This is a great idea and a natural extension. In fact, our original motivation for this paper; minimizing $f(S)/|S|$ for $f(S)=|N(S)|$ being the coverage function falls under SSS.

While our paper focuses on unrestricted versions to allow non-monotone and negative functions (which are common in real-world applications like ADS and HNSN), restricted versions such as Sparsest Submodular Set with Monotone or Positive f could offer both:

• Simpler theoretical analysis, and
• Opportunities for improved approximations or faster algorithms.

It is also worth noting that for DSS, one can obtain results in terms of multiplicative approximations that cannot be shown for UDSS. We have some preliminary results for SSS in similar vein - for example SuperGreedy performance in terms of curvature constant of $f$ or potentially convergence analysis for SuperGreedy++ that is similar to that for DSS in the Chekuri et al. SODA paper for a multiplicative $(1+\varepsilon)$-approximation rather than additive one.

We will mention this direction explicitly in the conclusion as a promising avenue for future work.

Once again, we thank the reviewer for this thoughtful, technically precise review. Your feedback directly improves the final version.

Response to Reviewer Pm74

We thank the reviewer for their detailed and constructive feedback. Below we address the specific questions and suggestions:

Q1: Are the other problems (e.g., DSS, HNSN, USSS) also polynomial-time solvable like DSG?

Yes, all of the problems mentioned (DSS, USSS, UDSS, SFM, MNP) are, at least in theory, all polynomial-time solvable in the exact optimization setting. In fact, one of our main contributions (Theorem 12) is to show that these problems are strongly polynomial-time equivalent, with efficient reductions between them. This means that since Submodular Function Minimization (SFM) and MNP are known to be solvable in strongly polynomial time, so too are DSS, USSS, and others.

Of course, as we also emphasize, the approximation landscape can vary wildly in practice, depending on the function structure, which is discussed in Theorem 13.

Q2: Theorem 13 condition vs. standard MNP approximation — can we derive an approximate solution to MNP itself from this condition?

The condition in Theorem 13 assumes an approximate solution $\hat{x} \in B(f)$ satisfying

which upper bounds the duality gap. Theorem 14 guarantees such approximate solution after a number of iterations. While Theorem 13 focuses on how this approximate $\hat{x}$ leads to good set-based solutions for other problems (like SFM, USSS), it is true that this same $\hat{x}$ is also an approximate solution to the MNP problem itself, in the sense that $\hat{x}$ is close to the true minimum-norm point up to additive error $\varepsilon$.

We appreciate the suggestion and will include a short clarification that this approximate solution serves both as a good MNP solution and as a bridge to solving the other problems.

Q3: Do we need to explicitly reduce to MNP before applying the algorithms? Or can we apply them directly?

The answer is: both perspectives are valid.

• Our reductions show that all five problems can be reduced to MNP, and therefore, solving MNP (even approximately) suffices to solve the others.
• However, we frequently apply the same algorithms (such as Frank-Wolfe, SUPERGREEDY++, or Fujishige-Wolfe) directly to each problem—meaning we obtain the solution to the target problem without explicitly transforming it into a Minimum Norm Point (MNP) instance. This is feasible because these algorithms operate over the same base polytope $B(f)$, which is common to all of these problem formulations.

In fact, one of the key messages of the paper is that many of these algorithms are implicitly solving MNP, even when applied “naively” to problems like DSS or SFM. SUPERGREEDY++, for instance, was designed for DSS but is, under the hood, approximating the MNP solution in the base polytope.

Users can either reduce to MNP explicitly or apply these solvers directly if the base polytope access is available, the behavior and guarantees remain the same.

Formatting Suggestion – Monotonicity and SFM

Thank you — this is a helpful comment. We will revise the paragraph to clarify that SFM applies regardless of monotonicity, and that the definition is simply introduced for completeness before defining monotone variants like DSS.

Once again, we appreciate the thoughtful comments and high score.

Response to Reviewer XFrn

We sincerely thank the reviewer for their generous and thoughtful comments. We appreciate the recognition of the paper's contributions. Below, we respond to the specific questions and suggestions:

Q1: Why do MNP and FW perform well on HNSN but underperform on Minimum s-t Cut, despite theoretical equivalence?

This is an important and nuanced question. As you point out, when solved exactly, the problems are mathematically equivalent, and Theorem 12 provides the reductions showing how their optimal solutions can be transformed into one another. However, in the approximate setting, the situation becomes much more subtle. In approximation algorithms, problems with output values that are zero or non-negative are typically more challenging, as additive error—being the more appropriate measure in such cases—is harder to achieve, whereas multiplicative error is generally easier to handle for non-negative objectives.

The key difference lies in the structure of the underlying submodular functions:

• For the HNSN problem, the function $f(S) = |N(S)|$ is a coverage function — it is monotone, non-negative, and has a clean characterisations.
• Conversely, in the minimum s-t cut formulation, the function $f(S) = |\delta(S \cup \{s\})| - |\delta(\{s\})|$ is not monotone, can take negative values, and typically leads to more complex polytopes with extreme points that are close together or highly skewed.

These structural differences strongly influence the convergence behavior of iterative solvers such as Frank-Wolfe and MNP. In practice, we find that solver performance can vary significantly depending on the geometry of the base polytope, even when the underlying optimization problems are theoretically equivalent. For instance, in the minimum s–t cut formulation, the function $f(S) = |\delta(S \cup \{s\})| - |\delta(\{s\})|$ tends to be sensitive to small changes in the graph, which can result in a "thin" or skewed base polytope along certain directions.

This geometric perspective is not merely anecdotal; some convergence analyses of Frank-Wolfe explicitly rely on notions like pyramidal width, a purely geometric quantity that captures how “sharp” or “flat” the polytope is in different directions. Since both Frank-Wolfe and MNP operate by navigating the extreme points of the base polytope, their efficiency is tightly coupled with its geometric structure.

While we consistently observe that at least one of our universal solvers performs well on any given problem, we do not yet fully understand which solver performs best when, or why. Understanding the interplay between the function structure and solver behavior remains an open question, and is explicitly noted in the limitations of our work.

Q2: Why do general-purpose methods outperform problem-specific heuristics? Does this mean the heuristics aren’t leveraging the problem structure?

This is a great observation. In many problem-specific heuristics (e.g., greedy peeling or local ratio methods), the “specific structure” that is used is often simplistic or myopic, such as removing low-degree nodes without a global view.

In contrast, general-purpose methods like MNP, Frank-Wolfe, and SUPERGREEDY++ implicitly operate on the full combinatorial or polyhedral structure of the problem. As a result, they can often exploit hidden structure better than naive heuristics.

That said, it remains possible to design better problem-specific algorithms that leverage deeper properties (e.g., flow-augmenting paths, dual decompositions). Our results highlight that some heuristics underperform not because the problem is hard, but because the heuristic doesn’t fully exploit the structure, which we believe is an exciting direction for future algorithm design. We will elaborate on this in the final paper.

Q3: Ambiguity in the term "MNP" (problem vs. algorithm)

Thank you, this is a valid and very helpful suggestion. We agree that overloading "MNP" to mean both the Minimum Norm Point problem and the Fujishige-Wolfe algorithm can cause confusion. In the final version, we will explicitly distinguish:

• MNP (problem): the Minimum Norm Point problem
• FW-MNP: the Fujishige-Wolfe algorithm used to solve MNP

Again, we thank the reviewer for their encouraging assessment and insightful questions.

Response to Reviewer xHD5

We sincerely thank the reviewer for their thoughtful and encouraging feedback.

We address your comments and questions below:

(1) Clarification of Problem 4 (HNSN):

You are correct — this was a typo. The summation in the objective should indeed be over the solution set $S$, not over all of $R$. We will fix this typo in the revised version.

(2) Binary Search and Flow-Based Algorithms:

This is a valid question — binary search is efficient in general, and much faster than simply enumerating all possible density thresholds $\lambda$. Our intention was to indicate that earlier flow-based algorithms for densest subgraph problems used binary search over the density threshold $\lambda$, requiring a full max-flow computation at each step of the search. The need for high-precision convergence and repeated max-flow computations can makes this approach impractical at scale.

For example, if we search for $\lambda$ in the range from $1/n$ to $n/2$ (the range of feasible densities), and aim for a precision of $\epsilon = 0.001$, the number of binary search steps required is roughly $\geq 30$ for $n\geq 2,000,000$. This translates to 30 full max-flow computations for graphs with $n \sim 10^6$. Each such computation is costly in runtime and memory.

In contrast, the density-improvement method (e.g., Huang et al. [32], Hochbaum [31]) iteratively updates $\lambda_k$ by solving

and typically converges in fewer than 3-4 iterations. This is because the number of "critical" values for $\lambda$ — points at which the optimal solution changes — is small in practice. Thus, density improvement "prunes" the solution space more quickly than sequential halving in binary search while achieving the same optimal result.

We will clarify this example in the final version to better explain the practical difference.

(3) On Pseudo-Polynomial Time of SUPERGREEDY++ (Theorem 14):

This is an important observation. Indeed, the iteration bound in Theorem 14 depends on a function-dependent term involving the function $f$, and therefore SUPERGREEDY++ is not guaranteed to run in strongly or weakly polynomial time under our current analysis — in that sense, you are absolutely correct that it is pseudo-polynomial.

We would also like to point out that even in the original analysis of SUPERGREEDY++ for the DSS problem by Chekuri et al. (SODA 2022), the convergence rate includes a term $\Delta_f$ that is a pseudopolynomial in the input parameters (the function $f$). Our understanding of the precise convergence rate of SuperGreedy++ is still limited even when the function is non-negative and monotone. We will clarify this point in the revision.

(Minor Suggestion – Citation Style):

Thank you for the suggestion. We agree and will revise citation phrasings like “[31] states” to “Huang et al. [31] state” for better readability and consistency with the literature.

Additional Improvements:

Following your helpful suggestion, we plan to add a table of acronyms in the longer version to improve readability for new readers and reduce cognitive overhead.

Once again, we truly appreciate your detailed and supportive review. We believe the revisions and clarifications above will further strengthen the clarity, accuracy, and impact of the paper.