6
$\begingroup$

The Maximum Edge Biclique(MEB) problem is to find a biclique with as many edges as possible in a bipartite graph. It was proved to be NP-complete by Peeters in 2003, and then the inapproximability result for MEB was given by this paper in 2011 . But I could hardly find any exact algorithm or parameterized algorithm for MEB problem(maybe there are some).

What is the state of research on exact algorithm or parameterized algorithm for MEB problem? I appreciate if someone can provide guidance on where to look for such research and whether designing such algorithms is valid as a research point.

$\endgroup$

1 Answer 1

8
$\begingroup$

A good starting point could be the paper Exact exponential-time algorithms for finding bicliques which provides an $O(1.31^n)$-time algorithm for Constrained Bipartite Vertex Cover on graphs with $n$ vertices. As discussed in the paper this algorithm can be used to find bicliques with constraints on the sizes of the two parts. This in turn can be used to find bicliques with a maximum number of edges by considering all possibilities for the size constraints.

Concerning parameterized algorithms, it depends on the parameter that you want to consider.

If the parameter is the number $\ell$ of edges in the biclique, then a simple fixed-parameter algorithm can be obtained from the fact that whenever $\ell\le \Delta$ where $\Delta$ is the maximum degree of the input graph $G$, then we have a yes-instance. If $\ell>\Delta$, then one may find a maximum-edge biclique by considering for each vertex $v$ in $G$ the induced subgraph of $G$ containing $v$ and all vertices within distance 2 of $v$. This subgraph has $O(\Delta^2)$ vertices giving a running time of $2^{O(\ell^2)}\cdot n^{O(1)}$ for the nontrivial case. This can probably be improved but I am not aware of algorithms with running time $2^{O(\ell)}\cdot n^{O(1)}$.

If the parameter is the number of vertices in the maximum edge biclique, then one needs to be quite careful with the exact problem definition. For example, if one asks for a biclique on at least $k$ vertices with at least $\ell$ edges, then one should obtain fixed-parameter tractability for $k$ by the above arguments. In contrast, if one asks for a biclique on at most $k$ vertices with at least $\ell$ edges, then the problem is a generalization of Balanced Bipartite Subgraph, also known as $(k,k)$-Biclique, which is W[1]-hard with respect to $k$ as shown by Bingkai Lin in The Parameterized Complexity of $k$-Biclique.

$\endgroup$

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.