Subgraph polytopes and independence polytopes of count matroids

DOI10.1016/J.ORL.2015.06.011MaRDI QIDQ1785403zbMATH OpenOpenAlexFDO

Authors Michele Conforti, Volker Kaibel, Matthias Walter, Stefan Weltge

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

extension complexityspanning tree polytopecount matroids

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: Given an undirected graph, the non-empty subgraph polytope is the convex hull of the characteristic vectors of pairs (F, S) where S is a non-empty subset of nodes and F is a subset of the edges with both endnodes in S. We obtain a strong relationship between the non-empty subgraph polytope and the spanning forest polytope. We further show that these polytopes provide polynomial size extended formulations for independence polytopes of count matroids, which generalizes recent results obtained by Iwata et al. referring to sparsity matroids. As a byproduct, we obtain new lower bounds on the extension complexity of the spanning forest polytope in terms of extension complexities of independence polytopes of these matroids.

Recommendations

• Extended formulations for independence polytopes of regular matroids
• Extended formulations for sparsity matroids
• scientific article; zbMATH DE number 1953186
• scientific article; zbMATH DE number 3929064
• Extension complexity of independent set polytopes

Cites work

• A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs
• Connections in combinatorial optimization
• Disjunctive Programming
• Edge-Disjoint Spanning Trees of Finite Graphs
• Forbidden vertices
• Matroids and the greedy algorithm
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(13)

• Polytopes from subgraph statistics
• Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
• About count matroids
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Extended formulations of lower-truncated transversal polymatroids
• Extended formulations for sparsity matroids
• An extended formulation of the convex recoloring problem on a tree
• Extended formulations for independence polytopes of regular matroids
• A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
• Extended formulations for radial cones
• Regular matroids have polynomial extension complexity
• Extended formulations for matroid polytopes through randomized protocols
• Smaller extended formulations for the spanning tree polytope of bounded-genus graphs

This page was built for publication: Subgraph polytopes and independence polytopes of count matroids

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