1
$\begingroup$

Let $G=(U \cup V, E)$ denotes a bipartite graph. A biclique $C = (U, V)$ is a subgraph of $G$ induced by a pair of two disjoint subsets $U' \subseteq U$, $V' \subseteq V$, such that $\forall u \in U', v \in V': (u, v) \in E$.

I'd like to identify the minimum number of bicliques such that the nodes on one side of the bipartite graph $G$ are covered, i.e. in an optimum solution $S$, consisting bicliques induced from $G$, (1) $\forall u \in U,$ there exists at least one biclique in $S$ containing $u$, and (2) $|S|$ is minimized.

More specifically, (1) I'm investigating if the problem with these constraints already studied? (2) If the problem is in polynomial time (PTIME), NP-hard, etc. (3) If there exists an approximate algorithm to solve it in PTIME?

Can anyone suggest anything on these questions? Is that possible to reduce it from vertex-cover?

I'm aware of biclique edge cover/partition problem that aims to find the minimum number of bicliques that cover all the edges in $G$, which is not exactly what I'm looking for.

Also, it's fine if bicliques are overlapped.

One application. In a bipartite graph consisting products and their components on each side. One may be interested in finding the minimum number of groups of components such that components in a group have been used in the same set of products and altogether cover the whole set of products. Note that the solution does not need to cover all components but all the products.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.