Facets for Node-Capacitated Multicut Polytopes from Path-Block Cycles with Two Common Nodes

A path-block cycle is a graph that consists of several cycles that all intersect in a common subset of nodes. The associated path-block-cycle inequalities are valid, and sometimes facet-defining, inequalities for polytopes in connection with graph partitioning problems and corresponding multicut problems. Special cases of the inequalities were introduced by De Souza & Laurent (1995) and shown to be facet-defining for the equicut polytope. Generalizations of these inequalities were shown by Ferreira et al. (1996) to be valid for node-capacitated graph partitioning polytopes on general graphs. This paper considers the special case of the inequalities, where all cycles intersect in two nodes, and establishes conditions under which the associated inequalities induce facets of node-capacitated multicut polytopes and bisection cut polytopes. These polytopes are associated with simple versions of the node-capacitated graph partitioning and bisection problems, where all node weights are assumed to be 1.

Citation

Published in: Discrete Optimization 25 (2017) 120-140 http://dx.doi.org/10.1016/j.disopt.2017.03.001 Elsevier share link ttps://authors.elsevier.com/a/1VSIv5bZJPeY7y

Article

Download

View Facets for Node-Capacitated Multicut Polytopes from Path-Block Cycles with Two Common Nodes