Optimization Online


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

Michael M. Sørensen (mim***at***econ.au.dk)

Abstract: 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.

Keywords: Graph bisection; graph partitioning; polyhedral combinatorics

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (Cutting Plane Approaches )

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


Entry Submitted: 07/27/2016
Entry Accepted: 07/28/2016
Entry Last Modified: 08/04/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society