Planar graph bipartization in linear time (Q2482113): Difference between revisions

This paper studies a parameterized version of the fundamental graph bipartization problem: given a graph \(G\), decide whether \(G\) can be made bipartite by deleting a set \(S\) of its vertices having cardinality at most \(k\), where \(k\) is a fixed natural number. This can be done if the graph has an odd cycle vertex transversal of size at most \(k\), i.e. a set of vertices \(S\) with \(|S|\leq k\) that hits all the odd cycles in \(G\). In particular, the authors focus on the bipartization problem in planar graphs. In this case, one may look at the properties of any plane embedding of the given graph \(G\). Then, the key observation in the paper is that a set \(W\) of vertices is an odd cycle transversal of \(G\) precisely if every face of \(G-W\) contains an even number of odd faces of \(G\). Starting from this observation, it is shown that if the graph has the required property than it has bounded treewidth, too. Moreover, it is observed that the bipartization problem for a fixed \(k\) can be expressed as a monadic second order logic formula, which entails that this problem is feasible in linear time on bounded treewidth instances. Nevertheless, for completeness and in order to give a more efficient technique, an explicit algorithm that computes a minimum odd cycle transversal for graphs having bounded treewidth is also described in the paper. In summary, we get a linear time algorithm to compute a bipartization of a planar graph, if a fixed bound \(k\) is given. That is, this paper shows that the bipartization problem is fixed-parameter tractable for planar graphs. I found this paper very interesting. However, possible readers interested in practical applications should consider that linearity here (as in the computation of tree-decompositions used in the proposed technique) hide very big constants that in many cases make such algorithms impractical.