Graph Bipartization and Via Minimization for Intersection Graphs

The graph bipartization problem, arising from via minimization in VLSI design and related areas, consists in finding a vertex subset Formula: see text of graph Formula: see text such that the induced subgraph Formula: see text is bipartite and Formula: see text is maximized. The problem has been proved to be NP-hard even for planar graphs and cubic graphs. On the other hand, the study of polynomial-time algorithms for typical graph classes is significant in both theoretical and applied aspects. This paper focuses on several intersection graph classes, such as line graphs, circular-arc graphs, and directed path graphs. For the line graphs, we show the NP-hardness results in general and present the polynomial-time algorithms for special cases. For circular-arc graphs and directed path graphs, we propose algorithms that improve on the previously known ones.