Plans regarding bicliques of (general) graphs.
More...
Go to the source code of this file.
Detailed Description
Plans regarding bicliques of (general) graphs.
 Todo:
 Directed graphs

Above we only considered undirected graphs, however it seems that perhaps directed graphs are somewhat more fundamental here (at least computationally).

The point is that there are no problems with the sides of the biclique (note that a biclique now requires all edges to go from one side to the other); this is especially important for clausesets where literals always have a polarity.

For combinatorial matrices we consider the adjacency matrices of directed graphs, which are nonnegative (but not symmetric).
 Todo:
 Maximum bicliques

There are two ways of measuring the size of a biclique: the number of edges and the number of vertices.

So let's speak of "maximumvertices bicliques" and "maximumedges
bicliques".

The maximumedges biclique decision problem (for a given lower bound on the number of edges):

In [Sperschneider, Bioinformatics, Springer 2008], Theorem 5.42, this is shown to be NPcomplete, even if the graph is just bipartite.

From this proof a reduction of 3SAT to this problem can be derived; we should implement this.

On the other hand, we should also have algorithms and reductions for solving this problem.

If the number of edges is given as a parameter: Is this problem then fixedparameter tractable?

The maximumvertices biclique decision problem:

Is this also NPcomplete?

And with the number of vertices as parameter: Is this problem then fixedparameter tractable?

See "Bioinformatics" in ComputerAlgebra/plans/general.hpp for an application.
Definition in file general.hpp.