pith. sign in

arxiv: 2601.11119 · v2 · pith:4RZHF5SGnew · submitted 2026-01-16 · 🧮 math.CO · cs.DM· math.OC

Bond Polytope under Vertex- and Edge-sums

Petr Kolman , Hans Raj Tiwary This is my paper

Pith reviewed 2026-05-16 13:55 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.OC
keywords bond polytopeextension complexity1-sum2-summinor-free graphsmaximum bondpolyhedral combinatorics
0
0 comments X

The pith

The bond polytope of a 1-sum or 2-sum graph is obtained directly from the bond polytopes of its component graphs.

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

A bond in a graph is a cut whose two sides each induce a connected subgraph, and the bond polytope is the convex hull of the indicator vectors of all such bonds. Maximum-weight bond is NP-hard in general, even on planar graphs, yet the problem becomes tractable on graphs that exclude K5 minus an edge as a minor. The paper supplies explicit combination rules that construct the bond polytope of any graph formed by vertex-sum or edge-sum operations from the polytopes of the two summands. These rules are then applied to the known clique-sum decompositions of (K5-e)-minor-free graphs to obtain a linear-size extended formulation for their bond polytopes.

Core claim

We show how to obtain the bond polytope of graphs that are 1- or 2-sum of graphs G1 and G2 from the bond polytopes of G1,G2. Using this we show that the extension complexity of the bond polytope of (K5 minus e)-minor-free graphs is linear. We also describe an elementary linear time algorithm for the MaxBond problem on (K5 minus e)-minor-free graphs.

What carries the argument

Combination rules for vertices and edges under 1-sums and 2-sums that map the vertices and facets of the input bond polytopes onto those of the summed graph without introducing new ones.

If this is right

  • The bond polytope of every (K5-e)-minor-free graph admits a linear-size extended formulation.
  • The maximum-weight bond in any (K5-e)-minor-free graph can be found by an elementary linear-time algorithm that does not rely on bounded-treewidth machinery as a black box.
  • Prior linear-size descriptions were available only for the special case of 3-connected planar (K5-e)-minor-free graphs.
  • The same decomposition technique immediately yields linear extension complexity for any minor-closed class whose members admit 1- and 2-sum decompositions into base graphs with known linear descriptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar composition rules may exist for higher-order clique sums, potentially extending linear descriptions to larger minor-closed families.
  • The approach suggests that other cut polytopes or connectivity polytopes could be assembled from their summands in the same modular way.
  • An explicit linear-time algorithm that avoids treewidth machinery may be portable to other problems on the same graph class.

Load-bearing premise

The bond polytope of the summed graph is exactly the image of the combined polytopes of G1 and G2 under the given mapping rules, with no extra facets or vertices created by the vertex or edge identification.

What would settle it

A concrete 1-sum or 2-sum graph G whose bond polytope requires strictly more inequalities in any extended formulation than the number produced by applying the paper's combination rules to the descriptions of G1 and G2.

Figures

Figures reproduced from arXiv: 2601.11119 by Hans Raj Tiwary, Petr Kolman.

Figure 1
Figure 1. Figure 1: {1, 2}-sum of graphs G1 and G2 Case 1. Consider F ∈ C(G1 ⊕u G2). As both sides of the bond F are connected, either F ⊆ E1 or F ⊆ E2; in the former case, F ∈ C(G1), in the later case, F ∈ C(G2). On the other hand, if F ∈ C(G1) or F ∈ C(G2), then the removal of F from G1 ⊕u G2 separates it into two connected parts, that is, F is a bond of it. Case 2. Consider first F ∈ Ce¯(G1 ⊕e G2). As both sides of the bon… view at source ↗
Figure 2
Figure 2. Figure 2: The wheel graph Wn Given a bond (S, V \ S) of Wn, its two connected components have a very special form: either one of them is the hub vertex c and the other consists of all the vertices on the rim - such a bond is called the trivial bond, or one of the connected components is a path on at most n − 1 vertices of the rim, denoted PS in the following, and the other component consists of all the other vertice… view at source ↗
read the original abstract

A cut in a graph $G$ is called a {\em bond} if both parts of the cut induce connected subgraphs in $G$, and the {\em bond polytope} is the convex hull of all bonds. Computing the maximum weight bond is an NP-hard problem even for planar graphs. However, the problem is solvable in linear time on $(K_5 \setminus e)$-minor-free graphs, and in more general, on graphs of bounded treewidth, essentially due to clique-sum decomposition into simpler graphs. We show how to obtain the bond polytope of graphs that are $1$- or $2$-sum of graphs $G_1$ and $ G_2$ from the bond polytopes of $G_1,G_2$. Using this we show that the extension complexity of the bond polytope of $(K_5 \setminus e)$-minor-free graphs is linear. Prior to this work, a linear size description of the bond polytope was known only for $3$-connected planar $(K_5 \setminus e)$-minor-free graphs, essentially only for wheel graphs. We also describe an elementary linear time algorithm for the \MaxBond problem on $(K_5\setminus e)$-minor-free graphs. Prior to this work, a linear time algorithm in this setting was known. However, the hidden constant in the big-Oh notation was large because the algorithm relies on the heavy machinery of linear time algorithms for graphs of bounded treewidth, used as a black box.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper shows how to obtain the bond polytope of graphs formed by 1-sums or 2-sums of graphs G1 and G2 directly from the bond polytopes of G1 and G2. This construction is then used to prove that the extension complexity of the bond polytope is linear for all (K5 minus e)-minor-free graphs, and to give an elementary linear-time algorithm for the maximum-weight bond problem on these graphs (improving on prior results that relied on bounded-treewidth machinery).

Significance. If the combination rules are exact, the result extends the known linear-size descriptions of the bond polytope from the special case of 3-connected planar (K5 minus e)-minor-free graphs to the full class via clique-sum decompositions. It simultaneously supplies a practical linear-time MaxBond algorithm whose hidden constant is smaller than that of the treewidth-based approach.

major comments (1)
  1. [§3] §3 (2-sum construction): the argument that the convex hull of the combined bonds equals the polytope obtained by the stated linear combination of the two input polytopes must be checked for the case when the identified edge lies in a bond; it is not immediately clear from the sketch whether new facets arise from the connectivity requirement on both sides of the cut after identification.
minor comments (2)
  1. [Abstract] The statement of the 1-sum rule in the abstract and introduction should explicitly note that the resulting polytope is the convex hull of the union of the lifted bonds rather than a Minkowski sum.
  2. [§2] Notation for the bond indicator vectors after vertex/edge identification should be introduced once and used consistently in the proofs of the combination lemmas.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and recommendation for minor revision. We address the single major comment below.

read point-by-point responses

  1. Referee: [§3] §3 (2-sum construction): the argument that the convex hull of the combined bonds equals the polytope obtained by the stated linear combination of the two input polytopes must be checked for the case when the identified edge lies in a bond; it is not immediately clear from the sketch whether new facets arise from the connectivity requirement on both sides of the cut after identification.

    Authors: We appreciate the referee drawing attention to this boundary case. In the 2-sum construction, a bond in the summed graph that contains the identified edge corresponds to selecting bonds in G1 and G2 that each contain the corresponding edge and whose cut-sets are compatible under the vertex identification. The linear combination of the two input polytopes produces exactly the incidence vectors of such combined bonds, because the connectivity of each side of the cut is preserved by the summands (no new crossing edges are introduced). Nevertheless, the current sketch is terse on this point. We will add an explicit case analysis in the revised Section 3 that enumerates the subcases (shared edge in the bond versus not) and verifies that the resulting polytope description introduces no extraneous facets beyond those already accounted for by the input polytopes. revision: yes

Circularity Check

0 steps flagged

No significant circularity; standard minor theory and new polytope combination rules

full rationale

The derivation introduces explicit combination rules for bond polytopes under 1-sums and 2-sums, then applies them to the known clique-sum decomposition of (K5-e)-minor-free graphs. No equation or claim reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the central construction is presented as a new result whose correctness is independent of the target complexity bound. Minor self-citation of prior polytope work is present but not load-bearing for the new claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters or new entities are introduced; the work uses existing notions of polytopes and graph sums.

axioms (1)
  • standard math Standard definitions of cuts, bonds, and graph minors hold as in prior literature.
    The paper relies on established graph theory concepts without redefining them.

pith-pipeline@v0.9.0 · 5573 in / 1399 out tokens · 59890 ms · 2026-05-16T13:55:41.705171+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    Aprile and S

    M. Aprile and S. Fiorini. Regular matroids have polynomial extension complexity.Math. Oper. Res., 47(1):540–559, 2022

    work page 2022

  2. [2]

    E. Balas. Disjunctive programming: Properties of the convex hull of feasible points.Discret. Appl. Math., 89(1-3):3–44, 1998

    work page 1998

  3. [3]

    Barahona and A

    F. Barahona and A. R. Mahjoub. On the cut polytope.Math. Program., 36(2):157–173, 1986

    work page 1986

  4. [4]

    J. L. Bentley. Programming pearls: algorithm design techniques.Communications of The ACM, 27:865–873, 1984

    work page 1984

  5. [5]

    Carvajal, M

    R. Carvajal, M. Constantino, M. Goycoolea, J. P. Vielma, and A. Weintraub. Imposing connectivity constraints in forest planning models.Oper. Res., 61(4):824–836, 2013

    work page 2013

  6. [6]

    Chaourar

    B. Chaourar. Connected max cut is polynomial for graphs without the excluded minorK 5 \e.J. Comb. Optim., 40(4):869–875, 2020

    work page 2020

  7. [7]

    Chimani, M

    M. Chimani, M. Juhnke-Kubitzke, and A. Nover. On the bond polytope.Advances in Geometry, 23(4):461–480, 2023

    work page 2023

  8. [8]

    Courcelle

    B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs.Information and Compu- tation, 85:12–75, 1990

    work page 1990

  9. [9]

    G. L. Duarte, H. Eto, T. Hanaka, Y. Kobayashi, Y. Kobayashi, D. Lokshtanov, L. L. C. Pedrosa, R. C. S. Schouery, and U. S. Souza. Computing the largest bond and the maximum connected cut of a graph.Algorithmica, 83(5):1421–1458, 2021

    work page 2021

  10. [10]

    G. L. Duarte, D. Lokshtanov, L. L. C. Pedrosa, R. C. S. Schouery, and U. S. Souza. Computing the largest bond of a graph. InProc. of 14th International Symposium on Parameterized and Exact Computation (IPEC), volume 148 of LIPIcs, pages 12:1–12:15, 2019

    work page 2019

  11. [11]

    H. Eto, T. Hanaka, Y. Kobayashi, and Y. Kobayashi. Parameterized algorithms for maximum cut with connectivity constraints. InProc. of 14th International Symposium on Parameterized and Exact Computation (IPEC), volume 148 ofLIPIcs, pages 13:1–13:15, 2019. 14 P. Kolman, H. R. Tiwary

    work page 2019

  12. [12]

    Gandhi, M

    R. Gandhi, M. T. Hajiaghayi, G. Kortsarz, M. Purohit, and K. K. Sarpatwar. On maximum leaf trees and connections to connected maximum cut problems.Inf. Process. Lett., 129:31–34, 2018

    work page 2018

  13. [13]

    Grimm, T

    V. Grimm, T. Kleinert, F. Liers, M. Schmidt, and G. Z¨ ottl. Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches.Optim. Methods Softw., 34(2):406–436, 2019

    work page 2019

  14. [14]

    Hajiaghayi, G

    M. Hajiaghayi, G. Kortsarz, R. MacDavid, M. Purohit, and K. K. Sarpatwar. Approximation algorithms for connected maximum cut and related problems.Theor. Comput. Sci., 814:74–85, 2020

    work page 2020

  15. [15]

    Hopcroft and R

    J. Hopcroft and R. Tarjan. Algorithm 447: efficient algorithms for graph manipulation.Commun. ACM, 16(6):372–378, June 1973

    work page 1973

  16. [16]

    Hopcroft and R

    J. Hopcroft and R. Tarjan. Dividing a graph into triconnected components.SIAM J. Comput., 2(3):135–158, 1973

    work page 1973

  17. [17]

    R. M. Karp. Reducibility among combinatorial problems. InProc. of a Symposium on the Complexity of Computer Computations, pages 85–103, 1972

    work page 1972

  18. [18]

    Kolman, M

    P. Kolman, M. Kouteck´ y, and H. R. Tiwary. Extension Complexity, MSO Logic, and Treewidth.Discrete Mathematics & Theoretical Computer Science, vol. 22 no. 4, Oct. 2020

    work page 2020

  19. [19]

    Langer, F

    A. Langer, F. Reidl, P. Rossmanith, and S. Sikdar. Practical algorithms for MSO model-checking on tree-decomposable graphs.Computer Science Review, 13-14:39–74, 2014

    work page 2014

  20. [20]

    Margot.Composition de polytopes combinatoires: une approche par projection

    F. Margot.Composition de polytopes combinatoires: une approche par projection. PhD thesis, ´Ecole polytechnique f´ ed´ erale de Lausanne, 1994

    work page 1994

  21. [21]

    Oxley.On the interplay between graphs and matroids, page 199–240

    J. Oxley.On the interplay between graphs and matroids, page 199–240. London Mathematical Society Lecture Note Series. Cambridge University Press, 2001

    work page 2001

  22. [22]

    Schieber and S

    B. Schieber and S. Vahidi. Approximating connected maximum cuts via local search. InProc. of 31st Annual European Symposium on Algorithms (ESA), volume 274 ofLIPIcs, pages 93:1–93:17, 2023

    work page 2023

  23. [23]

    P. D. Seymour. Decomposition of regular matroids.Journal of Combinatorial Theory, Series B, 28(3):305–359, 1980

    work page 1980

  24. [24]

    Vicente, V

    S. Vicente, V. Kolmogorov, and C. Rother. Graph cut based image segmentation with connectivity priors. InProc. of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2008

    work page 2008

  25. [25]

    K. Wagner. Bemerkungen zu Hadwigers Vermutung.Mathematische Annalen, 141:433–452, 1960

    work page 1960