On the minimum cut separator problem
Authors:
Abstract
Given G = (V,E) an undirected graph and two specified nonadjacent nodes a and b of V, a cut separator is a subset F =δ (C) ⊆ E such that a,b∈V / C and a and b belong to different connected components of the graph induced by V / C. Given a non‐negative cost vector \documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath, amssymb} \pagestyle{empty} \begin{align*}c\in\mathbb{R}^{|E|}_{+}\end{align*} , the cut separator problem is to find a cut separator of minimum cost. This new problem can be seen as a generalization of the vertex separator problem. In this article, we give a polynomial time algorithm for this problem. We also present six equivalent linear programming formulations, and we show their tightness. Using these results we obtain an explicit short polyhedral description of the dominant of the cut separator polytope. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012
Keywords
This publication has 7 references indexed in Scilit:
- Compact formulations as a union of polyhedraMathematical Programming, 2007
- Valid inequalities for mixed integer linear programsMathematical Programming, 2007
- Minimal multicut and maximal integer multiflow: A surveyEuropean Journal of Operational Research, 2005
- The vertex separator problem: a polyhedral investigationMathematical Programming, 2005
- On the dimension of projected polyhedraDiscrete Applied Mathematics, 1998
- An improved approximation algorithm for multiway cut1998
- Applications of a Planar Separator TheoremSIAM Journal on Computing, 1980