{"id":"3341b61b-0ddc-45ee-9b7a-23c43e3e0460","arxiv_id":"2411.14553","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A transfer theorem for boundary classes under bi-reductions is stated, but its converse is incomplete and several claimed new boundary classes apply only to restricted problem variants.","lead":"This paper claims a theorem that transfers boundary classes between NP-hard graph problems connected by bijective reductions, and applies it to produce new boundary classes for seven problems. The theorem has proof gaps and several applications overclaim results for restricted versions of TSP, subgraph-isomorphism, and bounded-degree-spanning-tree.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3 only transfers boundary classes relative to the image container f_G(A); the applications then assert absolute boundary classes, even though each reduction is a bijection onto a proper slice of the target (k=2, k=0, H=K_n), so the minimality proof cannot rule out hard classes outside the…","rationale":"The reader's verdict is REJECT with high confidence, and the identified weakest assumption is exactly the slice-relativity problem. My read confirms that the central transfer theorem produces only a boundary class relative to the image container f_G(A), while the paper's headline applications claim absolute boundary classes for the full target problems. The reductions in Corollaries 3, 4, 5, and 7 are bijections onto proper slices of the target instance sets: subgraph-isomorphism with H restricted to complete graphs, TSP with budget fixed to 0, and bounded-degree-spanning-tree with degree bound fixed to 2. The proof of Theorem 3 would need to preimage arbitrary Γ-hard hereditary classes, but those preimages are undefined for instances outside the slice, and inverse graph reductions are never shown to preserve hereditary classes. Consequently, the minimality argument does not go through for the full problem, and the claimed 'first boundary classes' for subgraph-isomorphism, TSP, and bounded-degree-spanning-tree are not established. The remaining applications for vertex-cover and clique are essentially known equivalences and do not add substantial novelty. The paper has no machine-checked proofs or reproducible code to offset these gaps. The reader's rejection stands; no verdict change is warranted.","tokens_in":9435,"tokens_out":16189,"duration_ms":168402,"concrete_test":"Test the minimality step of Theorem 3 on Corollary 7. Let Y' be any hereditary class properly contained in Q on which bounded-degree-spanning-tree is NP-hard for k=3 (a natural candidate is the class of subcubic graphs in Q, if such a class is hard; if none is known, test any finite-forbidden subclass that is k=3-hard). Write Y' as an intersection of Γ-hard classes Y'_i; since the bi-reduction f has image Z={⟨G,2⟩}, the instances ⟨G,3⟩ in Y'_i lie outside Z, so the proof step 'f^{-1}(Y'_i) is Π-Hard' cannot be executed. If such Y' exists, Q is not an absolute boundary class for bounded-degree-spanning-tree, and the claimed conclusion fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper defines a boundary class for a problem as a minimal limit class. Theorem 3, however, concludes that f_G(X) is a (Γ, f_G(A))-boundary, i.e. a boundary class relative to a hereditary container f_G(A). The applications silently upgrade this to an absolute boundary class for the full target problem. In every nontrivial application the bi-reduction f is a bijection onto a proper slice Z of the target: Corollary 3 maps clique to subgraph-isomorphism instances with H=K_n; Corollaries 4 and 5 map Hamiltonian cycle to travelling-salesperson instances with budget k=0; Corollary 7 maps Hamiltonian path to bounded-degree-spanning-tree instances with degree bound k=2. The minimality step of Theorem 3 considers a Γ-limit Y'⊂f_G(X) and asserts that each Γ-hard class Y'_i has a Π-hard preimage f^{-1}(Y'_i). But if Y'_i contains instances outside Z, for example a k=3 instance in Corollary 7, then f^{-1} is undefined on those instances and the assertion is meaningless. Even when defined, the preimage of a hereditary class need not be hereditary, a condition never stated. Thus the proof never excludes a proper hereditary subclass of f_G(X) on which the full target problem is NP-hard through parameters outside the slice. The corollaries' phrase 'boundary class for [full problem]' is therefore unsupported; the arguments establish at most a slice-relative boundary, and only after adding the missing inverse-heredity assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines several graph problems in an exact-value form (e.g., α(G)=k, ω(G)=k, β(G)=k) and introduces a transfer theorem (Theorem 3) for boundary classes: if Π and Γ are NP-hard graph problems and f is a bi-reduction from Π to Γ whose graph part f_G is hereditary-closed, then X is a (Π,A)-boundary class if and only if f_G(X) is a (Γ,f_G(A))-boundary class. It then applies this theorem to known boundary classes for independent-set, Hamiltonian cycle/path, and vertex-coloring, claiming seven previously unknown boundary classes for vertex-cover, clique, subgraph-isomorphism, travelling-salesperson (two classes), clique-cover, and bounded-degree-spanning-tree.","tokens_in":9812,"tokens_out":20779,"duration_ms":211530,"significance":"The idea of transporting boundary classes along reductions is natural and, if valid, would be a useful tool for the boundary-class literature. The paper is clearly structured and draws on a substantial body of known boundary-class results. However, the applications do not follow from the theorem as stated: the theorem only yields boundary classes relative to the image slice of the reduction, the converse direction silently assumes an inverse heredity condition, the exact-version problem definitions are unsupported and break Corollary 3, and the hereditary-class framework is not defined for weighted or two-input graph problems such as TSP and subgraph-isomorphism. The advertised results are therefore not established.","major_comments":[{"comment":"The theorem's conclusion is only a relative statement: f_G(X) is a (Γ, f_G(A))-boundary, not an absolute boundary class for Γ. In the proof of the forward direction, after choosing a Γ-limit class Y' ⊂ f_G(X), the proof forms f_G^{-1}(Y'_i); this is legitimate only if each approximating class Y'_i lies in the image f_G(A). The definition of a Γ-limit class does not require the approximating hard classes to lie in f_G(A), and Theorem 3 gives no way to approximate an arbitrary Y' inside f_G(A). The applications ignore this: Corollary 3 maps into the slice H=K_n, Corollaries 4 and 5 map into the slice k=0, and Corollary 7 maps into the slice k=2. For example, in Corollary 7 the proof never rules out a proper hereditary subclass of Q on which bounded-degree-spanning-tree is NP-hard through instances with degree bound k=3, because those instances are outside the reduction's image. The corollaries' claims of boundary classes for the full target problems are therefore not consequences of Theorem 3.","section":"§5, Theorem 3 and Corollaries 3–7"},{"comment":"The 'if' direction requires that f_G^{-1} maps hereditary Γ-hard classes to hereditary Π-hard classes, but the theorem assumes only that f_G is hereditary-closed in the forward direction. The proof states 'as Y'_i is Γ-Hard, f_G^{-1}(Y'_i) is Π-Hard' without argument; this is precisely what must be proved. A bijective graph reduction can be hereditary-closed forward without its inverse being hereditary-closed, so the missing condition is not automatic. The corollaries do not repair this gap: they check only that removing a vertex from a graph in the specific classes T, Q, R(Q), etc. stays in the corresponding image, and none of them proves the required property for arbitrary hereditary classes and arbitrary Γ-hard classes.","section":"§5, Theorem 3 proof, converse direction"},{"comment":"The exact-version decision problems defined in Section 4 are nonstandard and are never shown to be NP-hard or to have the same boundary classes as the standard at-least/at-most versions cited from the literature. Corollary 3 is internally inconsistent: with clique defined by ω(G)=k in Eq. (5), the map f(⟨G,n⟩)=⟨G,K_n⟩ sends a no-instance ⟨G,n⟩ with ω(G)>n to a yes-instance of subgraph-isomorphism, so f is not a reduction, let alone a bi-reduction, from the paper's clique problem. The same unsupported exact-version issue affects Corollaries 1 and 2, where the known boundary class T for independent-set is transferred without any argument that it is a boundary class for the equality version α(G)=k.","section":"§4, Eqs. (1), (5), (6), and Corollary 3"},{"comment":"The boundary-class framework is defined in Section 2 only for unweighted graphs, but the applications to travelling-salesperson and subgraph-isomorphism use inputs that are outside this framework. K(G) is a weighted complete graph, yet the paper never defines induced subgraphs or hereditary classes for weighted graphs; subgraph-isomorphism instances are pairs (G,H), and the graph reduction f_G transforms only the first coordinate, leaving the meaning of f_G(X), of a hereditary class of pairs, and of a Γ-hard class for subgraph-isomorphism unspecified. Without these definitions, Theorem 3 cannot be applied to these problems, and the claims in Corollaries 3–5 are not checkable.","section":"§4 and §5.1, applications to TSP and subgraph-isomorphism"}],"minor_comments":[{"comment":"The sentence 'The inverse L^{-1}(X)' is incomplete; the inverse line-graph transformation is never defined.","section":"§5.1, paragraph after Figure 3"},{"comment":"The final sentence says 'by Theorem 3, K(Q) is a boundary class for traveling-saleperson', but the intended conclusion concerns K(R(Q)); the spelling 'traveling-saleperson' also appears in Corollaries 4 and 5 and should be corrected.","section":"Corollary 5"},{"comment":"The phrase 'a Y-limit class ... of Y' is not formally defined; the definition should state explicitly that each approximating class X_i is a hereditary subclass of Y.","section":"§3, definition of Y-limit class"},{"comment":"The paper asserts that the obtained classes are 'previously unknown' and are the first boundary classes for vertex-cover, clique, TSP, bounded-degree-spanning-tree, clique-cover, and subgraph-isomorphism, but no literature survey supports the 'first' claim; it should be supported or qualified.","section":"Abstract and Conclusion"},{"comment":"The reduction from Hamiltonian path to bounded-degree-spanning-tree is cited only to [7]; a more specific citation, e.g., to the relevant theorem or problem number in that book, would be helpful.","section":"Corollary 7 proof"}],"recommendation":"reject","confidential_remarks":"The transfer theorem is an appealing idea and might be salvageable as a relative-boundary transfer result under an explicit inverse-heredity assumption. However, the paper's central contribution—seven absolute boundary classes for the target problems—rests on the errors described above, and one corollary contains a reduction that is false under the paper's own definitions. I do not see a minor-revision path; the authors would need to substantially rework the theorem's hypotheses, weaken the applications to slice-relative statements, or prove genuinely new absolute boundary results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the transfer idea is sensible and the paper knows the right literature, but as written Theorem 3 is not proven and the corollaries overclaim. The iff in Theorem 3 needs the inverse graph reduction to preserve hereditary classes; the proof's converse silently uses that, and it is not assumed. The forward direction also has a gap: f_G(X_i) is hereditary when X_i is hereditary, which the 'hereditary closed' assumption gives, but you also need the preimage of a Γ-hard class to be a Π-hard class, and that needs the preimage to be hereditary. So the theorem currently gives at most one direction without an extra condition.\n\nThe applications then upgrade slice-relative conclusions to global boundary classes. In Corollaries 3, 4, 5, and 7, the reduction maps into a proper slice of the target: H=K_n for subgraph-isomorphism, budget k=0 for TSP, degree bound k=2 for bounded-degree-spanning-tree. Theorem 3 only yields a boundary class relative to the image container f_G(A). The minimality argument never rules out hard subclasses outside the slice. Corollary 3 is also simply wrong: G contains K_n as a subgraph iff ω(G) ≥ n, not ω(G)=n, so the reduction does not preserve the exact clique problem.\n\nWhat is genuinely useful here: the general idea of transporting boundary classes through bi-reductions, and the simple observations that complement and identity reductions transfer T, co(T), L(T). The vertex-cover and clique corollaries are immediate from known equivalences, not new. The exact-version problem definitions (α(G)=k, etc.) are nonstandard and are not reconciled with the boundary-class literature, which uses the usual decision versions.\n\nI would not send this to referees in its current form. The main theorem's missing hypothesis and the slice-relative overclaims are load-bearing; a revision that adds the inverse-heredity condition and honestly restates the corollaries as slice-relative might rescue a modest toolkit, but as it stands the central claims do not hold.","headline":"A natural transfer idea undermined by a missing converse hypothesis and by applications that upgrade slice-relative boundary classes to global ones.","tokens_in":10269,"tokens_out":9087,"would_cite":false,"duration_ms":85275,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"A hereditary closed bi-reduction between two NP-hard graph problems transfers boundary classes in both directions, yielding the first boundary classes for vertex cover, clique, TSP, bounded-degree spanning tree, clique cover, and subgraph…","keywords":["boundary classes","NP-hard graph problems","reducibility","bi-reduction","hereditary graph classes","independent set","Hamiltonian cycle","traveling salesperson"],"falsifier":"The decisive test is on the slices the reductions actually hit: fix the spanning-tree degree bound at $2$ and solve bounded-degree spanning tree on hereditary subclasses of $Q$; if any finitely defined hereditary subclass of $Q$ is polynomial for this slice while NP-hard for Hamiltonian path, Theorem 1 rules out $Q$ as a boundary class for bounded-degree spanning tree. The same slice test applies to subgraph isomorphism with patterns restricted to complete graphs and to TSP with budget $0$.","tokens_in":9202,"feed_emoji":"🧩","tokens_out":11187,"duration_ms":90611,"temperature":0.7,"pith_summary":"Some NP-hard graph problems become easy once the input is restricted to certain hereditary graph classes; boundary classes are the minimal remaining obstacles that keep a problem hard. This paper claims that a bi-reduction from one NP-hard graph problem to another, whose graph-to-graph part preserves hereditary classes, transfers boundary classes in both directions: $X$ is a boundary class for the source problem exactly when its image is a boundary class for the target. Applying this to known boundary classes for independent set, Hamiltonian cycle, Hamiltonian path, and vertex coloring yields the first boundary classes for vertex cover, clique, traveling salesperson, bounded-degree spanning tree, clique cover, and subgraph isomorphism. If the claim is right, any known reduction between NP-hard graph problems becomes a channel for finding the minimal hard substructures of new problems.","feed_headline":"Boundary classes jump between NP-hard problems via reductions: 6 new","feed_subtitle":"A hereditary-closed bi-reduction moves a hard-case boundary from one graph problem to another, unlocking first classes for six problems.","key_machinery":"The load-bearing device is the bi-reduction $f$ and its graph part $f_G$. A bi-reduction is a polynomial-time reduction whose restriction to a subset of the target is a bijection with a polynomial-time inverse; $f_G$ is the graph-to-graph component, obtained by discarding the parameter part of the mapping. The single condition that carries the argument is that $f_G$ is hereditary closed, meaning the image of every hereditary class is again hereditary; once that holds, boundary classes, which are intersections of descending chains of hereditary hard classes, are preserved under images and preimages. The concrete transforms used in the corollaries are the identity, complementation, the line-graph complement, and the weighted-complete-graph transform $K(\\cdot)$.","core_discovery":"Theorem 3 is the paper's central claim: let $\\Pi$ and $\\Gamma$ be NP-hard graph problems, let $f$ be a bi-reduction from $\\Pi$ to $\\Gamma$, and suppose the graph reduction $f_G$ is hereditary closed. Then a hereditary class $X$ is a $(\\Pi,A)$-boundary if and only if $f_G(X)$ is a $(\\Gamma,f_G(A))$-boundary for some hereditary class $A \\supseteq X$. The proof transfers each class in the descending chain of $\\Pi$-hard classes to the image side, and uses the inverse image to rule out any strictly smaller limit class. The applications use four bi-reductions: the identity graph map with parameter change $k \\mapsto n-k$ (independent set to vertex cover), complementation (independent set to clique and coloring to clique cover), the pattern map $G \\mapsto (G,K_n)$ (clique to subgraph isomorphism), and the weighted-complete-graph transform $K(G)$ with budget $0$ (Hamiltonian cycle to TSP), plus the degree-bound map $G \\mapsto (G,2)$ (Hamiltonian path to bounded-degree spanning tree). The paper presents the seven resulting boundary classes as the first known for these problems.","pith_inferences":["The bi-reductions in Corollaries 3, 4, 5, and 7 land in restricted slices of the target problems---patterns equal to $K_n$, tour budget $0$, and degree bound $2$---so the paper's boundary-class conclusions for subgraph isomorphism, TSP, and bounded-degree spanning tree carry an unstated assumption that hardness on those slices represents the full problem; this extension is not argued in the text.","The converse direction of Theorem 3 silently depends on the inverse graph reduction $f_G^{-1}$ preserving hereditary classes, a hypothesis that the theorem states nowhere; if that inverse closure fails, minimality can fail to transfer.","The $K(G)$ transform produces only complete graphs with $0/1$ edge weights, a highly structured slice of TSP instances; a boundary class proved on that slice may describe a thinner, potentially easier subproblem unless the slice is shown to inherit the full problem's hardness.","A natural next step would be applying the same transfer to other known boundary classes, such as those for dominating set or edge coloring, and checking whether the resulting classes remain boundary classes when the target problem is widened beyond the slice hit by the chosen reduction."],"forward_implications":["If Theorem 3 is correct, every hereditary-closed bi-reduction between NP-hard graph problems makes boundary classes portable, so boundary classes no longer have to be re-derived for each problem from scratch.","Seven concrete boundary classes follow: $T$ for vertex cover, $\\mathrm{co}(T)$ for clique and subgraph isomorphism, $K(Q)$ and $K(R(Q))$ for traveling salesperson, $L(T)$ for clique cover, and $Q$ for bounded-degree spanning tree.","Because the transfer is an if-and-only-if, a strictly smaller limit class on either side would force one on the other side, so the theorem can also be used to certify that a candidate hereditary class is not a boundary class.","Since many NP-complete graph problems are reducible to each other, the theorem gives a general search strategy: pair a problem with a known boundary class and any known bi-reduction to another problem, and the image class is a candidate boundary class for the latter."],"supporting_citations":[{"why":"Introduced boundary classes for the independent-set problem and supplies the boundary class $T$ used in Corollaries 1 and 2.","marker":"[2]"},{"why":"Provides the general definition of boundary classes and the two theorems that tie NP-hardness of hereditary classes to containment of a boundary class.","marker":"[3]"},{"why":"Establishes $Q$ and $R(Q)$ as boundary classes for Hamiltonian cycle, the source classes for the two TSP corollaries.","marker":"[10]"},{"why":"Establishes $Q$ as a boundary class for Hamiltonian path, the source class for the bounded-degree spanning tree corollary.","marker":"[18]"},{"why":"Establishes $\\mathrm{co}(L(T))$ as a boundary class for vertex coloring, the source for the clique-cover corollary.","marker":"[12]"},{"why":"Cited for the reduction from vertex coloring to clique cover used in Corollary 6.","marker":"[8]"},{"why":"Cited for the reductions from clique to subgraph isomorphism and from Hamiltonian path to bounded-degree spanning tree used in Corollaries 3 and 7.","marker":"[7]"},{"why":"Supplies the identities $\\alpha(G)+\\beta(G)=|V(G)|$ and $\\alpha(G)=\\omega(\\overline{G})$ that produce the parameter translations in Corollaries 1 and 2.","marker":"[21]"},{"why":"Cited for the definitions of NP-hardness and polynomial-time reductions on which the notion of bi-reduction builds.","marker":"[20]"}],"fun_headline_variants":["Boundary classes transfer via reductions: new hard cases for six","Reduction trick yields first boundary classes for six NP-hard problems","Six new boundary classes from hereditary-closed reductions","Bi-reductions carry hard-case boundaries across NP-hard problems","First boundary classes for clique, TSP, and more via reductions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The applications assume that a boundary class proved on a restricted slice of the target problem---patterns equal to $K_n$, tour budget $0$, or spanning-tree degree bound $2$---is automatically a boundary class for the full problem, a step the paper does not justify; the converse of Theorem 3 also silently assumes that the inverse graph reduction preserves hereditary classes.","fun_headline_variants_meta":{"raw":{"variants":["Boundary classes transfer via reductions: new hard cases for six","Reduction trick yields first boundary classes for six NP-hard problems","Six new boundary classes from hereditary-closed reductions","Bi-reductions carry hard-case boundaries across NP-hard problems","First boundary classes for clique, TSP, and more via reductions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0004,"raw_usage":{"total_tokens":2139,"prompt_tokens":1043,"completion_tokens":1096,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":659,"completion_tokens_details":{"reasoning_tokens":1012}},"tokens_in":659,"tokens_out":1096,"duration_ms":8107,"temperature":1.0,"reasoning_tokens":1012,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:10:59.311763+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The decisive test is on the slices the reductions actually hit: fix the spanning-tree degree bound at $2$ and solve bounded-degree spanning tree on hereditary subclasses of $Q$; if any finitely defined hereditary subclass of $Q$ is polynomial for this slice while NP-hard for Hamiltonian path, Theorem 1 rules out $Q$ as a boundary class for bounded-degree spanning tree. The same slice test applies to subgraph isomorphism with patterns restricted to complete graphs and to TSP with budget $0$.","supporting_citations":[{"cited_title":"On easy and hard hereditary classes of graphs with respect to the independent set problem","cited_arxiv_id":null,"evidence_quote":"Introduced boundary classes for the independent-set problem and supplies the boundary class $T$ used in Corollaries 1 and 2."},{"cited_title":"NP-hard graph problems and boundary classes of graphs","cited_arxiv_id":null,"evidence_quote":"Provides the general definition of boundary classes and the two theorems that tie NP-hardness of hereditary classes to containment of a boundary class."},{"cited_title":"Boundary properties of graphs for algorithmic graph problems","cited_arxiv_id":null,"evidence_quote":"Establishes $Q$ and $R(Q)$ as boundary classes for Hamiltonian cycle, the source classes for the two TSP corollaries."},{"cited_title":"Boundary classes for graph problems involving non-local properties","cited_arxiv_id":null,"evidence_quote":"Establishes $Q$ as a boundary class for Hamiltonian path, the source class for the bounded-degree spanning tree corollary."},{"cited_title":"On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number","cited_arxiv_id":null,"evidence_quote":"Establishes $\\mathrm{co}(L(T))$ as a boundary class for vertex coloring, the source for the clique-cover corollary."},{"cited_title":"Reducibility among combinatorial problems","cited_arxiv_id":null,"evidence_quote":"Cited for the reduction from vertex coloring to clique cover used in Corollary 6."},{"cited_title":"Computers and Intractability; A Guide to the Theory of NP- Completeness","cited_arxiv_id":null,"evidence_quote":"Cited for the reductions from clique to subgraph isomorphism and from Hamiltonian path to bounded-degree spanning tree used in Corollaries 3 and 7."},{"cited_title":"Introduction to Graph Theory","cited_arxiv_id":null,"evidence_quote":"Supplies the identities $\\alpha(G)+\\beta(G)=|V(G)|$ and $\\alpha(G)=\\omega(\\overline{G})$ that produce the parameter translations in Corollaries 1 and 2."}],"review_version":1}