Raphael Steiner

Louis Esperet, Kevin Hendrey, Aurélie Lagoutte et al.

We initiate the study of nowhere-zero flow reconfiguration. The natural question is whether any two nowhere-zero $k$-flows of a given graph $G$ are connected by a sequence of nowhere-zero $k$-flows of $G$, such that any two consecutive flows in the sequence differ only on a cycle of $G$. We study this problem in the setting of integer flows and group flows, and prove a number of positive and negative results. * The natural reconfiguration variant of Tutte's 5-flow conjecture, stating that any two nowhere-zero 5-flows in any 2-edge-connected graph are connected, is false in the group and integer cases. * All nowhere-zero $\mathbb{Z}_2^8$-flows of every 2-edge-connected graph are connected and for every sufficiently large abelian group $A$, all nowhere-zero $A$-flows of every 2-edge-connected graph are connected. * The group structure affects the answer, contrary to the existence problem for nowhere-zero flows. * We highlight a duality with recoloring in planar graphs and deduce that any two nowhere-zero 7-flows in a planar graph are connected, among other results. * For every 2-edge-connected graph $G$, there is an integer $k$ such that all nowhere-zero $k$-flows of $G$ are connected.

Alexander E. Black, Raphael Steiner

We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and Sanità. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard. In fact, we show this is NP-hard already for fractional knapsack polytopes. By applying an additional polyhedral construction, we show that computing the diameter of a simple polytope is NP-hard, resolving a 2003 open problem by Kaibel and Pfetsch. Finally, on the positive side we show that every polytope has a small, simple extended formulation for which a linear length path may be found between any pair of vertices in polynomial time building upon a result of Kaibel and Kukharenko.

António Girão, Freddie Illingworth, Bojan Mohar et al.

A "dominating $K_t$-model" in a graph $G$ is a sequence $(T_1,\dots,T_t)$ of pairwise vertex-disjoint connected subgraphs of $G$, such that whenever $1\leq i<j\leq t$ every vertex in $T_j$ has a neighbour in $T_i$. Replacing "every vertex in $T_j$" by "some vertex in $T_j$" retrieves the standard definition of $K_t$-model, which is equivalent to a $K_t$-minor in $G$. We prove that every graph with no dominating $K_5$-model is $4$-colourable. This generalises and is significantly stronger than the 4-colour theorem for planar graphs or for graphs with no $K_5$-minor. It also makes progress towards Hajós' conjecture on $K_5$-subdivisions in $5$-chromatic graphs.