# How to perform local search to find maximal induced subgraphs?

I'm looking for efficient ways to perform local search to find maximal induced subgraphs that satisfy certain properties : a tree, a forest or a bipartite subgraph for example.

What I mean by local search is moving from solution to solution by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

• What have you tried? How can you find out whether an induced subgraph (forest/bipartite/...) is maximal? – Pål GD Jan 14 at 19:53
• I shouldn't have said maximal but as large as possible even if it's not optimal. I thought of simulated annealing. – Katrina Jan 14 at 20:01
• What is meant by "local search"? Please explain or define it in the question. – Apass.Jack Jan 14 at 20:01
• @Apass.Jack Is it clearer ? – Katrina Jan 14 at 20:43
• @Apass.Jack Wikipedia has a page on local search. Simulated annealing is a popular method to implement a local search strategy. – Discrete lizard Jan 15 at 20:48

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)$$.