Department of Economics and Business Economics

Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review



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 and 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 these 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.
Original languageEnglish
JournalDiscrete Optimization
Pages (from-to)120-140
Number of pages21
Publication statusPublished - 27 Jul 2017

    Research areas

  • Graph bisection, Graph partitioning, Polyhedral combinatorics

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 111162262