Fiorini–Huynh–Joret–Pashkovich conjecture on spanning tree polytopes in minor-closed classes
Fiorini–Huynh–Joret–Pashkovich conjecture on spanning tree polytopes in minor-closed classes
Let be a proper minor-closed graph class, and let be a connected -vertex graph in . The spanning tree polytope of is the convex hull of the incidence vectors of its spanning trees. Fiorini–Huynh–Joret–Pashkovich conjecture. The spanning tree polytope of every connected -vertex graph in has extension complexity in . This would improve the paper's 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.