سؤال

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

Given $\delta$, I'd like to identify bicliques $(U',V')$ such that $|V'| \ge \delta$. Since the number of all bicliques in a bipartite graph w.r.t its size can be exponential, I'm looking for an approximate algorithm (desirably with guarantees), that can find bicliques such that $|V'| \ge \delta$. For example, find $k$ bicliques where $|V'| \geq \delta$, in time polynomial w.r.t. $k$ and $G$. Can anyone suggest such an algorithm?

One naive solution is to enumerate bicliques using an enumeration-based algorithm and keep the bicliques that satisfy the last condition until the selection of "k" bicliques.

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top