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
    Commented Jan 14, 2019 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
    Commented Jan 14, 2019 at 20:01
  • $\begingroup$ What is meant by "local search"? Please explain or define it in the question. $\endgroup$
    – John L.
    Commented Jan 14, 2019 at 20:01
  • $\begingroup$ @Apass.Jack Is it clearer ? $\endgroup$
    – Katrina
    Commented Jan 14, 2019 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
    Commented Jan 15, 2019 at 20:48

1 Answer 1


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

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.