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.

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