{"id":"ceeaa40f-3a16-4e01-ae00-4fad72250fce","arxiv_id":"1908.06541","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper's label-merging operation does not preserve minimum label cut values, so its central reduction and derived hardness results are unsupported.","lead":"This paper studies the Minimum Label Cut problem, in which edges carry labels and a cut removes all edges of selected labels to disconnect the graph. It proposes a polynomial-time transformation from overlapping-label instances to weighted non-overlapping instances and claims new hardness results, but the transformation is invalid.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Operation K rests on Lemma 1, which asserts that two labels co-occurring on one edge are globally correlated; this is false, and a four-vertex path shows K changes the optimum from 1 to 2.","rationale":"The reader's strongest claim identifies exactly the same load-bearing defect: Lemma 1 is false, and operation K does not preserve minimum label cut values. This is not a minor technical gap; the counterexample is a simple four-vertex path whose optimum changes under the proposed transformation. Since operation K is the bridge from the overlapping version to the weighted non-overlapping version, every theorem and corollary that relies on that bridge loses its proof in this paper. The paper's criticism of Ghaffari, Karger, and Panigrahi's rainbow-path operation may be valid, and some of the submodularity observations are correct, but those pieces do not support the paper's main positive claims. There is also a secondary problem in Theorem 3: the promised construction from hitting set to an s-t label cut instance is only described in one sentence and no concrete graph is specified, so even if operation K were correct, the proof would be incomplete. However, the false Lemma 1 is already sufficient to invalidate the central argument. The verdict should remain REJECT, as no part of the core transformation survives scrutiny.","tokens_in":6818,"tokens_out":2981,"duration_ms":33147,"concrete_test":"Run a brute-force check on the four-vertex path s-a (label A), a-b (labels {A,B}), b-t (label B): enumerate all label subsets to compute the original optimum, then apply operation K exactly as stated and compute the optimum of the transformed weighted instance. Assert the two optima are equal. The test fails because the original optimum is 1 and the transformed optimum is 2. Automate this check over all labeled paths with up to five edges to confirm the mismatch is not an artifact of the single example.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 1 in Section 3 is the load-bearing step. It claims that if an edge carries labels Li and Lj, then selecting Li removes not only that edge but every edge carrying Lj. Co-occurrence on one edge only means that one edge belongs to both hedges; it does not imply the two hedges are identical or globally correlated. This invalidates Corollary 1 and operation K, which relabel every edge carrying Li or Lj as a single new label of weight 2. The transformation over-counts cuts that need only one of the two labels. Concretely, let G be the 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: selecting A removes the first two edges and disconnects s from t. After operation K, all three edges carry a single label C with weight 2, so the transformed minimum label cut has value 2. Thus Theorem 1's preservation claim is false. Because Theorem 3, Theorem 4, and Corollaries 2-6 are derived through operation K, those results are unsupported. The paper's critique of the rainbow-path replacement has merit, but the proposed replacement does not preserve hedge connectivity.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7007,"tokens_out":1826,"duration_ms":18716,"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":[{"comment":"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":"Section 3, Lemma 1"},{"comment":"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":"Section 3, Theorem 1 and Corollary 1"},{"comment":"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":"Section 4, Theorem 3"},{"comment":"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.","section":"Section 4, Theorem 4 and Corollaries 2-6"}],"minor_comments":[{"comment":"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":"Abstract"},{"comment":"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":"Section 2, Definitions 1-4"},{"comment":"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":"Section 3, Figure 1 discussion"},{"comment":"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.","section":"Section 4.2, Lemmas and corollaries"},{"comment":"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.","section":"References"}],"recommendation":"reject","confidential_remarks":"The paper's central transformation is demonstrably incorrect, and most of the claimed new results depend on it. The paper also relies heavily on the authors' own prior work [7] and on known results without providing self-contained proofs. While the observation that the rainbow-path replacement is flawed may be of some interest, it is not sufficient to support publication in a serious journal without a correct replacement technique. I would recommend reject rather than major revision, since the main mechanism proposed here is not salvageable within the paper's current scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, quick take on arXiv:1908.06541. The paper aims to unify overlapping and non-overlapping versions of minimum label cut, fix an error in Ghaffari-Karger-Panigrahi, and transfer hardness/approximation results. The fix and transfer hinge on operation K, which is unsound. Lemma 1 says two labels that share one edge are globally correlated: if you remove one, you remove all edges of the other. That is false. Co-occurrence on a single edge only means that one edge is covered by both hedges. The path s-a (label A), a-b (labels A,B), b-t (label B) gives min label s-t cut 1 (pick A), but after merging A and B into one label of weight 2, the cut value becomes 2. So operation K does not preserve hedge connectivity, and Theorem 1 is false. Everything built on it — Theorems 3 and 4, Corollaries 2-6 — is unsupported. The proof of Theorem 3 is also not a real reduction; it gestures at hitting set and Menger but doesn't construct a graph.\n\nOn the positive side, the paper does correctly identify a real issue in GKP's rainbow-path replacement: replacing an overlap edge with a path whose edges each carry one label makes the new path vertices separable by two labels, so hedge connectivity can drop. That criticism seems valid and is the only genuinely new observation here. But the paper's own proposed replacement is broken, so the paper as a whole doesn't deliver.\n\nThe submodularity properties are correct but trivial — the label-counting function on edge sets is obviously submodular; this doesn't address the actual cut objective.\n\nCitation pattern: the paper leans heavily on the authors' own earlier work [7] for NP-hardness, which is not a problem by itself, but the new hardness claims are not independent.\n\nWho is this for? Someone tracking the hedge connectivity literature might skim the GKP critique, but the paper's main results are not usable. I would not send it to referees in its current form; if the authors want to publish the rainbow-path critique, that should be a short note or a comment, not a landscape paper with invalid hardness theorems.\n\nRecommendation: reject. Don't spend referee time on the current version.","headline":"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.","tokens_in":7578,"tokens_out":1925,"would_cite":false,"duration_ms":19080,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C40","05C85","68Q17","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["minimum label cut","hedge connectivity","label overlaps","operation K","weighted transformation","approximation hardness","submodularity","graph cut"],"falsifier":"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.","tokens_in":6520,"feed_emoji":"✂️","tokens_out":9617,"duration_ms":94857,"temperature":0.7,"pith_summary":"The paper aims to give a unified treatment of four minimum label cut (hedge connectivity) problems, distinguished by source-sink versus global cuts and by whether edges carry one label or several. Its central claim is that every instance with overlapping labels can be converted in polynomial time into an equivalent weighted instance whose edges each have one label, using operation K: labels that co-occur on an edge are merged into a single new label whose weight is the number of merged labels. If this conversion preserves the minimum label cut, then algorithms and inapproximability results for weighted non-overlapping instances transfer immediately to the overlapping case, and the paper uses that transfer to state APX-hardness and concrete approximation lower bounds for overlapping instances. The paper also argues that an earlier rainbow-path replacement in the literature does not preserve hedge connectivity, and it records submodularity properties of the label-count cut function.","feed_headline":"Overlapping label cuts reduce to weighted cuts in polynomial time","feed_subtitle":"The merge operation preserves the minimum cut, so known hardness and approximation results carry over.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the earlier rainbow-path transformation that the paper argues does not preserve hedge connectivity and that motivates operation K.","marker":"[9]"},{"why":"Gives the NP-hardness of the overlapping global label cut and the path-vulnerability setting used as background.","marker":"[7]"},{"why":"Provides the APX-hardness of the weighted non-overlapping label $s$-$t$ cut that the paper transfers to overlapping instances.","marker":"[3]"},{"why":"Supplies the NP-completeness of hitting set, the starting problem in the paper's new $s$-$t$ hardness proof.","marker":"[12]"},{"why":"Gives the 2-to-2-games resolution that yields the vertex-cover hardness bound used in Corollaries 4 and 5.","marker":"[10]"}],"fun_headline_variants":["Overlapping label cuts collapse to weighted cuts","One label per edge suffices for label cut reduction","Merging overlapping labels preserves min cut","Fix: Overlap label cuts reduce to weighted case"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Overlapping label cuts collapse to weighted cuts","One label per edge suffices for label cut reduction","Merging overlapping labels preserves min cut","Fix: Overlap label cuts reduce to weighted case"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000222,"raw_usage":{"total_tokens":1484,"prompt_tokens":1009,"completion_tokens":475,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":625,"completion_tokens_details":{"reasoning_tokens":416}},"tokens_in":625,"tokens_out":475,"duration_ms":5261,"temperature":1.0,"reasoning_tokens":416,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:42:02.172796+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Karger, and Debmalya Panigrahi","cited_arxiv_id":null,"evidence_quote":"Supplies the earlier rainbow-path transformation that the paper argues does not preserve hedge connectivity and that motivates operation K."},{"cited_title":"”A graph theoretic model for complex network failure scenarios.” In Proceedings of the Eighth INFORMS Telecommunications Conference, Dallas, Texas","cited_arxiv_id":null,"evidence_quote":"Gives the NP-hardness of the overlapping global label cut and the path-vulnerability setting used as background."},{"cited_title":"”Approximation and hardness results for label cut and related problems.” Journal of Combinatorial Op- timization 21, no","cited_arxiv_id":null,"evidence_quote":"Provides the APX-hardness of the weighted non-overlapping label $s$-$t$ cut that the paper transfers to overlapping instances."},{"cited_title":"”Reducibility among combinatorial problems.” Complexity of computer computations","cited_arxiv_id":null,"evidence_quote":"Supplies the NP-completeness of hitting set, the starting problem in the paper's new $s$-$t$ hardness proof."},{"cited_title":"”Pseudorandom sets in grassmann graph have near-perfect expansion.” 2018 IEEE 59th Annual Symposium on Foun- dations of Computer Science (FOCS)","cited_arxiv_id":null,"evidence_quote":"Gives the 2-to-2-games resolution that yields the vertex-cover hardness bound used in Corollaries 4 and 5."}],"review_version":1}