A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
- 1 June 1982
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 34 (3) , 519-524
- https://doi.org/10.4153/cjm-1982-036-8
Abstract
Let G be a symmetric connected graph without loops. Denote by b(G) the maximum number of edges in a bipartite subgraph of G. Determination of b(G) is polynomial for planar graphs ([6], [8]); in general it is an NP-complete problem ([5]). Edwards in [1], [2] found some estimates of b(G) which give, in particular, for a connected graph G of n vertices and m edges, where and ﹛x﹜ denotes the smallest integer ≧ x.We give an 0(V3) algorithm which for a given graph constructs a bipartite subgraph B with at least f(m, n) edges, yielding a short proof of Edwards’ result.Further, we consider similar methods for obtaining some estimates for a particular case of the satisfiability problem. Let Φ be a Boolean formula of variables x1, …, xn.Keywords
This publication has 1 reference indexed in Scilit:
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969