\(\mathcal {G}\) -bipartization is fpt if \(\mathcal {G}\)  is hereditary
and decidable.

Using the algorithm of [1]}, we first try to find a set \(S_0\)  of size at most
\(k\)  such that \(G\setminus S_0\)  is bipartite. If no such set exists,
then clearly there is no set \(S\)  satisfying the requirements.
Otherwise, we branch in \(3^{|S_0|}\)  directions: each vertex of \(S_0\) 
is removed or colored black or colored white.
For a particular branch, let \(R=\lbrace v_1, \dots , v_r\rbrace \)  be the vertices of
\(S_0\)  to be removed and let \(B_0\)  (resp., \(W_0\) ) be the vertices
of \(S_0\)  having color black (resp., white) in a 2-coloring of
the resulting bipartite graph. Let us call a set \(S\)  such that
\(S \cap S_0=R\) , and \(G \setminus S\)  is bipartite and having a 2-coloring where \(B_0\)  and \(W_0\)  are colored black and white, respectively,
a set compatible with \((R,B_0,W_0)\) . Clearly, \((G,k)\)  is a `YES'
instance of the \(\mathcal {G}\) -bipartization problem if and only if for at
least one branch corresponding to partition \((R,B_0,W_0)\)  of \(S_0\) , there is
a set compatible with \((R,B_0,W_0)\)  having size at most \(k\)  and such
that \(G[S] \in \mathcal {G}\) . Clearly, we need to check only those
branches where \(G[B_0]\)  and \(G[W_0]\)  are both independent sets.
