Bond Polytope under Vertex- and Edge-sums
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909054664704000 |
|---|---|
| author | Kolman, Petr Tiwary, Hans Raj |
| author_facet | Kolman, Petr Tiwary, Hans Raj |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_11119 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Bond Polytope under Vertex- and Edge-sums Kolman, Petr Tiwary, Hans Raj Combinatorics Discrete Mathematics Optimization and Control 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. |
| title | Bond Polytope under Vertex- and Edge-sums |
| topic | Combinatorics Discrete Mathematics Optimization and Control |
| url | https://arxiv.org/abs/2601.11119 |