Pith. sign in

REVIEW 2 major objections 4 minor 37 references

The stable set problem in graphs with bounded genus and bounded odd cycle packing number

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For graphs embedded in a fixed surface with at most k node-disjoint odd cycles, the maximum-weight stable set is polynomial-time computable.

desk verdict 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. read the letter →

arxiv 1908.06300 v1 pith:THOBR2QR submitted 2019-08-17 cs.DM cs.DSmath.COmath.OC

Michele Conforti , Samuel Fiorin , Tony Huynh , Gwenaël Joret , Stefan Weltge This is my paper · ORCID
classification cs.DMcs.DSmath.COmath.OC MSC 05C1005C8505C6990C10
keywords stablesetproblemoddcyclepackingnumberErdős-PósapropertygraphembeddingsEulergenushomologouscirculationsextendedformulationssurfacetopology
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [Section 10, Theorem 45, Case 2] 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.
  2. [Section 10, final paragraph] 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.
minor comments (4)
  1. [Section 9 and Section 12.3] 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.
  2. [Section 10, proof of Lemma 24] 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.
  3. [Sections 3 and 4] 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.
  4. [Section 5, Lemma 16] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is a chain of independent polyhedral equivalences plus an externally grounded Erdős-Pósa theorem.

full rationale

The paper's main algorithm is built from explicit polyhedral equivalences (Sections 5–9) that connect the stable set problem to a minimum-cost homologous circulation problem; these are proofs, not fitted predictions, and none of the intermediate objects (P(G), Q(G), dual representations, cover graphs) are defined in terms of the target algorithm's output. The only preprocessing step that could raise a concern is Assumption 1, which invokes Theorem 4 to delete a small set X hitting all 2-sided odd cycles. Theorem 4 is proved in Section 10 from independent external results (planar odd-cycle min-max theorems, toroidal results, Brunet–Mohar–Richter, Robertson–Seymour disjoint paths with computable bounds from [15,23]); it is not derived from, nor equivalent to, the stable-set theorem. The self-citations to [14] and [15] are ordinary references to independent prior work and are not load-bearing in the sense of importing the target conclusion. The mathematical issue noted by the reviewer—the misdefinition of q as a maximum in Theorem 45, Case 2, and the sketchy orientable-case comment—would be a correctness gap if sustained, not a circularity: it concerns whether an external lemma supplies the required separator, not whether the paper's derivation assumes what it proves. Since no equation or fitted parameter reintroduces the conclusion as an input, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 10 assumptions · 0 invented entities

The central claims rest on standard topological facts and on several deep theorems from the graph minors and surface embedding literature. All such inputs are external, cited results, not fitted or adjusted to the present problem. No free parameters are introduced: the constants in the algorithm and in the Erdős-Pósa bounds are either problem inputs (k, g) or explicitly computed from them. The only place where an input is asserted without a displayed formula is the computable function b(g,k) in Theorem 43, whose existence is cited to [15,23].

assumptions (10)
  • standard math Classification of surfaces: every surface is homeomorphic to S(h,c) with Euler genus 2h+c.
    Used in Section 2 to define Euler genus and throughout the paper to set up embeddings.
  • standard math Euler's formula for cellular embeddings: g = 2 + |E| - |V| - |F|.
    Used in Lemma 18 to compute the dimension of the circulation space.
  • standard math H1(S; Z) is isomorphic to Z_2 × Z^{g-1} for non-orientable surfaces of Euler genus g.
    Used in Section 8 to justify that the map ω distinguishes homology classes of circulations.
  • domain assumption Nemhauser-Trotter theorem and LP duality.
    Used in Section 4, Assumption 3, to reduce arbitrary node weights to edge-induced weights.
  • domain assumption Odd cycle transversal and packing in planar graphs: Theorem 30 (Kráľ-Sereni-Stacho), |X| ≤ 6|C|.
    Serves as the sphere base case and is used repeatedly in the torus and projective plane proofs.
  • domain assumption Robertson-Seymour disjoint paths theorems on surfaces (Theorems 42 and 43).
    Core engine in the inductive step of Theorem 4 to construct linkages and packings of 2-sided odd cycles.
  • domain assumption Brunet-Mohar-Richter Theorem 41 giving many disjoint noncontractible separating cycles when facewidth is large.
    Used in Case 2 of the proof of Theorem 4 to obtain a cylinder D containing the cycles C1,...,Cq.
  • domain assumption de Graaf-Schrijver grid minor theorem and Schrijver's torus facewidth theorem (Theorems 38 and 39).
    Used in the toroidal base case Theorem 40.
  • domain assumption Malnič-Mohar bound on the number of homotopy classes of disjoint noncontractible curves (Proposition 3.6).
    Used in property (7) of Theorem 4 to show at most 3g of the constructed cycles are 2-sided.
  • standard math Balas' union-of-polyhedra extended formulation theorem and Chvátal's clique cutset lemma.
    Used in Section 12 to assemble the polynomial-size extended formulation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The stable set problem in graphs with bounded genus and bounded odd cycle packing number." pith.science (2026). https://pith.science/paper/THOBR2QR

@misc{pith2026190806300,
  author       = {Pith},
  title        = {Pith review of: The stable set problem in graphs with bounded genus and bounded odd cycle packing number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/THOBR2QR}},
  note         = {Machine review of arXiv:1908.06300}
}
abstract

Consider the family of graphs without $ k $ node-disjoint odd cycles, where $ k $ is a constant. Determining the complexity of the stable set problem for such graphs $ G $ is a long-standing problem. We give a polynomial-time algorithm for the case that $ G $ can be further embedded in a (possibly non-orientable) surface of bounded genus. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that $2$-sided odd cycles satisfy the Erd\H{o}s-P\'osa property in graphs embedded in a fixed surface. This extends the fact that odd cycles satisfy the Erd\H{o}s-P\'osa property in graphs embedded in a fixed orientable surface (Kawarabayashi & Nakamoto, 2007). Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which turns out to be efficiently solvable in our case.

Figures

Figures reproduced from arXiv: 1908.06300 by the authors.

Figure 1
Figure 1. Using the neighborhood of an edge, one can compare local orientations around its ends. In the above case, the local orientations are inconsistent and hence the edge belongs to Σ. We are almost ready to prove Lemma 17. However, before doing so, we require a more combinatorial definition of 1-sided and 2-sided closed walks. Let G be a graph embedded in a surface S. Regardless of the (global) orientability of S, one ca… view at source ↗
Figure 2
Figure 2. If the local orientations around the nodes of the graph (dots and dashed edges) are inconsistent along edges, then they induce an orientation of the dual graph (squares and solid arcs). that Σ4δ(v1)4 · · · 4δ(vk) = E(G). This means that if we reverse the local orientations around the nodes v1, . . . , vk, the induced signature changes to Σ = E(G). In this case, the local orientations around the ends of each edge mus… view at source ↗
Figure 3
Figure 3. A graph whose node-edge incidence matrix does not satisfy Equation (8). Lemma 50. Let G be any graph, and let v0 be any fixed node of G. The projection of P(G) onto the coordinates indexed by V (G − v0) equals P(G − v0). Proof. To see that the projection of P(G) is contained in P(G−v0), it suffices to prove that every integer point x ∈ P(G) projects to a point in P(G − v0). Let x 0 ∈ Z V (G−v0) be the projection of … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    Armstrong.Basic Topology

    M. Armstrong.Basic Topology. Undergraduate Texts in Mathematics. Springer-Verlag New York, 1983

    work page 1983

  2. [2]

    Artmann, R

    S. Artmann, R. Weismantel, and R. Zenklusen. A strongly polynomial algorithm for bimodular integer linear programming. InSTOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1206–1219. ACM, New York, 2017

    work page 2017

  3. [3]

    E. Balas. Disjunctive programming.Ann. Discrete Math., 5:3–51, 1979. Discrete optimization (Proc. Adv. Res. Inst. Discrete Optimization and Systems Appl., Banff, Alta., 1977), II

    work page 1979

  4. [4]

    A. Bock, Y. Faenza, C. Moldenhauer, and A. J. Ruiz-Vargas. Solving the stable set problem in terms of the odd cycle packing number. In34th International Conference on Foundation of Software Technology and Theoretical Computer Science, volume 29 ofLIPIcs. Leibniz Int. Proc. Inform., pages 187–198. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2014

    work page 2014

  5. [5]

    Bonifas, M

    N. Bonifas, M. Di Summa, F. Eisenbrand, N. Hähnle, and M. Niemeier. On sub-determinants and the diameter of polyhedra.Discrete & Computational Geometry, 52(1):102–115, 2014

    work page 2014

  6. [6]

    Brunet, B

    R. Brunet, B. Mohar, and R. B. Richter. Separating and nonseparating disjoint homotopic cycles in graph embeddings.J. Combin. Theory Ser. B, 66(2):201–231, 1996

    work page 1996

  7. [7]

    E. W. Chambers, J. Erickson, and A. Nayyeri. Homology flows, cohomology cuts.SIAM J. Comput., 41(6):1605–1634, 2012

    work page 2012

  8. [8]

    V. Chvátal. On certain polytopes associated with graphs.J. Combin. Theory Ser. B, 18:138–154, 1975

    work page 1975

Show all 37 references
  1. [9]

    de Graaf and A

    M. de Graaf and A. Schrijver. Grid minors of graphs on the torus.J. Combin. Theory Ser. B, 61(1):57–62, 1994

    1994

  2. [10]

    Dyer and A

    M. Dyer and A. Frieze. Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Program., 64(1-3):1–16, 1994

    1994

  3. [11]

    J. Edmonds. A combinatorial representation for polyhedral surfaces.Notices Amer. Math. Soc., 7:646, 1960

    1960

  4. [12]

    Eisenbrand and S

    F. Eisenbrand and S. Vempala. Geometric random edge.Math. Program., 164(1-2):325–339, 2017

    2017

  5. [13]

    D. B. A. Epstein. Curves on2-manifolds and isotopies.Acta Math., 115:83–107, 1966

    1966

  6. [14]

    Fiorini, N

    S. Fiorini, N. Hardy, B. Reed, and A. Vetta. Approximate min-max relations for odd cycles in planar graphs. Math. Program., 110(1, Ser. B):71–91, 2007

    2007

  7. [15]

    Geelen, T

    J. Geelen, T. Huynh, and R. B. Richter. Explicit bounds for graph minors.J. Combin. Theory Ser. B, 132:80–106, 2018

    2018

  8. [16]

    J. W. Grossman, D. M. Kulkarni, and I. E. Schochetman. On the minors of an incidence matrix and its smith normal form.Linear Algebra and its Applications, 218:213–224, 1995

    1995

  9. [17]

    Kawarabayashi, B

    K.-i. Kawarabayashi, B. Mohar, and B. Reed. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 771–780. IEEE, 2008

    2008

  10. [18]

    Kawarabayashi and A

    K.-i. Kawarabayashi and A. Nakamoto. The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces.Discrete Math., 307(6):764–768, 2007

    2007

  11. [19]

    Kawarabayashi and K

    K.-i. Kawarabayashi and K. Ozeki. A simpler proof for the two disjoint odd cycles theorem.J. Combin. Theory Ser. B, 103(3):313–319, 2013

    2013

  12. [20]

    Kráľ, J.-S

    D. Kráľ, J.-S. Sereni, and L. Stacho. Min-max relations for odd cycles in planar graphs.SIAM J. Discrete Math., 26(3):884–895, 2012

    2012

  13. [21]

    Lokshtanov, S

    D. Lokshtanov, S. Saurabh, and S. Sikdar. Simpler parameterized algorithm for OCT. InCombinatorial Algorithms, 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28-July 2, 2009, Revised Selected Papers, pages 380–384, 2009

    2009

  14. [22]

    Malnič and B

    A. Malnič and B. Mohar. Generating locally cyclic triangulations of surfaces.J. Combin. Theory Ser. B, 56(2):147–164, 1992

    1992

  15. [23]

    Matoušek, E

    J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner. Untangling two systems of noncrossing curves. Israel J. Math., 212(1):37–79, 2016

    2016

  16. [24]

    B. Mohar. Face-width of embedded graphs.Mathematica Slovaca, 47(1):35–63, 1997

    1997

  17. [25]

    Mohar and C

    B. Mohar and C. Thomassen.Graphs on surfaces. Johns Hopkins University Press, Baltimore, U.S.A., 2001

    2001

  18. [26]

    G. L. Nemhauser and J. L. E. Trotter. Properties of vertex packing and independence system polyhedra. Math. Program., 6:48—-61, 1974

    1974

  19. [27]

    J. Paat, M. Schlöter, and R. Weismantel. Most IPs with bounded determinants can be solved in polynomial time. arXiv:1904.06874, 2019. STABLE SETS IN BOUNDED GENUS, BOUNDED OCP GRAPHS 30

    1904 arXiv

  20. [28]

    T. D. Parsons, G. Pica, T. Pisanski, and A. G. Ventre. Orientably simple graphs.Mathematica Slovaca, 37(4):391–394, 1987

    1987

  21. [29]

    B. Reed. Mangoes and blueberries.Combinatorica, 19(2):267–296, 1999

    1999

  22. [30]

    B. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals.Operations Research Letters, 32:299– 301, 2004

    2004

  23. [31]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph minors. VII. Disjoint paths on a surface.J. Combin. Theory Ser. B, 45(2):212–254, 1988

    1988

  24. [32]

    Schrijver

    A. Schrijver. Graphs on the torus and geometry of numbers.J. Combin. Theory Ser. B, 58(1):147–158, 1993

    1993

  25. [33]

    P. D. Seymour. Matroid minors. InHandbook of combinatorics, Vol. 1, 2, pages 527–550. Elsevier Sci. B. V., Amsterdam, 1995

    1995

  26. [34]

    D. Slilaty. Projective-planar signed graphs and tangled signed graphs.J. Combin. Theory Ser. B, 97(5):693–717, 2007

    2007

  27. [35]

    E. Tardos. A strongly polynomial algorithm to solve combinatorial linear programs.Operations Research, 34(2):250–256, 1986

    1986

  28. [36]

    S. Tazari. Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs. Theoret. Comput. Sci., 417:95–107, 2012

    2012

  29. [37]

    S. I. Veselov and A. J. Chirkov. Integer program with bimodular matrix.Discrete Optimization, 6(2):220–222, 2009

    2009

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.