BasicNotions.hpp File Reference

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

Go to the source code of this file.

Detailed Description

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

The notion of a biclique partition
  • For each of the above notions of bicliques, we obtain a notion of biclique partition.
  • Most interesting seems the vertex-oriented notions for (multi-) graphs.
  • This corresponds to a representation of the adjacency matrix of the multigraph as a sum of sub-matrices which are constant 1.
  • Considering the edge-oriented notion, we get the notion of an "edge-biclique-partition" of a general graph as a partition of the edge set such that each part constitutes a complete bipartite graph.
    1. We take "partition" here in the formal sense, that is, a set of subsets, none empty, union the whole, pairwise disjoint.
    2. As mentioned, we also need "polarised" versions where the parts of the biclique are also specified.
    3. Here we need, given an edge-subset of a general graph, to construct the "induced" general sub-graph, whose vertex set is just the vertices used by those edges.
    4. Then we need a check for simplicity of a general graph.
    5. And then we need a bipartiteness test for general graphs (using the Maxima function).
  • Write predicates to check for biclique-partitions:
    1. From Maxima we can use bipartition(gr).
    2. For edge-bicliques of general graphs:
      ebcp_gg_p(B,G) := partitionp(B,G[2]) and
      where G is a general graph,
  • We have a natural hierarchy of contexts for biclique partitions:
    1. Most special are biclique partitions of directed (multi-)graphs.
    2. Next come biclique partitions of bipartite (multi-)graphs with given bipartition. Directed (multi-)graphs G are covered here by the conversion which uses the bipartition (V(G), V(G)), where we have an edge from "left" to "right" iff the corresponding directed edge in G exists.
    3. This conversion corresponds to considering the adjacency matrix of G, and interpreting it as the reduced adjacency matrix of a bipartite graph.
    4. Finally we have biclique partitions of arbitrary (multi-)graphs.
    5. Note that representing graphs G by directed graphs G' (via creating from each edge two arcs, in both directions) does not embed the biclique partition problem for graphs in that for directed graphs, since in G' we have to find (different) bicliques for both arcs, while in G, so to speak, one chooses an orientation.
Combinatorial matrices
  • Likely the more algebraic aspects of graph theory are handled better by combinatorial matrices; see ComputerAlgebra/CombinatorialMatrices/Lisp/plans/general.hpp.
  • Also for translating biclique partition into clause-sets we do most work at the level of combinatorial matrices.
  • In ComputerAlgebra/CombinatorialMatrices/Lisp/plans/general.hpp we find some plans on doing biclique partitioning for combinatorial matrices:
    1. The question is, what is the right place, here or there?
    2. Especially with multidigraphs the difference is only that for combinatorial matrices we have two arguments (the 2 indices), while for multigraphs we have one (the edge).
    3. So with combinatorial matrices we have automatically the bipartitions given, while this is not the case for (general) graphs, and this makes the difference.
    4. More pronouncedly, as discussed above a biclique partitioning of a graph needs to choose an orientation (corresponding to choosing only one of the two 1's representing the edge in the adjacency matrix).
    5. So representing a combinatorial matrix over NN_0 as a "sum" of 1-constant matrices with disjoint row- and column-sets is, up to a different encoding, the same as a biclique partition of a bipartite multigraph with given bipartition.
    6. Algorithmically, graphs are "sparse representations", while combinatorial matrices are "dense" (i.e., with them it is natural to query "quickly" whether two vertices are adjacent).
    7. So we should explore both avenues.
Directed graphs

Definition in file BasicNotions.hpp.