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

Yotaro Takazawa(takazawa.y.abm.titech.ac.jp)
Shinji Mizuno(mizuno.s.abm.titech.ac.jp)

Abstract: 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 maximum total weight such that a subgraph induced by W is bipartite. WIBSP is also referred as to the graph bipartization problem or the odd cycle transversal problem. In this paper, we show that WIBSP can be reduced to the weighted independent set problem (WISP) where the number of nodes becomes twice and the maximum degree increases by 1. WISP is a well-studied combinatorial optimization problem. Thus, by using the reduction and results about WISP, we can obtain nontrivial approximation and exact algorithms for WIBSP.

Keywords: Weighted induced bipartite subgraph problem, Graph bipartization problem, Odd cycle transversal problem, Independent set problem

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Combinatorial Optimization (Approximation Algorithms )

Citation:

Download: [PDF]

Entry Submitted: 07/17/2018
Entry Accepted: 07/22/2018
Entry Last Modified: 07/17/2018

Modify/Update this entry