OKlibrary  0.2.1.6
general.hpp File Reference

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 clause-sets 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 "maximum-vertices bicliques" and "maximum-edges bicliques".
• The maximum-edges biclique decision problem (for a given lower bound on the number of edges):
1. In [Sperschneider, Bioinformatics, Springer 2008], Theorem 5.42, this is shown to be NP-complete, even if the graph is just bipartite.
2. From this proof a reduction of 3-SAT to this problem can be derived; we should implement this.
3. On the other hand, we should also have algorithms and reductions for solving this problem.
4. If the number of edges is given as a parameter: Is this problem then fixed-parameter tractable?
• The maximum-vertices biclique decision problem:
1. Is this also NP-complete?
2. And with the number of vertices as parameter: Is this problem then fixed-parameter tractable?
• See "Bioinformatics" in ComputerAlgebra/plans/general.hpp for an application.

Definition in file general.hpp.