Approximating clique and biclique problems
Abstract
We present here 2-approximation algorithms for several
node deletion and edge deletion biclique problems and for an
edge deletion clique problem.
The biclique problem is to find a node induced subgraph which is
bipartite and complete. The objective is to minimize the total weight
of nodes or edges deleted so that the remaining subgraph is bipartite
complete. Several variants of the biclique problem are studied here
where the problem is defined on bipartite graph or on general graphs
with or without the requirement that each side of the bipartition forms
an independent set.
The maximum clique problem is formulated as maximizing the number (or
weight) of edges in the complete subgraph. A 2-approximation
algorithm is given for the minimum edge deletion version of this problem.
The approximation algorithms given here are derived as a special
case of an approximation technique devised for a class of
formulations introduced by Hochbaum [Hoc96]. All approximation
algorithms described (and the polynomial algorithms for two versions of
the node biclique problem) involve calls to a minimum cut algorithm.
One conclusion of our analysis of the NP-hard problems here is that all these
problems are MAX SNP-hard and at least as difficult to
approximate as the vertex cover problem. Another conclusion is that
the problem of finding minimum node cut-set the removal of which leaves two cliques in
the graph is NP-hard and 2-approximable.
Download Information
Click on the following title to view and download the paper in PostScript format.
- Approximating clique and biclique
problems (22 pages, 294 KB)
- Dorit S. Hochbaum. To appear in Journal of Algorithms.
dorit@hochbaum.ieor.berkeley.edu
7/28/98