Optimization Online


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

Yotaro Takazawa(takazawa.y.ab***at***m.titech.ac.jp)
Shinji Mizuno(mizuno.s.ab***at***m.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 )


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society