Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
Francisco Barahona, Ali Ridha Mahjoub · SIAM Journal on Discrete Mathematics · 1994
Let $P( G )$ be the balanced induced subgraph polytope of G. If G has a two-node cutset, then G decomposes into $G_1 $ and $G_2$. It is shown that $P( G )$ can be obtained as a projection of a polytope defined by a system of inequalities that decomposes into two pieces associated with $G_1 $ and $G_2$. The problem max $cx,x \in P( G )$ is decomposed in the same way. This is applied to series-parallel graphs to show that, in this case, $P( G )$ is a projection of a polytope defined by a system with $O( n )$ inequalities and $O( n )$ variables, where n is the number of nodes in G. Also for this class of graphs, an algorithm is given that finds a maximum weighted balanced induced subgraph in $O( n\log n )$ time. This approach is also used to obtain composition of facets of $P( G )$. Analogous results are presented for acyclic induced subgraphs.