Generalized cut and metric polytopes of graphs and simplicial complexes

Michel Deza, Mathieu Dutour Sikirić

Given a graph $G$ one can define the cut polytope CUTP(G) and the metric polytope METP(G) of this graph and those polytopes encode in a nice way the metric on the graph. According…