- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies a network design problem that is useful in distributed learning. In particular, we are given as input a directed graph together with a special root node and terminal set , a demand , a demand (both integers at least one) for each , edge costs , and a budget . We need to find a subgraph with at most edges such that for every there are at least edge-disjoint paths from to and at least edge-disjoint paths from to . The goal is to minimize the total cost of our subgraph. In other words, it is the directed survivable network design problems (Directed-SNDP) with a single source and an edge cardinality constraint. They design a dynamic programming algorithm that depends exponentially on the treewidth of the underlying undirected graph and the sum of the number of bits needed to represent the demands. Note that since each demand requires at least one bit, this means that they depend exponentially on . They also provide a number of experiments.
Critical strengths
- The problem might be interesting.
Critical weaknesses
I do not think that this paper should be accepted to ICLR. While I think that the problem is reasonable as a network design problem (i.e., it could be an interesting special case of directed SNDP), the writing is poor, the algorithm is not particularly interesting, and the results are somewhat weak.
-
The writing is a major issue. I read the abstract and intro and still did not understand what the problem was. It wasn't until they formally define it in Section 2 that I finally understood it. Their informal explanations earlier are written too poorly to be understandable. And then, in the actual formal definition in Section 2, their technical writing is also quite poor: they use notation and concepts without defining them, switch between formal and informal, etc. For example, in Theorem 2 on page 2 they use a tree decomposition. But this isn't defined until Section 4.1 on page 4, and even there they do not cite this definition (although they obviously did not invent it). Then in Section 4.1, they use a bunch of terms either without defining them or with crazy definitions. As a short set of examples, but from the 1/2 page of Section 4.1"
- They use "root, introduce-vertex nodes, forget-vertex nodes, equal-bag two-child joins, and introduce-arc nodes" without defining any of them.
- They say "For a partial binary flow...", but never define what a "partial binary flow" actually is. From the type of the object it seems to be a subgraph (each edge is assigned zero or one), in which case calling it a "flow" is crazy writing.
- In Lemma 6 the statement of the lemma is about "binary witnesses", but a "binary witness" is never defined.
- In equation (3), is never defined. It is presumably a vertex, but from what set? ? Or ? Even ignoring this issue, equation (3) is, if I'm interpreting it correctly, just out-degree - in-degree for a particular subgraph. This is not a hard concept, but the current writing completely obscures it.
-
The algorithm and analysis are not particularly interesting. It seems to be a basically standard use of a tree decomposition to get a DP algorithm -- there are thousands of such algorithms, particularly in the FPT literature. If there is anything new and exciting, then the authors did not highlight it (another sign of poor writing). The correctness and complexity arguments take less than a page combined (although while they use earlier lemmas, the earlier lemmas are all essentially trivial). Moreover, the authors themselves say that there are already known ways to get algorithms for bounded treewidth (see the discussion just before Section 2). So there doesn't seem to be much that is of deep interest.
-
I was incredibly underwhelmed by the experimental results. All of their graphs are just small grids! What about realistic graphs? Or if you are going to use grids, they should at least be big! I think the largest grid they used was something like 30 nodes. If you're going to evaluate algorithms experimentally, you at least need to do it on graphs big enough to demonstrate why anyone should care. And even on these graphs, it seems like using a standard MILP approach is usually (almost always) better.
So in my opinion, this is a poorly written paper about an algorithm that isn't great in practice and isn't very interesting theoretically.
Questions for authors
None
2 comments
Thanks for the response. I will leave my rating where it is.
Definitions, proof details, and the quantitative contribution
Thank you for identifying where the presentation obstructed the argument. The reader should not have to reconstruct the model or states. We address each example, then novelty and evaluation.
Problem statement and order of definitions. The problem is to choose a minimum-cost set of at most ℓ directed arcs so that, for every worker t, there are bt+ arc-disjoint coordinator-to-worker paths and bt− arc-disjoint return paths. Different requirements may share an arc, whose cost is paid once. We will put this before the application discussion and define tree decompositions before Theorem 2, citing Cygan et al. (2015, Chapter 7). Neither is claimed as new.
The decomposition nodes and the missing domains. A tree decomposition has bags covering all vertices, both endpoints of each arc in some bag, and connected bags for every fixed vertex. Its width is the largest bag size minus one. In the rooted normalization, root and leaves have empty bags. Relative to its child, an introduce-vertex node adds one vertex and a forget-vertex node removes one. An introduce-arc node has the same bag and processes one uniquely assigned original arc whose endpoints lie in it. A join has two children with exactly the parent's bag. Unique arc assignment makes their processed arc sets disjoint.
For node x, Vx is the union of bags in its subtree and Ax is its processed arc set. Equation (3) is defined for v∈Vx, but only values at v∈Bx are stored. It is outdegree minus indegree in the selected subgraph. We will say so explicitly.
A complete witness for requirement g=(sg,tg,bg) is the indicator of the union of bg simple arc-disjoint sg–tg paths. At completion its divergence is bg at sg, −bg at tg, and zero elsewhere. General binary flows may also contain removable circulations. Lemma 6 uses a path-union witness: each vertex has at most bg incoming and outgoing selected arcs. After restriction to any Ax, both counts remain in [0,bg], so their difference lies in [−bg,bg]. The bound holds at every node, but not for arbitrary assignments.
At the root, all conservation equations have been checked. Integral unit-capacity flow decomposition supplies the required disjoint paths. Removing a circulation from one requirement removes only that requirement's arc uses, not another requirement's certificate. Nonnegative union costs and an at-most budget make this harmless. This is why connectivity pairings can be omitted without a soundness gap.
You are correct that the bound is exponential in workers. The distinction is polynomial dependence on multiplicity for fixed width and requirement count. Chalermsook et al. (2018) already provide rooted survivable-design algorithms with another parameter dependence. Feldmann et al. (2025) establish directed demand-two hardness and related undirected tractability. We claim neither novelty for qualitative FPT alone nor uniform improvement over those algorithms. The significance question is the quantitative guarantee, not the number of proof steps.
References:
[1] Cygan et al. (2015), Parameterized Algorithms, Chapter 7, Springer.
[2] Chalermsook et al. (2018), “Survivable Network Design for Group Connectivity in Low-Treewidth Graphs,” APPROX/RANDOM.
[3] Feldmann et al. (2025), “The Parameterized Complexity of the Survivable Network Design Problem,” JCSS.