Facets of the balanced (acyclic) induced subgraph polytope

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 polytope P(G) of a graph G is the convex hull of the incidence vectors of all node sets that induce balanced subgraphs of G. This paper exhibits various (rank) facet defining inequalities. It describes several methods with which new facet defining inequalities of P(G) can be constructed from known ones. Finding a maximum weighted balanced induced subgraph of a series parallel graph is a polynomial problem. The paper shows that for this class of graphs P(G) may have complicated facet defining inequalities. It derives analogous results for the polytope of acyclic induced subgraphs.