Subgraph polytopes and independence polytopes of count matroids

DOI10.1016/J.ORL.2015.06.011zbMATH Open1408.90250arXiv1502.02817OpenAlexW2963528914MaRDI QIDQ1785403FDOQ1785403

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

Publication date: 28 September 2018

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

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.

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

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

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)

Cites Work

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

Cited In (14)

• 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”
• On Vertices and Facets of Combinatorial 2-Level Polytopes
• 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
• Polytopes from subgraph statistics

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)