Enumeration.hpp File Reference

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

Go to the source code of this file.

Detailed Description

Plans regarding enumeration of all biclique partitions in (general) graphs.

Enumerating biclique partitions
  • Given a general graph G, enumerate all biclique partitions.
  • As discussed in ComputerAlgebra/Graphs/Lisp/BicliquePartitions/plans/Bicliques.hpp, likely multigraphs are more appropriate, since then we do not need to distinguish between different parallel edges.
  • The problem is the same as finding all clause-sets without pure literals with a given conflict multigraph (namely G).
  • The simplest approach:
    1. Via set_partitions(edge_set) create all possible partitions of the edge-set, and then we compute the subset given by bicliquepartp.
  • Alternatively, we translate the biclique partition problem into a SAT problem (see ComputerAlgebra/Graphs/Lisp/BicliquePartitions/plans/Transformations.hpp) and enumerate all solutions.
    1. However, this is then a harder problem, since we demand certain properties of the biclique partition.
  • Can we write an efficient generator, which creates one biclique partition at a time, with polynomial delay, running through all biclique partitions without repetition?
    1. For example, running through the lexicographical ordering?!
    2. Most natural seems to consider a backtracking approach.
  • Given all biclique partitions, we can then find all isomorphism types:
    1. Two biclique partitions are isomorphic if the associated clause-sets are isomorphic.
    2. The problem of finding all isomorphism types is then the same as determining all isomorphism types of clause-sets without pure literals and with conflict multigraph G.
  • Again the question is whether there is an efficient generator for all isomorphism types?
    1. Definitely we do not need to generate first all biclique partitions.
    2. Instead we use a backtracking approach, where we investigate new branches only if they are not isomorphic to branches already considered.
  • Viewing biclique partitions are solutions of a constraint satisfaction problem:
    1. Given a general G = (V,E).
    2. Find a function b : E -> {1,...,|E|} which yield biclique partitions.
    3. This blows up the search space, but makes the problem more accessible.
    4. Making this translation explicit is discussed below in ComputerAlgebra/Graphs/Lisp/BicliquePartitions/plans/Transformations.hpp.
    5. But we can explore such a point of view more implicitely.

Definition in file Enumeration.hpp.