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.
 Todo:
 Connections
 Todo:
 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 vertexoriented notions for (multi) graphs.

This corresponds to a representation of the adjacency matrix of the multigraph as a sum of submatrices which are constant 1.

Considering the edgeoriented notion, we get the notion of an "edgebicliquepartition" of a general graph as a partition of the edge set such that each part constitutes a complete bipartite graph.

We take "partition" here in the formal sense, that is, a set of subsets, none empty, union the whole, pairwise disjoint.

As mentioned, we also need "polarised" versions where the parts of the biclique are also specified.

Here we need, given an edgesubset of a general graph, to construct the "induced" general subgraph, whose vertex set is just the vertices used by those edges.

Then we need a check for simplicity of a general graph.

And then we need a bipartiteness test for general graphs (using the Maxima function).

Write predicates to check for bicliquepartitions:

From Maxima we can use bipartition(gr).

For edgebicliques of general graphs:
ebcp_gg_p(B,G) := partitionp(B,G[2]) and
every_s(lambda([b],ebc_gg_p(b,G)),B)$
where G is a general graph,

We have a natural hierarchy of contexts for biclique partitions:

Most special are biclique partitions of directed (multi)graphs.

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.

This conversion corresponds to considering the adjacency matrix of G, and interpreting it as the reduced adjacency matrix of a bipartite graph.

Finally we have biclique partitions of arbitrary (multi)graphs.

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.
 Todo:
 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 clausesets 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:

The question is, what is the right place, here or there?

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

So with combinatorial matrices we have automatically the bipartitions given, while this is not the case for (general) graphs, and this makes the difference.

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

So representing a combinatorial matrix over NN_0 as a "sum" of 1constant matrices with disjoint row and columnsets is, up to a different encoding, the same as a biclique partition of a bipartite multigraph with given bipartition.

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

So we should explore both avenues.
 Todo:
 Directed graphs
 Todo:
 Abbreviations
Definition in file BasicNotions.hpp.