1
$\begingroup$

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.

$\endgroup$
  • $\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
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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