2
$\begingroup$

The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs).

It has been shown that "Biclique Vertex-Cover" is not fixed-parameter tractable unless P = NP in Covering Graphs with Few Complete Bipartite Subgraphs.

Most of the work in the literature proved the hardness of the problem in general/special cases. However, I need an exact algorithm for solving this problem on bipartite graphs. An approximate algorithm with a guarantee is also good (I'm aware of "Clustering and the Biclique Partition Problem", but it provided an approx solution for "Biclique Vertex Partition" not vertex-cover i.e. the provided solution is for disjoint bicliques not possibly overlapped ones).

Is anyone aware of an exact algorithm for "biclique vertex-cover" problem? Potentially, with time complexity analysis?

A naive algorithm, perhaps, would be starting from the whole bipartite graph to check for a biclique that covers all vertices (covering with one biclique). If not successful, we check subsets by removing one vertex and investigate if there exist two bicliques in this set that cover all vertices (trying to cover with two bicliques), and so on (trying to cover with more bicliques until reaching "k").

$\endgroup$
1
  • $\begingroup$ In terms of selected tags, I think "bipartite-graphs", "bicliques", and "vertex-cover" is a better fit. However, I didn't have enough reputation to add those :). $\endgroup$
    – mhn_namak
    Mar 25, 2018 at 21:28

1 Answer 1

2
$\begingroup$

If you have an exact algorithm for the partitioning problem (perhaps one is mentioned in the paper describing the approximate algorithm?), you immediately have an exact algorithm for the covering problem.

First, observe that a partition is a valid cover. Now suppose the partitioning algorithm reports an optimal partition with $k$ bicliques, and suppose to the contrary that there exists a cover $C$ with fewer than $k$ bicliques. But any cover can be turned into a partition easily: Whenever two bicliques in the cover contain the same vertex, delete the vertex from one of them. (This works because bicliques are hereditary: every induced subgraph of a biclique is also a biclique.most of the time, deleting a vertex from a biclique leaves another biclique; the only time where this would not be the case is when deleting the last vertex from one side of a biclique with 3 or more vertices, which would disconnect the graph. But the need to do so could only arise if some $(\{u\},V)$ and $(\{u\},W)$ are both in the cover, and in that case these two bicliques could be replaced with $(\{u\},V\cup W)$, contradicting optimality, so this cannot happen.) This will result in a valid cover with at most as many bicliques as there were originally (it may cause a biclique to have zero vertices: In that case, the original cover was not minimal). Repeat this vertex deletion step until all bicliques are pairwise vertex disjoint. If we apply this to the cover $C$, then because we started with strictly fewer than $k$ bicliques and never increased the number of them that we have, we now have a partition with strictly fewer than $k$ bicliques, contradicting the known optimal solution from the partition solver. Thus the optimal partition must have also been an optimal cover.

$\endgroup$
8
  • $\begingroup$ Thanks for the answer. This is very helpful. Please let me keep the question open to see if anybody can suggest an exact algorithm for either biclique partitioning or cover problem since there is no exact algorithm provided in the mentioned paper. $\endgroup$
    – mhn_namak
    Mar 26, 2018 at 19:37
  • $\begingroup$ Another question is that if we have an exact algorithm for cover, can we say, we use the same algorithm also for partitioning and still get an exact answer? Is this a two-way road? Thanks. $\endgroup$
    – mhn_namak
    Mar 26, 2018 at 19:44
  • $\begingroup$ By all means keep the question open :) Yes, it's a two-way road: there cannot be a partition with fewer bicliques than exist in your optimal cover, since that partition is itself a cover, and no cover can be smaller than an optimal cover. To extract an optimal partition from an optimal cover, just apply the vertex deletion algorithm I described. $\endgroup$ Mar 27, 2018 at 5:08
  • $\begingroup$ BTW, in the same way, covering with cliques (not bicliques) is equivalent to partitioning into cliques, which is equivalent to solving Vertex Colouring in the complement graph (where we make every edge a non-edge, and vice versa). This might help your search for an optimal biclique partitioning algorithm. $\endgroup$ Mar 27, 2018 at 5:11
  • $\begingroup$ @OliverKullmann: The question asks about bipartite vertex cover, and this problem variant permits edges of the original graph to be missed. Indeed on p. 2046 of the OP's first linked paper: "We observe that the Biclique Vertex-Cover and Biclique Vertex-Partition problem are equivalent, since we can always make the bicliques of a biclique vertex-cover disjoint without increasing the size of the cover". $\endgroup$ Mar 11 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.