Smaller extended formulations for the spanning tree polytope of bounded-genus graphs

DOI10.1007/S00454-016-9852-9MaRDI QIDQ527446zbMATH OpenOpenAlexFDO

Authors Samuel Fiorini, Tony Huynh, Gwenaël Joret, Kanstantsin Pashkovich

Publication date 11 May 2017

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.07976

zbMATH Keywords

extended formulationgenusspanning tree polytope

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Programming involving graphs or networks (90C35)

Abstract: We give an $O(g^{1/2}{n}^{3/2}+g^{3/2}{n}^{1/2})$-size extended formulation for the spanning tree polytope of an $n$-vertex graph embedded on a surface of genus $g$, improving on the known $O(n^2+gn)$-size extended formulations following from Wong and Martin.

Recommendations

• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Fooling sets and the spanning tree polytope
• Extended formulations for sparsity matroids
• On the spanning tree polyhedron
• Spanning trees in locally planar triangulations

Cites work

• A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs
• Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
• Extension complexity, MSO logic, and treewidth
• scientific article; zbMATH DE number 4068901 (Why is no real title available?)
• On the convex hull of the union of certain polyhedra
• Planarization of graphs embedded on surfaces
• Subgraph polytopes and independence polytopes of count matroids
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(10)

• Fooling sets and the spanning tree polytope
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• The facets of the spanning trees polytope
• On the combinatorial lower bound for the extension complexity of the spanning tree polytope
• Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
• Extended formulations for matroid polytopes through randomized protocols
• A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
• Linear-size formulations for connected planar graph partitioning and political districting
• A polyhedral perspective on tropical convolutions
• Exact approaches for the connected vertex cover problem

This page was built for publication: Smaller extended formulations for the spanning tree polytope of bounded-genus graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q527446)