Polynomial Algorithms for Special Cases of the Balanced Complete Bipartite Subgraph Problem

Abstract

Particular balanced bipartite subgraph problems have applications in fields such as VLSI design and flexible manufacturing. An example of such problems is the following: given a graph $G$ and a positive integer $m$, does $G$ contain a balanced complete bipartite subgraph with at least $2m$ vertices? This problem is NP-complete for several classes of graphs, including bipartite graphs. However, the problem can be solved in polynomial time for particular graph classes. We aim to contribute to the characterization of “easy” classes of instances of the problem, and to individuate graph-theoretic properties that can be useful to develop solution algorithms for the general case. A simple polynomial algorithm can be devised for bipartite graphs with no induced $P_5$ on the basis of a result of Bacsó and Tuza.
We generalize the result to particular subclasses of

1. graphs with no odd cycles of given size,
2. paw-free graphs,
3. diamond-free graphs.