On a reduction of the weighted induced bipartite subgraph problem to the weighted independent set problem

Yotaro Takazawa, Shinji Mizuno

We study the weighted induced bipartite subgraph problem (WIBSP). The goal of WIBSP is, given a graph and nonnegative weights for the nodes, to find a set W of nodes with the maxim…