
We prove that the minimum stable \(s-t\)  cut problem (Is
there an independent set \(S\)  of size at most \(k\)  whose removal
separates \(s\)  and \(t\) ?) is fixed-parameter tractable. This problem
received some attention in the community. Our techniques allow us to
prove various generalizations of this result very easily. First,
instead of requiring that \(S\)  is independent, we can require that it
induces a graph that belongs to a hereditary class \(\mathcal {G}\) ; the problem
remains fpt. Second, in the multicut problem a
list of pairs of terminals are given \((s_1,t_1)\) , \(\dots \) ,
\((s_\ell ,t_\ell )\)  and the solution \(S\)  has to be a set of at most \(k\)  vertices that
induces a graph from \(\mathcal {G}\)  and separates \(s_i\)  from \(t_i\)  for every
\(i\) . We show that this problem is fpt parameterized by \(k\) 
and \(\ell \) , which is a very strong generalization of previous
results [1]}, [2]}. Third, the results
generalize to the multicut-uncut problem, where two sets
\(T_1\) , \(T_2\)  of pairs of terminals are given, and \(S\)  has to
separate every pair of \(T_1\)  and should not separate any
pair of \(T_2\) .

We prove that the exact stable bipartization problem (Is there
an independent set of size exactly \(k\)  whose removal makes the graph bipartite?) is
fixed-parameter tractable (fpt) answering an open question posed in 2001 by Díaz
et al. [3]}. We establish this result by proving that
the stable bipartization problem (Is there an independent set of size
at most \(k\)  whose removal makes the graph bipartite?) is fpt,
answering an open question posed by Fernau [4]}.

We show that the edge-induced vertex
cut (Are there at most \(k\)  edges such that the removal of their
endpoints separates two given terminals \(s\)  and \(t\) ?) is
fpt, answering an open problem posed in 2007 by Samer
[4]}. The motivation behind this
problem is described in [6]}.

