How to perform local search to find maximal induced subgraphs?
All three problems are easy to formalize as local search problems.  Let $f$ be a function that measures the quality of a solution $s$, in your cases

$f(s)$ is


the number of edges (or vertices) in the tree $s$
the number of edges (or vertices) in the forest $s$
the number of vertices (?) in the bipartite graph $s$


and your goal is to maximize $f$.

Lastly, you need to define a neighborhood function $N(s)$ that gives all possible ways of modifying a current solution $s$ to a new solution $s'$.

To illustrate $N(s)$ in the simplest case, the tree:
$$ N(s) = \{ X \subseteq V(G) \mid \text{is_tree}(V(s) \setminus X \cup (X \setminus V(s)) \}, $$

and my apologies for the terse syntax.  It is simply all the ways you can delete a certain set of vertices from the solution $s$, simultaneously adding a different set of vertices, at the same time keeping the property that the new $s'$ is a tree.

Now, the search algorithm simply starts with a random solution (tree) $s$ (which might be the empty tree), and just randomly walk $N(\cdot)$.