Compositions in the bipartite subgraph polytope (Q1199475)

Given a graph \(G=(V,E)\) with edge weights \(c(e)>0\) for all \(e\in E\), the max-cut problem (the problem of finding a cut with maximal weight) is equivalent to the following linear problem \(\text{Max}\{cx;x\in P_ B(G)\}\), where \(P_ B(G)\) is the bipartite subgraph polytope of \(G\), defined as the convex hull of the incidence vectors of all edge sets of bipartite subgraphs of \(G\). (For \(F\subseteq E\) the incidence vector \(x^ F\in\mathbb{R}^{| E|}\) is defined by \(x^ F(e)=1\) if \(e\in F\) and \(x^ F(e)=0\) if \(e\notin F.)\) The max-cut problem and the related bipartite subgraph polytope are studied in graphs which are decomposable by clique-articulation having at most three vertices. If \(G\) decomposes into \(G_ 1,\dots,G_ n\) it is shown that there exists a polynomial time algorithm to solve the max-cut problem in \(G\) provided that such an algorithm is known for appropriate graphs defined from \(G_ 1,\dots,G_ n\). If \(G\) decomposes into \(G_ 1\) and \(G_ 2\), a linear system of inequalities is derived which defines the bipartite subgraph polytope of \(G\) from two linear systems related to \(G_ 1\) and \(G_ 2\). Using this result, it is shown that if \(G_ 1\) and \(G_ 2\) are weakly bipartite graphs then \(G\) is weakly bipartite. Moreover, it is proved that every graph noncontractible to \(K_ 5\) is weakly bipartite. Further classes of weakly bipartite graphs are discussed.