Thus we have established an fpt-time reduction from an instance of
the \(\mathcal {G}\) -mincut problem to another instance of this problem where the treewidth
is bounded by a function of parameter \(k\) . Now, let \(G_1=(V(G^*),E(G^*),ST)\)  be a labeled
graph where \(ST=\lbrace s,t\rbrace \) . We present an algorithm for constructing
a monadic second-order (mso) formula
\(\varphi \)  whose atomic predicates (besides equality) are \(E(x_1,x_2)\)  (showing that
\(x_1\)  and \(x_2\)  are adjacent in \(G^*\) ) and predicates of the form \(X(v)\)  (showing
that \(v\)  is contained in \(X \subseteq V\) ), whose size is bounded by a function
of \(k\) , and \(G_1 \models \varphi \)  if and only if \((G^*,s,t,k)\)  is a `YES' instance
of the \(\mathcal {G}\) -mincut problem. According to a restricted version of
the well-known Courcelle's Theorem (see the survey article of Grohe [1]},
Remarks 3.19Although the branchwidth
of \(G_1\)  appears in the parameter, it can be replaced by the treewidth of \(G_1\) 
since the former is bounded by a function of \(k\)  if and only
if the latter is [2]}. and 3.20),
it will follow that the \(\mathcal {G}\) -mincut problem is fpt.
The part of \(\varphi \)  describing the separation of \(s\)  and \(t\)  is based on the ideas from [3]}.
