Bond Polytope under Vertex- and Edge-sums
For researchers in combinatorial optimization and graph theory, this provides a simpler, more efficient algorithm and a compact polytope description for a class of graphs where the problem was previously solvable but with large constants.
The authors characterize the bond polytope under 1- and 2-sums of graphs, leading to a linear-size extended formulation for (K5 \\ e)-minor-free graphs. They also provide an elementary linear-time algorithm for the maximum weight bond problem on these graphs, improving on previous heavy machinery.
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.