ARC Seminar/DOS: Samuel Fiorini - Université libre de Brussels (Brussels, Belgium).

Title: Cut-dominant and forbidden minors


The cut-dominant of a connected graph G is the polyhedron that corresponds to the problem of computing global min-cuts in G. Despite the fact that computing a global min-cut can be done in polynomial time, the geometry of the cut-dominant is far from being understood. We study graphs for which all facets of the corresponding cut-dominant have right-hand side at most a fixed integer k. These graphs form a minor-closed collection. We give a complete list of forbidden minors for k <= 2. This is then applied to the TSP to give a shorter proof of a classic result of Fonlupt and Naddef (Math. Prog., 1992)  that characterizes TSP-perfect graphs. This work in progress is joint with Kanstantsin Pashkovich (Brussels) and Michele Conforti (Padova).

Event Details


  • Wednesday, March 26, 2014
    4:00 pm - 5:00 pm
Location: Groseclose 402

For More Information Contact