Fiorini–Huynh–Joret–Pashkovich conjecture on spanning tree polytopes in minor-closed classes

Let G\mathcal{G} be a proper minor-closed graph class, and let GG be a connected nn-vertex graph in G\mathcal{G}. The spanning tree polytope of GG is the convex hull of the incidence vectors of its spanning trees. Fiorini–Huynh–Joret–Pashkovich conjecture. The spanning tree polytope of every connected nn-vertex graph in G\mathcal{G} has extension complexity in O(n)O(n). This would improve the paper's O(n3/2)O(n^{3/2}) bound for every proper minor-closed graph class and would establish linear-size extended formulations throughout these classes.

Sources & referencesView supporting material

Primary source

Manuel Aprile, Samuel Fiorini, Tony Huynh, Gwenaël Joret and David R. Wood, “Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond”, arXiv:2106.11945 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.