Facets of the balanced (acyclic) induced subgraph polytope |
| |
Authors: | Francisco Barahona Ali Ridha Mahjoub |
| |
Institution: | (1) Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada;(2) Present address: Department of Statistics, King Saud University, P.O. Box 2455, 1451 Riyadh, Saudi Arabia |
| |
Abstract: | A signed graph is a graph whose edges are labelled positive or negative. A signed graph is said to be balanced if the set of negative edges form a cut. The balanced induced subgraph polytopeP(G) of a graphG is the convex hull of the incidence vectors of all node sets that induce balanced subgraphs ofG. In this paper we exhibit various (rank) facet defining inequalities. We describe several methods with which new facet defining inequalities ofP(G) can be constructed from known ones. Finding a maximum weighted balanced induced subgraph of a series parallel graph is a polynomial problem. We show that for this class of graphsP(G) may have complicated facet defining inequalities. We derive analogous results for the polytope of acyclic induced subgraphs.Research supported in part by the Natural Sciences and Engineering Research Council of Canada; the second author has also been supported by C.P. Rail. |
| |
Keywords: | Balanced subgraphs acyclic subgraphs facets of polyhedra |
本文献已被 SpringerLink 等数据库收录! |