Sampling.hpp File Reference

Plans regarding sampling of biclique partitions in (general) graphs. More...

Go to the source code of this file.

Detailed Description

Plans regarding sampling of biclique partitions in (general) graphs.

Uniformly sampling biclique partitions
  • Given the uniform probability distribution on the set of all biclique partitions of a given general graph, can we efficiently sample it?
  • This appears to be difficult.
  • However as a "benchmark" this is relevant.
Random processes
  • A simple approach is to construct random processes P for constructing random biclique partitions.
  • A simple model P1(p) is, given a probability p, find a random maximal biclique MB, keep edges with probability p, obtain a biclique B, remove B, and repeat the process.
  • The fundamental problem with this edge-oriented approach is that edges cannot be eliminated in isolation, but eliminating one edge means eliminating its two endpoints (with all incident edges).
  • So likely the vertex-oriented approach is better.
  • Given a biclique MB = K_{a,b}, one can construct random subsets of the two sides (each subset equally likely, or each size equally likely, or considering some fixed size etc.), and obtain so B.
  • This yields a process P2, allowing many parameterisations. MB here is constructed by choosing a random order of the vertices and then including every vertex if possible (in this order).
  • Given a parameter p, we can construct a simpler process P3(p) as follows:
    1. Set B := {} and choose a random ordering v_1, ..., v_n of the vertices.
    2. Run trough v_1, ..., v_n, and include v_i into B with probability p if {v_i} union B yields a biclique.
    3. Output B.
  • For the cases we can enumerate all possible biclique partitions, we should run experiments with the different random process in order to estimate which probability distributions they induce:
    1. That is, we repeat the process many times and determine the frequence that a biclique partition is computed.
    2. Once we have the data, we can also consider isomorphism types of biclique partitions are their frequencies of being chosen.
  • Sampling of general graphs is definitive of high interest, since it yields an alternative random formula generator (for SAT problems)!
    1. However we should also consider special graph types for G.
    2. One example is G = K_{n,m} (complete bipartite graphs); see below "The conjecture of [Galesi, Kullmann]".
    3. Another example is G = K_n (complete graphs), which yields 1-regular hitting clause-sets.
    4. We should also consider various forms of random graphs G.
    5. For the latter we should study the distribution of SAT/UNSAT, and whether threshold phenomena occur.
    6. Of course, in all cases the (empirical) hardness of the created SAT problems for SAT solvers is of interest.

Definition in file Sampling.hpp.