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.

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


Your Answer

