{"id":"73c1310d-4bc9-43fd-af8f-23ef209f1ba6","arxiv_id":"1908.06300","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every fixed k and g, maximum-weight stable sets can be found in polynomial time in graphs with odd cycle packing number at most k and Euler genus at most g.","lead":"This paper gives a polynomial-time algorithm for the maximum-weight stable set problem in graphs with a bounded number of node-disjoint odd cycles that can also be embedded in a fixed surface. It also derives polynomial-size extended formulations for the stable set polytopes of these graphs, plus a new Erdős-Pósa theorem for 2-sided odd cycles.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 45 misdefines the facewidth threshold q, so the proof of Theorem 4 is not complete for orientable surfaces; the preprocessing step of the main algorithm depends on Theorem 4.","rationale":"The reader's verdict is CONDITIONAL, and I agree that the central claims are likely correct but not unconditionally established. The reader's weakest_assumption focused on computability of the Robertson-Seymour bound b(g,k) in Theorem 43. I think that external dependency is less concerning, because the paper explicitly cites published sources [15,23] for computability and the argument does not otherwise depend on the numerical value of b(g,k). The more load-bearing internal issue is in Theorem 45 itself: the proof of Theorem 4, on which the reduction in Section 4 depends, has a definite error in the definition of q and an explicitly sketchy orientable-case paragraph. The q=max/min mistake breaks the application of Theorem 41 for orientable surfaces, and the orientable-case comment is not a complete proof. These are not fatal to the overall mathematical program: q can be replaced by the min, and the orientable case is covered by known results or by filling in the sketched argument. However, as written, the proof of the preprocessing lemma is incomplete, so the polynomial-time algorithm of Theorem 2 is not fully supported until that lemma is repaired. This leaves the reader's CONDITIONAL verdict unchanged: the paper should be accepted only after the orientable case of Theorem 4 is either fully proved or explicitly derived from a cited theorem.","tokens_in":31809,"tokens_out":36657,"duration_ms":377050,"concrete_test":"Re-derive Theorem 45, Case 2 with q := min{ floor((t-9)/8), floor((t-1)/4) } and verify the full chain of inequalities: q >= m(g,k) + c(g,k) follows from t >= 8m(g,k) + 8c(g,k) + 9; q - |X1| - |X2| >= c; the facewidth of J is at least c; and b - 6g >= k + 1 holds after taking b(g,k) large enough. If all steps go through for both orientable and non-orientable surfaces, then the q error is typographical. Separately, either replace the orientable 'comment' with a complete proof or explicitly invoke the known orientable-surface Erdős-Pósa theorem; if neither can be done, Theorem 4 is not fully proven and the reduction in Section 4 lacks a justified bound on the deletion set X.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reduction from Problem 1 to Problem 2 in Section 4 (Assumption 1) rests entirely on Theorem 4, whose proof is Theorem 45. In Theorem 45, Case 2 defines q := max{ floor((t-9)/8), floor((t-1)/4) } and then asserts the equality q = floor((t-9)/8). This equality is false: the second term is always at least as large as the first. With q as defined, Theorem 41's orientable hypothesis (t-9)/8 >= q is not guaranteed, so the claimed q pairwise node-disjoint surface-separating, noncontractible, pairwise homotopic cycles need not exist when S is orientable. The subsequent paragraph, labelled 'a comment about the orientable case,' attempts to repair this, but it is explicitly a sketch: it changes the Case 1 threshold and asserts that the proof is concluded 'quickly' without carrying out the linkage step, the parity argument, or the final contradiction. Since the paper sets out to prove Theorem 2 for graphs embedded in any surface of bounded Euler genus, both orientable and non-orientable, and since the small deletion set X that powers the reduction to the standard assumptions comes from Theorem 4, this is a real gap in the proof chain. The gap is likely repairable: q should be the minimum, not the maximum, of the two floor terms, and the orientable case could also be supplied by the known Kawarabayashi-Nakamoto result. But as written, the central claim is conditional on completing this part of the proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the maximum-weight stable set problem in graphs whose odd cycle packing number is bounded by a fixed constant k and that are embeddable in a fixed surface of Euler genus at most g. The main result, Theorem 2, claims a polynomial-time algorithm for this problem, and Theorem 3 claims a polynomial-size extended formulation for the corresponding stable set polytopes. The proof strategy is a chain of reductions: first a preprocessing step, based on a new Erdős-Pósa-type theorem for 2-sided odd cycles in embedded graphs, reduces the problem to graphs satisfying standard parity and connectivity assumptions; then polyhedral reformulations move from node space to edge space, through an alternating orientation of the dual graph, to a minimum-cost integer circulation problem in a prescribed homology class; finally this circulation problem is solved by enumerating short decompositions and running min-cost flow in a finite cover graph. The paper also proves structural results of independent interest, including an Erdős-Pósa theorem for 2-sided odd cycles with a linear bound in the orientable case.","tokens_in":32019,"tokens_out":18338,"duration_ms":177112,"significance":"If the proof gap identified below is repaired, the paper settles the bounded-genus case of a long-standing open problem and provides the first polynomial-time exact algorithm for this family beyond the previously known cases ocp(G)=0 and ocp(G)=1. The algebraic and algorithmic skeleton is substantial and mostly convincing: Section 6 (Proposition 14), Section 8 (Proposition 20 and Corollary 21), and the cover-graph circulation algorithm in Section 9 are detailed and internally consistent, with no circularity or fitted parameters. The claimed linear Erdős-Pósa bound for orientable surfaces would also strengthen the earlier exponential bound of Kawarabayashi and Nakamoto. However, the proof of the Erdős-Pósa theorem in Section 10 is incomplete as written, and since that theorem underpins the preprocessing step of the main algorithm, the central claims are currently conditional on a local but load-bearing repair.","major_comments":[{"comment":"In Case 2 the proof defines q := max{floor((t-9)/8), floor((t-1)/4)} and then asserts the equality q = floor((t-9)/8). This equality is false: for every t >= 9, floor((t-1)/4) is at least floor((t-9)/8), and for most t it is strictly larger. Consequently, when S is orientable, the orientable hypothesis of Theorem 41, namely (t-9)/8 >= q, is not guaranteed, so the claimed existence of q pairwise node-disjoint, surface-separating, noncontractible, pairwise homotopic cycles does not follow. Since Theorem 4 is the basis of the reduction in Section 4, Assumption 1, and hence of Theorem 2 for orientable surfaces, this is a load-bearing gap. It is repairable: taking q := floor((t-9)/8), which is the minimum of the two floors, still satisfies q >= m(g,k) + c(g,k) from the Case 2 lower bound on t, and it makes both bullets of Theorem 41 applicable. The proof should be corrected accordingly.","section":"Section 10, Theorem 45, Case 2"},{"comment":"The concluding paragraph, labelled 'a comment about the orientable case,' is explicitly a sketch. It changes the Case 1 threshold, asserts an inequality involving q and the f(gi,k), and then claims that the contradiction follows 'quickly' from the arguments of (5), without carrying out the linkage step, the parity argument, or the application of Theorem 43. Because the orientable linear bound is part of the statement of Theorem 4, and because Theorem 4 is the theorem invoked in the preprocessing of the main algorithm, this sketch must either be expanded into a complete proof or Theorem 4 must be weakened to the existential bound after the correction described in the previous comment.","section":"Section 10, final paragraph"}],"minor_comments":[{"comment":"The recession cone of the unit-flow polytopes in the cover graph is described as the 'space of circulations'; it should be the cone of non-negative circulations, since the flows are required to be non-negative. The terminology should be adjusted to avoid ambiguity.","section":"Section 9 and Section 12.3"},{"comment":"The proof cites 'Lemma 23' to bound the number of pairwise node-disjoint cycles with pairwise distinct homology classes; the correct reference appears to be Lemma 22, which states exactly this bound, with Lemma 23 being used inside the proof of Lemma 22.","section":"Section 10, proof of Lemma 24"},{"comment":"The notation f(g)*k is used in the algorithm overview and in Assumption 1, while Theorem 4 states a function f(g,k). The notation should be aligned to avoid suggesting a product that has not been defined.","section":"Sections 3 and 4"},{"comment":"The sentence 'We leave to the reader to check that Lemma 16 is actually true for all graphs' is an unproved assertion. Since only connected non-bipartite graphs are needed later, the statement should either be proved in full generality or explicitly restricted to the case used in the paper.","section":"Section 5, Lemma 16"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main thing to know: this paper delivers the goods. For fixed k and g, it gives a polynomial-time algorithm for max-weight stable set in graphs with odd cycle packing number at most k embedded in a surface of Euler genus at most g, plus polynomial-size extended formulations for the stable set polytope. The architecture is a clean chain of reductions: preprocess to standard assumptions using a new Erdos-Posa theorem for 2-sided odd cycles, transform the stable set problem into a min-cost homologous circulation problem, then solve that via a cover graph and min-cost flow. The extended formulation in Section 12 is a nice payoff of the same machinery.\n\nWhat is genuinely new: the Erdos-Posa theorem for 2-sided odd cycles in non-orientable surfaces, and the improved linear bound for orientable surfaces. The reduction to homologous circulations, and the identity STAB(G) = P(G) cap [0,1]^V, are also interesting in their own right. I checked the algebraic core (Sections 5 through 9): Proposition 14, Corollary 21, and the flow decomposition in Lemma 24 are coherent, and the arguments are detailed. I found no circularity and no fitted parameters.\n\nThe soft spots are real but small. The bigger one is in Theorem 45, Case 2: it defines q as the maximum of floor((t-9)/8) and floor((t-1)/4), then asserts q = floor((t-9)/8). That equality is false; the second term is always at least as large. With q as the max, the orientable hypothesis of Theorem 41 is not met, so the claimed disjoint homotopic cycles are not guaranteed for orientable surfaces. This looks like a one-character typo -- q should be the minimum, which equals floor((t-9)/8) -- but as written it leaves the proof incomplete for orientable S. The follow-up \"comment about the orientable case\" is explicitly a sketch and does not repair the gap. Note, though, that for the main algorithm the orientable case can fall back on Kawarabayashi-Nakamoto's earlier Erdos-Posa bound, so Theorem 2 likely survives regardless. The other soft spot is minor: the computable bound b(g,k) from Robertson-Seymour is cited without an explicit expression, which is standard and acceptable in this line of work.\n\nBottom line: this deserves a serious referee. I would send it out, asking the authors to fix q (take the minimum) and to expand the orientable-case proof or clearly mark the linear bound as relying on a known result. The paper is a solid contribution either way.","headline":"Strong, likely-correct algorithm for stable set in bounded-genus bounded-OCP graphs; one repairable typo in the Erdos-Posa proof needs fixing before the orientable case is airtight.","tokens_in":32638,"tokens_out":5780,"would_cite":true,"duration_ms":52250,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C85","05C69","90C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"For graphs embedded in a fixed surface with at most k node-disjoint odd cycles, the maximum-weight stable set is polynomial-time computable.","keywords":["stable set problem","odd cycle packing number","Erdős-Pósa property","graph embeddings","Euler genus","homologous circulations","extended formulations","surface topology"],"falsifier":"Exhibit a projective-planar graph family with $\\mathrm{ocp}(G)\\le k$ whose smallest vertex set meeting all 2-sided odd cycles has size greater than $114k$; this would directly contradict the projective-plane base case (Theorem 36) of the Erdős-Pósa theorem and therefore break the preprocessing step on which the polynomial-time algorithm rests.","tokens_in":31539,"feed_emoji":"🧮","tokens_out":11365,"duration_ms":100592,"temperature":0.7,"pith_summary":"The paper targets a long-standing question: is the maximum-weight stable set problem polynomial for graphs whose odd cycle packing number is bounded by a constant? It proves the answer is yes for graphs that can also be embedded in a fixed surface, orientable or not. The proof runs through a chain of reductions, ending at a minimum-cost non-negative integer circulation in a prescribed homology class, which is solvable in polynomial time for fixed genus. Along the way the paper shows that 2-sided odd cycles satisfy an Erdős-Pósa-type property in fixed-surface embeddings, and that the resulting stable set polytopes have polynomial-size extended formulations.","feed_headline":"Stable sets are polynomial on bounded-genus, low-ocp graphs","feed_subtitle":"If true, it settles a long-open complexity case and yields small linear descriptions of the stable set polytope.","key_machinery":"The load-bearing objects are the affine map $\\sigma(x)=1-Mx$ from node space to edge space, the alternating orientation $D$ of the dual graph, and the homology class of integer circulations. The affine map turns the stable set polytope into $Q(G)$, whose integer points are exactly non-negative integer edge vectors with alternating-sum parity conditions; using the alternating orientation of the dual, $Q(G)$ becomes the set of non-negative integer circulations homologous to the all-one circulation, i.e. whose homology class is $(1,0)$ in $H_1(S;\\mathbb{Z})\\cong\\mathbb{Z}_2\\times\\mathbb{Z}^{g-1}$. Solving the resulting minimum-cost homologous circulation problem by decomposing vertices into $O(g)$ strongly connected Eulerian subgraphs and using min-cost flows on a cover graph yields the algorithm. The Erdős-Pósa-type bound for 2-sided odd cycles is the preprocessing engine that reduces the general input to one satisfying parity-consistent standard assumptions.","core_discovery":"The paper's central claim is that bounded odd cycle packing number plus bounded Euler genus makes the weighted stable set problem polynomial: for fixed $k$ and $g$, every graph $G$ with $\\mathrm{ocp}(G)\\le k$ embedded in a surface of Euler genus at most $g$ has a maximum-weight stable set computable in polynomial time, and its stable set polytope has a polynomial-size extended formulation. The argument establishes this by an equivalence chain: the original problem reduces to maximizing a linear function over the unbounded polyhedron $P(G)=\\operatorname{conv}\\{x\\in\\mathbb{Z}^{V(G)}:Mx\\le 1\\}$, where $M$ is the edge-node incidence matrix; an affine transformation sends this to a polyhedron $Q(G)$ whose integer points are non-negative integer circulations in an alternatingly oriented dual graph that are homologous to the all-one circulation. The remaining task, minimum-cost circulation in a fixed homology class, is solved in polynomial time for fixed genus by decomposing vertices into $O(g)$ Eulerian subgraphs and using min-cost flows on a cover graph. A separate result, the Erdős-Pósa theorem for 2-sided odd cycles in fixed surfaces, supplies the preprocessing that makes the reduction to parity-consistent embeddings possible.","pith_inferences":["One testable extension: because the orientable bound in the Erdős-Pósa theorem is explicit and linear in $k$, the main bottleneck for a fully self-contained proof is the non-orientable case; making the computable bound $f(g,k)$ explicit would turn the preprocessing step from an existence result into a practical procedure.","The reduction to homologous circulations suggests that the same strategy could be tried for signed graphs or for parity constraints on walks with prescribed winding numbers, where a similar chain of dual orientations and homology classes might apply.","If the paper's Conjecture 48 is true, the homologous-circulation step would run in $g^{O(g)}n^{3/2}$ time, upgrading the polynomial-time algorithm to one with explicit genus dependence; testing the conjecture on small genus-2 and genus-3 instances would be a tractable first step.","The identity $\\mathrm{STAB}(G)=P(G)\\cap[0,1]^{V(G)}$ may characterize a broader class of 0/1 matrices beyond edge-node incidence matrices; a natural test is to classify which clutter matrices satisfy it, using the paper's counterexample as the boundary case."],"forward_implications":["For every fixed $k$ and $g$, maximum-weight stable sets in graphs with $\\mathrm{ocp}(G)\\le k$ embedded in a surface of Euler genus at most $g$ can be computed in polynomial time.","The stable set polytope of every such graph admits a polynomial-size extended formulation, so the separation problem for that polytope is also tractable.","In fixed surfaces, 2-sided odd cycles satisfy the Erdős-Pósa property, with a linear bound $19^{g+1}k$ in the orientable case; this strengthens the earlier orientable-surface result and answers its question about linear bounds.","The paper's reductions show that in this setting the stable set problem is equivalent to finding a minimum-cost non-negative integer circulation in a fixed homology class, making the topology of the surface the only remaining source of hardness.","The identity $\\mathrm{STAB}(G)=P(G)\\cap[0,1]^{V(G)}$ holds for edge-node incidence matrices of all graphs, even though it fails for general 0/1 matrices; this makes the unbounded polyhedron $P(G)$ a valid proxy for the stable set polytope in both the algorithm and the extended formulation."],"supporting_citations":[{"why":"Supplies the planar odd-cycle transversal bound $6|C|$ used as the sphere base case and inside the projective-plane and torus reductions.","marker":"[20]"},{"why":"Gives the toroidal facewidth result that a high-facewidth torus embedding contains many disjoint noncontractible cycles, used in the torus base case.","marker":"[32]"},{"why":"Provides the toroidal grid-minor theorem used to force all cycles of the nonplanar toroidal block to be even.","marker":"[9]"},{"why":"Supplies the disjoint-paths theorems on surfaces (cylinder and one-hole cases) that the high-facewidth induction uses to construct $k+1$ disjoint 2-sided odd cycles.","marker":"[31]"},{"why":"Gives sufficient conditions for many disjoint noncontractible homotopic surface-separating cycles, used to set up the cylinder in the high-facewidth case.","marker":"[6]"},{"why":"Bounds the number of pairwise non-freely-homotopic disjoint simple closed curves in a surface, used in both the vertex decomposition and the ear-parity counting.","marker":"[22]"},{"why":"Establishes computability of the disjoint-paths bound behind the Erdős-Pósa theorem; without it the function $f(g,k)$ would not be known to be computable.","marker":"[15]"},{"why":"Also establishes computability of the same disjoint-paths bound via a different route, cited alongside [15] for the computable function $b(g,k)$.","marker":"[23]"},{"why":"Provides the LP-based reduction that makes node weights edge-induced, a required preprocessing step before the edge-space transformation.","marker":"[26]"},{"why":"Supplies the disjunctive-programming theorem used to assemble the polynomial-size extended formulation from a union of flow polytopes.","marker":"[3]"}],"fun_headline_variants":["Stable set is polynomial for bounded genus and odd cycle packing","Polynomial stable set algorithm for bounded genus and ocp graphs","New poly-time stable set when genus and odd cycle packing bounded","Stable set polytope gets small formulation under genus and ocp","Erdos-Posa for 2-sided odd cycles yields stable set poly time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm's first step assumes a computable bound $f(g,k)$ on how many vertices must be deleted to destroy all 2-sided odd cycles in any fixed-genus graph with no $k+1$ disjoint such cycles; the paper cites the bound as computable rather than explicit, so its existence is the load-bearing premise.","fun_headline_variants_meta":{"raw":{"variants":["Stable set is polynomial for bounded genus and odd cycle packing","Polynomial stable set algorithm for bounded genus and ocp graphs","New poly-time stable set when genus and odd cycle packing bounded","Stable set polytope gets small formulation under genus and ocp","Erdos-Posa for 2-sided odd cycles yields stable set poly time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000846,"raw_usage":{"total_tokens":3703,"prompt_tokens":990,"completion_tokens":2713,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":606,"completion_tokens_details":{"reasoning_tokens":2622}},"tokens_in":606,"tokens_out":2713,"duration_ms":17819,"temperature":1.0,"reasoning_tokens":2622,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:51:35.185011+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a projective-planar graph family with $\\mathrm{ocp}(G)\\le k$ whose smallest vertex set meeting all 2-sided odd cycles has size greater than $114k$; this would directly contradict the projective-plane base case (Theorem 36) of the Erdős-Pósa theorem and therefore break the preprocessing step on which the polynomial-time algorithm rests.","supporting_citations":[{"cited_title":"Kráľ, J.-S","cited_arxiv_id":null,"evidence_quote":"Supplies the planar odd-cycle transversal bound $6|C|$ used as the sphere base case and inside the projective-plane and torus reductions."},{"cited_title":"Schrijver","cited_arxiv_id":null,"evidence_quote":"Gives the toroidal facewidth result that a high-facewidth torus embedding contains many disjoint noncontractible cycles, used in the torus base case."},{"cited_title":"de Graaf and A","cited_arxiv_id":null,"evidence_quote":"Provides the toroidal grid-minor theorem used to force all cycles of the nonplanar toroidal block to be even."},{"cited_title":"Robertson and P","cited_arxiv_id":null,"evidence_quote":"Supplies the disjoint-paths theorems on surfaces (cylinder and one-hole cases) that the high-facewidth induction uses to construct $k+1$ disjoint 2-sided odd cycles."},{"cited_title":"Brunet, B","cited_arxiv_id":null,"evidence_quote":"Gives sufficient conditions for many disjoint noncontractible homotopic surface-separating cycles, used to set up the cylinder in the high-facewidth case."},{"cited_title":"Malnič and B","cited_arxiv_id":null,"evidence_quote":"Bounds the number of pairwise non-freely-homotopic disjoint simple closed curves in a surface, used in both the vertex decomposition and the ear-parity counting."},{"cited_title":"Geelen, T","cited_arxiv_id":null,"evidence_quote":"Establishes computability of the disjoint-paths bound behind the Erdős-Pósa theorem; without it the function $f(g,k)$ would not be known to be computable."},{"cited_title":"Matoušek, E","cited_arxiv_id":null,"evidence_quote":"Also establishes computability of the same disjoint-paths bound via a different route, cited alongside [15] for the computable function $b(g,k)$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the LP-based reduction that makes node weights edge-induced, a required preprocessing step before the edge-space transformation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the disjunctive-programming theorem used to assemble the polynomial-size extended formulation from a union of flow polytopes."}],"review_version":1}