REVIEW 4 major objections 5 minor 1 cited by
The Landscape of Minimum Label Cut (Hedge Connectivity) Problem
T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper claims that any minimum label cut instance with overlapping labels can be rewritten in polynomial time as a weighted instance with disjoint labels, preserving the optimum.
desk verdict The paper's central transformation is invalid because Lemma 1 is false, so the claimed hardness transfer collapses, though the critique of the rainbow-path operation is worth a footnote. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Operation K is the central machinery. It reads each overlapping edge as a set of labels, takes the transitive closure of set intersections (a union-find merge), and replaces each closure class with a single new label whose weight is the size of the class. The paper also uses the label degree $DL(v)$, the number of distinct labels on edges incident to $v$, as a bound on the weights created by the relabeling. Lemma 1 is the load-bearing identity: co-occurrence of two labels on one edge is treated as full mutual correlation, so merging those labels should not affect which edge sets must be removed to disconnect the graph.
What would settle it
On a path $s$--$a$--$b$--$t$, give edge $(s,a)$ label $A$, edge $(a,b)$ labels $\{A,B\}$, and edge $(b,t)$ label $B$. The minimum label $s$-$t$ cut is 1, since removing $A$ or $B$ alone disconnects $s$ from $t$; after operation K merges $A$ and $B$ into one label of weight 2, the weighted minimum cut is 2, which would show the transformation does not preserve hedge connectivity.
Extended reading notes
Core claim
On the paper's own terms, the discovery is Theorem 1: operation K transforms any undirected graph with overlapping edge labels into a graph with one label per edge and positive integer weights, and the minimum label cut (hedge connectivity) value is unchanged. The proof route is Lemma 1, which asserts that two labels sharing an edge are correlated, so every edge carrying either label is removed together; Corollary 1 then relabels each overlap-connected group by a new label with weight equal to the group size. The paper concludes that hardness for weighted non-overlapping label cut, such as APX-hardness for the $s$-$t$ version, carries over to the overlapping version, and it derives corresponding lower bounds from vertex-cover hardness. It further claims that the label-count function on edge subsets is submodular, in both the overlapping and non-overlapping settings.
Load-bearing premise
The transformation rests on the assumption that if two labels appear together on one edge, removing either label removes every edge carrying the other label; if this correlation is not complete, merging the labels can change the minimum cut.
Editorial extensions
If this is right
- Any polynomial-time algorithm for weighted non-overlapping minimum label cut becomes an algorithm for the overlapping version with the same approximation guarantee.
- The overlapping version cannot admit a PTAS under the stated conditions on longest path, label frequency, and treewidth, and it inherits the $\sqrt{2}$ inapproximability bound when the longest $s$-$t$ path is bounded by 2.
- The global overlapping version inherits the strong inapproximability bounds stated in Corollaries 3 and 6.
- The submodularity of the label-count function gives a structural property that could be used in further algorithm design for both versions.
- The paper's correction of the earlier rainbow-path replacement means the two versions can no longer be related by that simple edge-subdivision trick.
Reading between the lines
- Because operation K is defined purely by set intersections among labels, the same rewriting would apply to hypergraph hedge cuts whenever each hedge is a set of edges, allowing weighted graph-cut algorithms to run on those instances after relabeling.
- In network-failure terms, the transformation turns shared-risk labels into a single weighted failure resource, so routing problems phrased over shared-risk link groups could inherit min-cut algorithms directly.
- The minimal test case for the reduction is a single edge carrying two labels that otherwise appear separately; checking whether the minimum cut is unchanged on that instance is the fastest way to see how much of the correlation assumption is needed.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Minimum Label Cut (Hedge Connectivity) problem in four variants: s-t versus global, and non-overlapping versus overlapping labels. Its central contribution is a claimed polynomial-time transformation, called operation K, from the overlapping-label version to a weighted non-overlapping version, based on a purported Lemma 1 about label correlation. From this transformation the paper derives NP-hardness and APX-hardness results (Theorems 3 and 4), several approximation lower-bound corollaries, and a submodularity property for the label cut function. The paper also criticizes the rainbow-path replacement proposed by Ghaffari, Karger, and Panigrahi as not hedge-connectivity preserving.
Significance. If the central transformation were correct, it would unify the overlapping and non-overlapping versions of the problem and would transfer known hardness and approximation results to the overlapping case. The paper's critique of the rainbow-path replacement has some merit, and the paper correctly identifies that the hedge cut function is not submodular in the sense used in [9]. However, the central technical lemma is false, and the main results depend on it. The paper does not provide machine-checked proofs, reproducible code, or a parameter-free derivation that survives scrutiny. The significance of the paper as a contribution is therefore limited by a load-bearing error in its core reduction.
major comments (4)
- [Section 3, Lemma 1] Lemma 1 is false as stated. The lemma asserts that if one edge e carries labels Li and Lj, then selecting Li for removal also removes every other edge labeled Lj. Co-occurrence on a single edge only means that that edge belongs to both hedges; it does not imply that the two labels are globally correlated or that the hedge of Lj is a subset of the hedge of Li. A concrete counterexample is a path s-a with label A, a-b with labels {A,B}, and b-t with label B. The original minimum label s-t cut is 1 (select A, which removes the first two edges and disconnects s from t). After applying operation K, all three edges carry a single label C of weight 2, so the transformed minimum label cut value becomes 2. Thus the transformation does not preserve hedge connectivity.
- [Section 3, Theorem 1 and Corollary 1] Because Theorem 1 rests entirely on Lemma 1, its preservation claim is unsupported and in fact false. Corollary 1, which relabels every edge carrying Li or Lj as a single new label of weight 2, over-counts cuts that need only one of the two labels; the weight-2 relabeling can increase the objective value of a label cut. The proof of Theorem 1 also appears to conflate the number of labels incident to a vertex with the weight of a merged hedge; the bound using min or max label degree does not follow from the definitions given.
- [Section 4, Theorem 3] Theorem 3 claims NP-hardness for Minimum Label s-t Cut with Label Overlaps via a reduction from Hitting Set, but the reduction is not stated in a verifiable way. The construction refers to applying operation K and to Menger's theorem, but does not specify the graph, the label assignment, or how the hitting set solution maps to a label cut. Moreover, since operation K does not preserve the optimum, the reduction cannot establish the claimed hardness. The proof would need a formal, self-contained construction that does not rely on the false Lemma 1.
- [Section 4, Theorem 4 and Corollaries 2-6] The APX-hardness result and all the approximation lower-bound corollaries are derived by first applying operation K and then invoking known results for weighted non-overlapping Minimum Label s-t Cut. Since operation K is not optimality-preserving, these results are unsupported. In particular, Corollary 2 and Corollary 4 state inapproximability for very restricted graph classes, but no proof is given that the instances obtained by the required reduction satisfy those restrictions after the transformation.
minor comments (5)
- [Abstract] The phrase 'the label cut problem(hedge connectivity) problem asks' is awkwardly repeated; 'edge sets(each edge set (or hedge) is the edges with the same label) whose removal disconnects' needs grammatical cleanup, and the abbreviation 's−t' should be typeset consistently as 's-t' throughout.
- [Section 2, Definitions 1-4] Definitions 1 and 2 are identical in wording except for the phrase 'one or multiple labels'; this should be clarified explicitly, and the paper would benefit from using distinct names for the s-t and global variants consistently rather than both being called 'Minimum Label s-t Cut problem' in Definition 2.
- [Section 3, Figure 1 discussion] The argument that the rainbow-path replacement changes the hedge connectivity uses DL(v) values, but the connection between label degree and hedge connectivity is asserted in Property 1 without proof; a formal proof of Property 1 would make the discussion more rigorous.
- [Section 4.2, Lemmas and corollaries] Corollary 6 states that the Minimum Label Cut problem with Label Overlaps cannot be approximated within (1-o(1)) ln n unless P=NP, but the proof is not given and the relationship to the Set Cover lower bound is only implicit; a citation or a short derivation would be helpful.
- [References] Reference [10] is cited as Khot, Minzer, and Safra for the 2-to-2 games result, but the exact venue and version should be checked; also, the paper cites its own prior work [7] for the NP-hardness of the global overlapping version, but the reader would benefit from a more detailed account of what is proved in [7] versus what is new here.
Circularity Check
No significant circularity; the paper's central flaw is a false correlation lemma, and the only by-construction result is a bookkeeping identity about merged weights.
-
self definitional
[Section 3, Theorem 1(3) and its proof; compare Corollary 1 and Figure 2]
"As after label replacement step, correlated labels(have nonempty overlaps in some edges) is replaced by a new label with weight to be the number of such correlated labels, each label with other label correlations only replaced by one new label, thus the total weight of hedges in the new graph is exactly equal to the total number of hedges of the original graph."
This theorem item is true by construction. Corollary 1 defines the new label's weight as 1+1 = 2 for a merged pair, and operation K assigns each new label a weight equal to the number of original labels in the union set. Therefore the equality between total new weight and the number of original hedges is an immediate restatement of the weight definition, not an independently derived hedge-connectivity fact. It is a bookkeeping identity rather than evidence that the transformation preserves minimum label cut. The actual preservation claim rests on Lemma 1, which is false, but that falsehood is a correctness error, not a circular derivation.
full rationale
The paper does not fit parameters to data, rename a fitted value as a prediction, or define the target optimum in terms of the transformed optimum. Its central claimed contribution, operation K preserving hedge connectivity, is invalid because Lemma 1 wrongly asserts that two labels co-occurring on one edge are globally removal-correlated; a four-vertex path example shows the transformed optimum can change from 1 to 2. That is a serious mathematical error, but it is not circularity. The one genuinely by-construction piece is Theorem 1(3): because the new label weights are defined as counts of merged original labels, the stated total-weight equality is a direct consequence of the construction rather than a derived result. The paper also cites its own prior work [7] for NP-hardness of the global overlapping version, but the main transformation and the claimed s-t hardness proof do not depend on that citation as their load-bearing premise, so the self-citation is minor and not circular. The derivation chain is therefore not circular in the sense of reducing to its inputs, even though it is unsound for independent reasons.
Assumptions & free parameters
assumptions (6)
- ad hoc to paper If an edge carries labels Li and Lj, then selecting Li removes all edges labeled Lj (Lemma 1, Section 3).
- ad hoc to paper Operation K preserves hedge connectivity (Section 3, Theorem 1).
- domain assumption Weighted Minimum Label s-t Cut is APX-hard [3].
- standard math Menger's theorem gives a polynomial-time computable minimum edge cut equal to the maximum number of edge-disjoint paths.
- standard math Hitting set is NP-complete [12].
- domain assumption The 2-to-2 games result [10] gives NP-hard approximation of Vertex Cover within sqrt(2).
invented entities (1)
-
Merged labels L'_t produced by operation K
Cite this review
Pith. "Pith review of The Landscape of Minimum Label Cut (Hedge Connectivity) Problem." pith.science (2026). https://pith.science/paper/P47PWCW2
@misc{pith2026190806541,
author = {Pith},
title = {Pith review of: The Landscape of Minimum Label Cut (Hedge Connectivity) Problem},
year = {2026},
howpublished = {\url{https://pith.science/paper/P47PWCW2}},
note = {Machine review of arXiv:1908.06541}
}
abstract
Minimum Label Cut (or Hedge Connectivity) problem is defined as follows: given an undirected graph $G=(V, E)$ with $n$ vertices and $m$ edges, in which, each edge is labeled (with one or multiple labels) from a label set $L=\{\ell_1,\ell_2, ..., \ell_{|L|}\}$, the edges may be weighted with weight set $W =\{w_1, w_2, ..., w_m\}$, the label cut problem(hedge connectivity) problem asks for the minimum number of edge sets(each edge set (or hedge) is the edges with the same label) whose removal disconnects the source-sink pair of vertices or the whole graph with minimum total weights(minimum cardinality for unweighted version). This problem is more general than edge connectivity and hypergraph edge connectivity problem and has a lot of applications in MPLS, IP networks, synchronous optical networks, image segmentation, and other areas. However, due to limited communications between different communities, this problem was studied in different names, with some important existing literature citations missing, or sometimes the results are misleading with some errors. In this paper, we make a further investigation of this problem, give uniform definitions, fix existing errors, provide new insights and show some new results. Specifically, we show the relationship between non-overlapping version(each edge only has one label) and overlapping version(each edge has multiple labels), by fixing the error in the existing literature; hardness and approximation performance between weighted version and unweighted version and some useful properties for further research.
Figures
Forward citations
Cited by 1 Pith paper
-
Color-avoiding connected colorings and orientations
Graphs admiting color-avoiding connected colorings are exactly the sufficiently connected graphs, and for simple connectivity the minimum number of colors is computable in polynomial time.
Reference graph
Works this paper leans on
-
[7]
Farag´ o, Andr´ as. ”A graph theoretic model for complex network failure scenarios.” In Proceedings of the Eighth INFORMS Telecommunications Conference, Dallas, Texas. 2006
work page 2006
-
[9]
Karger, and Debmalya Panigrahi
Ghaffari, Mohsen, David R. Karger, and Debmalya Panigrahi. ”Random contrac- tions and sampling for hypergraph and hedge connectivity.” In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1101-
-
[1]
Coudert, David, Pallab Datta, St´ ephane P´ erennes, Herv´ e Rivano, and M-E. Voge. ”Shared risk resource group complexity and approximability issues.” Parallel Pro- cessing Letters 17, no. 02 (2007): 169-184
work page 2007
-
[2]
Jha, Somesh, Oleg Sheyner, and Jeannette Wing. ”Two formal analyses of attack graphs.” In Proceedings 15th IEEE Computer Security Foundations Workshop. CSFW-15, pp. 49-63. IEEE, 2002
work page 2002
-
[3]
Zhang, Peng, Jin-Yi Cai, Lin-Qing Tang, and Wen-Bo Zhao. ”Approximation and hardness results for label cut and related problems.” Journal of Combinatorial Op- timization 21, no. 2 (2011): 192-208. 10 Rupei Xu, Andr´ as Farag´ o
work page 2011
-
[4]
Tang, Linqing, and Peng Zhang. ”Approximating minimum label s-t cut via linear programming.” In Latin American Symposium on Theoretical Informatics, pp. 655-
-
[5]
Broersma, Hajo, Xueliang Li, Gerhard J. Woeginger, and Shenggui Zhang. ”Paths and cycles in colored graphs.” Australasian J. Combinatorics 31 (2005): 299-312
work page 2005
-
[6]
Fellows, Michael R., Jiong Guo, and Iyad Kanj. ”The parameterized complexity of some minimum label problems.” Journal of Computer and System Sciences 76, no. 8 (2010): 727-740
work page 2010
Show all 15 references
-
[8]
”Efficient algorithms for the label cut problems.” In International Conference on Theory and Applications of Models of Computation, pp
Zhang, Peng. ”Efficient algorithms for the label cut problems.” In International Conference on Theory and Applications of Models of Computation, pp. 259-270. Springer, Cham, 2014
2014
-
[10]
”Pseudorandom sets in grassmann graph have near-perfect expansion.” 2018 IEEE 59th Annual Symposium on Foun- dations of Computer Science (FOCS)
Subhash, Khot, Dor Minzer, and Muli Safra. ”Pseudorandom sets in grassmann graph have near-perfect expansion.” 2018 IEEE 59th Annual Symposium on Foun- dations of Computer Science (FOCS). IEEE, 2018
2018
-
[11]
”On the hardness of approximating minimum vertex cover.” Annals of mathematics (2005): 439-485
Dinur, Irit, and Samuel Safra. ”On the hardness of approximating minimum vertex cover.” Annals of mathematics (2005): 439-485
2005
-
[12]
”Reducibility among combinatorial problems.” Complexity of computer computations
Karp, Richard M. ”Reducibility among combinatorial problems.” Complexity of computer computations. Springer, Boston, MA, 1972. 85-103
1972
-
[13]
”On weighted vs un- weighted versions of combinatorial optimization problems.” Information and Com- putation 167.1 (2001): 10-26
Crescenzi, Pierluigi, Riccardo Silvestri, and Luca Trevisan. ”On weighted vs un- weighted versions of combinatorial optimization problems.” Information and Com- putation 167.1 (2001): 10-26
2001
-
[666]
Springer, Berlin, Heidelberg, 2012
2012
-
[1114]
Society for Industrial and Applied Mathematics, 2017
2017
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.