On the (near) optimality of extended formulations for multi-way cut in social networks

Abstract

Given an edge-weighted graph and a subset of the vertices called terminals, the multiway cut problem aims to find a minimum weight set of edges that separates each terminal from all the others. This problem is known to be NP-hard even for k= 3. Computational experiments on social networks obtained from the Indian e-commerce company Flipkart show that an integer programming formulation (referred to as EF2) of the problem introduced by Chopra and Owen (1996) provides a very strong LP-relaxation that allows us to solve large problems in a reasonable amount of time. We show that the cardinality EF2 (where all edge weights are 1) on a wheel graph has a primal integer solution and a dual integer solution of the same value. We consider a hub-spoke network of wheel graphs constructed by adding edges connecting the hub vertices of a collection of wheel graphs. We assume that every wheel has a terminal hub or a terminal vertex with three non-terminal neighbors, and show that if the graph connecting the hub vertices is planar, the cardinality EF2 on the hub-spoke network of the wheel graphs has a primal integer solution and a dual integer solution of the same value. Given the prevalence of such structures in our social networks, our results provide some theoretical justification for the strong empirical performance of the EF2 formulation.