Search.hpp File Reference

Plans regarding searching for (special) biclique partitions. More...

Go to the source code of this file.

Detailed Description

Plans regarding searching for (special) biclique partitions.

The role of maximal bicliques
  • One process for finding a biclique partition is to choose a maximal biclique, remove it, and iterate this process.
  • The basic question is, whether in this way we can always find an optimal biclique partition (w.r.t. minimal number of parts, and assuming the right choices).
  • This statement is equivalent to the assertion that there always exists an optimal biqlique partition containing at least one maximal biclique.
  • Also for graphs I (OK) don't see a direct way of proving this property, so I guess it is wrong.
Finding interesting biclique partitions
  • For creating random biclique partitions, one goal is to use only a minimal number of bicliques (i.e., variables for the corresponding clause-sets).
  • Really minimising it is interesting in its own right (see "Finding specific biclique partitions via SAT" above), and we could investigate whether there are special algorithms.
  • Another approach is heuristical.
    1. This would be of interest for creating random biclique partitions, since we could randomise the algorithm, and then obtain "random" biclique partitions with some special properties (like using only relatively few bicliques).
  • The first question to consider are heuristics for creating as few bicliques as possible.
    1. The greedy approach is to find a first biclique as large as possible, remove it, and iterate.
    2. We should study reductions of the problem of finding biclique partitions to closely related other problems, so that then we can transfer techniques from these fields (see ComputerAlgebra/Graphs/Lisp/BicliquePartitions/plans/Transformations.hpp).

Definition in file Search.hpp.