Keywords

1 Introduction

In the maximum edge biclique (MEB) problem, a bipartite graph \(G=(A,B,E)\) and a positive integer k are given, the question is to decide whether there exist two subsets \(R\subseteq A\) and \(S\subseteq B\) such that, \(|R|*|S|\ge k\) and (R, S) induces a complete bipartite subgraph (biclique) in G. MEB was firstly introduced in [6] and shown \(\mathcal {NP}\)-complete for bipartite graphs in [27]. MEB has many applications in molecular biology, web community discovery, manufacturing optimization, text mining, and conjunctive clustering, see e.g. [1, 11, 26]. Polynomial time algorithms for MEB in convex bipartite graphs and chordal bipartite graphs were developed in [2, 7, 8, 10, 26]. An algorithm of MEB for random graphs was developed in [11]. The (in)approximability of MEB was also investigated in [3, 9, 12].

In a tree convex bipartite graph \(G=(A,B,E)\), there is an associated tree \(T=(A,F)\) such that, for each vertex b in B, its neighborhood \(N_G(b)\) induces a subtree on T. When the associated tree T is a star (a number of edges with a common end) or a triad (three paths with a common end), the tree convex bipartite graph is called star convex or triad convex, respectively. Tree convex bipartite graphs were introduced in [14] as a generalization of convex bipartite graphs. In a convex bipartite graph, the associated tree is a path [13].

Many graph problems are still \(\mathcal {NP}\)-complete for bipartite graphs, but tractable for convex bipartite graphs, such as the minimum feedback vertex set (FVS), the minimum dominating set, treewidth, hamiltonicity, etc. For tree convex bipartite graphs, it turns out that the computational complexity of these problems depends on the associated trees. For example, star convex bipartite graphs were introduced in [14], triad convex bipartite graphs were introduced in [16], and it was shown that FVS is still \(\mathcal {NP}\)-complete for star convex bipartite graphs [14, 31], but tractable for triad convex bipartite graphs [16]. Similar results for the minimum dominating set and its variants such as independent dominating set or connected dominating sets, as well as for the treewidth and hamiltonicity, were obtained in [5, 20, 22, 24, 28,29,30]. (In)approximability of the minimum dominating set for star convex bipartite graphs was also obtained in [28].

Besides the above mentioned graph problems, when taken tree convex bipartite graphs as hypertrees or tree convex set systems, similar results for the minimum set cover, the minimum hitting set and the maximum set packing were obtained in [23]. The union-closed sets conjecture was shown to hold for tree convex sets [21].

In this paper, we show that the computational complexity of the maximum edge biclique (MEB) problem in tree convex bipartite graphs depends on the associated trees. That is, MEB is \(\mathcal {NP}\)-complete for star convex bipartite graphs, but polynomial time solvable for tree convex bipartite graphs whose associated trees have a constant number of leaves. In particular, MEB is polynomial time solvable for triad convex bipartite graphs. Moreover, we show that the same algorithm strategy may not work for circular convex bipartite graphs, and triad convex bipartite graphs are incomparable with respect to chordal bipartite graphs.

This paper is structured as follows. After introducing necessary definitions and facts in Sect. 2, the \(\mathcal {NP}\)-completeness of MEB for star convex bipartite graph classes is shown in Sect. 3, the tractability of MEB for tree convex bipartite graphs whose associated trees have a constant number of leaves and for triad convex bipartite graphs is shown in Sect. 4, the comparison between triad convex bipartite graphs and chordal bipartite graphs is shown in Sect. 5 and finally are concluding remarks in Sect. 6.

2 Preliminaries

A graph \(G=(V,E)\) has a vertex set V and an edge set E. We use V(G) to denote the vertex set of G, and E(G) the edge set of G. Each edge \(e=(u,v)\) has its two ends u and v in V, and these two ends u and v are adjacent. The neighborhood of a vertex x, denoted by \(N_G(x)\), is the set of all adjacent vertices to x. For a graph \(G=(V,E)\) and a subset \(U\subseteq V\), we use G[U] to denote the induced subgraph \((U,\{(u,v)\in E| u\in U, v\in U\})\). In a complete graph, every two vertices are adjacent. A clique in a graph is an induced complete subgraph.

A bipartite graph \(G=(A,B,E)\) has a bipartition \(A\cup B=V\) with no adjacent vertices in A (B, respectively). For a bipartite graph \(G=(A,B,E)\) and two subset \(R\subseteq A\) and \(S\subseteq B\), we use G[R, S] to denote the induced bipartite subgraph \((R,S,\{(u,v)\in E|u\in R, v\in S\})\). In a complete bipartite graph \(G=(A,B,E)\), every vertex in A is adjacent to every vertex in B. A biclique in a bipartite graph is an induced complete bipartite subgraph.

A path is a vertex sequence with every two consecutive vertices adjacent. A cycle is a path where the first vertex is equal to the last vertex in the path. A graph is connected if every two vertices are connected by a path. A tree is a connected cycle-less graph. Two special kinds of trees are stars and triads. A star is a set of edges with a common end called its center. A triad is three paths with a common end also called its center.

Given a cycle, a chord is an edge whose two endpoints are not consecutive on the cycle. In a chordal bipartite graph, every cycle of length at least six has a chord. It is known that all convex bipartite graphs are chordal bipartite graphs, and all chordal bipartite graphs are tree convex bipartite graphs [4, 15]. In a circular convex bipartite graph \(G=(A,B,E)\), there is an associated circular ordering on A such that, for each vertex b in B, its neighborhood \(N_G(b)\) induces an arc or interval on A under the circular ordering [17, 19, 25].

3 Hardness

In this section, MEB is shown \(\mathcal {NP}\)-complete for star convex bipartite graphs.

Theorem 1

MEB is \(\mathcal {NP}\)-complete for star convex bipartite graphs.

Proof

The proof in [27], showing \(\mathcal {NP}\)-completeness of MEB in bipartite graphs, made a reduction from CLIQUE to MEB and produced a bipartite graph which is already a star convex bipartite graph. For completeness, we repeat the reduction here and check the star convexity of the produced bipartite graph.

Given an instance (G, k) of CLIQUE, we can assume that \(G=(V,E)\) and, without loss of generality, \(k=\frac{1}{2}|V|\). An instance \((G',k')\) of MEB is constructed by \(G'=(A,B,E')\), \(A=V\), \(B=E\cup W\), \(|W|=\frac{1}{2}k^2-k\), \(k'=k^3-\frac{3}{2}k^2\), and

$$ E'=\{(v,e)|v\in V, e\in E, v\not \in e\}\cup \{(v,w)|v\in V, w\in W\}. $$

The correctness of this reduction was shown in [27]. To see that \(G'\) is a star convex bipartite graph with an associated star T on B, note that each vertex w in W is adjacent to every vertex in A, thus we can take any w in W as the center of T and make all vertices in \(B\setminus \{w\}\) the leaves of T. The proof is finished.    \(\square \)

Since star convex bipartite graphs is a subclass of tree convex bipartite graphs, MEB is also \(\mathcal {NP}\)-complete for tree convex bipartite graphs. Another subclass of bipartite graphs is the so-called perfect elimination bipartite graphs, which is incomparable with respect to tree convex bipartite graphs by the results in [18]. We note that \(\mathcal {NP}\)-completeness of MEB for perfect elimination bipartite graphs or for the so-called comb convex bipartite graphs [29] is still unknown.

4 Tractability

In this section, MEB is shown polynomial time solvable for tree convex bipartite graphs whose associated trees are given and have a bounded number of leaves. In particular, MEB is polynomial time solvable for triad convex bipartite graphs.

To this end, we first show a structural property of optimal solutions of MEB for tree convex bipartite graphs. Recall that a solution of an instance (G, k) of MEB is a pair of sets (R, S), such that \(R\subseteq A\), \(S\subseteq B\), \(|R|*|S|\ge k\), and G[R, S] is a biclique, where G[R, S] is the subgraph of G induced by (R, S). We call a solution (R, S) to be optimal, if \(|R|*|S|\) is maximized among all the solutions.

Lemma 1

If (R, S) is an optimal solution to an instance (G, k) of MEB and \(G=(A,B,E)\) is a tree convex bipartite graph, with an associated tree \(T=(A,F)\), then R is a vertex set of a subtree in T, that is, \(V(T[R])=R\).

Proof

Recall that \(R\subseteq A\) and \(S\subseteq B\). For any two vertices x, y in R, there is a unique path \(P_{xy}\) in T connecting x and y. For every w in S, \(N_G(w)\) induces a subtree \(T[N_G(w)]\) in T, which contains both x and y. So any vertex z in \(P_{xy}\) is also in \(N_G(w)\) for all w in S, and \((R\cup \{z\},S)\) is also a solution to (G, k). If z is not in R, then \(|R\cup \{z\}|*|S|>|R|*|S|\), a contradiction to the optimality of (R, S). Thus, R is already a vertex set of a subtree in T.

The proof is finished.    \(\square \)

Lemma 2

In a tree with bounded number of leaves, the number of subtrees is bounded by a polynomial.

Proof

The number of leaves in a subtree will never exceeds the number of leaves in the tree. A subtree is uniquely determined by listing all its leaves. Indeed, a subtree is just the union of all pairs shortest paths between its leaves. If a tree with n vertices has \(L=O(1)\) leaves, then the number of its subtrees is at most \(O(n^L)=n^{O(1)}\). The proof is finished.    \(\square \)

Theorem 2

MEB is polynomial time solvable in tree convex bipartite graphs whose associated trees are given and have a constant number of leaves.

Proof

A polynomial time algorithm based on enumeration is as follows.

Input: (G, k), where \(G=(A,B,E)\) is a tree convex bipartite graph with an associated tree T on A. The number of leaves of T is a constant L.

Output: Yes, if there is (R, S) such that G[R, S] is a biclique and \(|R|*|S|\ge k\); No, otherwise.

Algorithm:

  1. 1.

    Enumerate all subtrees of T;

  2. 2.

    For each subtree with vertex set R, let \(S_R=\{w\in B|R\subseteq N_G(w)\}\).

  3. 3.

    Record \((R,S_R)\) with the maximum \(|R|*|S_R|\).

  4. 4.

    Return Yes, if \(|R|*|S_R|\ge k\); No, otherwise.

To enumerate all subtrees of T, we first enumerate and record all pairs shortest paths of T in \(O(n^3)\) time, where n is the input size, in any standard way. Note that for a tree T, the shortest path \(P_{xy}\) between two vertices x and y in T is also the unique path connecting x and y in T. Then we enumerate all subsets \(A'\) of size at most L of A in \(O(n^L)\) time, where L is the number of leaves of T. For each subset \(A'\) of A, we compute the union of all shortest paths \(P_{xy}\) in T for all pairs x and y in \(A'\) in \(O(nL^2)\) time, since we have \(O(L^2)\) paths and each path has length O(n). This union is a subtree \(T'\) of T, and any subtree \(T'\) of T is obtained in this way by putting all leaves of \(T'\) into \(A'\).

For each subtree \(T'\) with vertex set R, we can find the set \(S_R\) and compute \(|R|*|S_R|\) in \(O(n^2)\) time. So the total running time is \(O(n^{L+2})\).

The correctness of this algorithm is guaranteed by Lemmas 1 and 2. The proof is finished.    \(\square \)

Theorem 3

MEB is \(O(n^5)\) time solvable in triad convex bipartite graphs.

Proof

By Lemma 2 and the fact that all triads have three leaves.    \(\square \)

The number of subtrees in a star with n vertices is \(O(2^n)\), and this seems to be a reason for the hardness of MEB for star convex bipartite graphs. We guess that MEB is also hard for comb convex bipartite graphs by the same reason, that is, an exponential number of subtrees.

We note that Lemma 1 does not hold for circular convex bipartite graphs. We construct a circular convex bipartite graph G by \(G=(A,B,E)\), where \(A=\{a_1,a_2,a_3,a_4\}\), \(B=\{b_1,b_2,b_3\}\), \(E=\{(a_i,b_j)|1\le i\le 4, 1\le j\le 3\}\setminus \{(a_1,b_3),(a_3,b_1)\}\), and the associated circular ordering on A is T, as shown in Fig. 1. The maximum biclique in G is induced by \(R=\{a_2,a_4\}\) and \(S=B\), but R does not induce an interval in T. Due to this break down of the connectedness of the optimal solutions of MEB for circular convex bipartite graphs, the above enumeration algorithm does not work for circular convex bipartite graphs. We note that it is still unknown whether MEB is polynomial time solvable for circular convex bipartite graphs.

Fig. 1.
figure 1

A circular convex bipartite graph G whose optimal solution does not induce an interval in T.

Full size image

5 Comparison

In this section, we show that triad convex bipartite graphs are incomparable with respect to chordal bipartite graphs.

Lemma 3

There is a triad convex bipartite graph which is not a chordal convex bipartite graph.

Proof

Let \(G=(A,B,E)\) with \(A=\{a_0,a_1,a_2,a_3\}\), \(B=\{b_1,b_2,b_3\}\) and \(E=\{(b_i,a_0),(a_i,b_i),(a_i,b_{i-1\bmod 3})|1\le i\le 3\}\). That is, the graph G is a cycle \(C=a_1b_1a_2b_2a_3b_3a_1\) plus a star with center \(a_0\) and leaves \(b_1,b_2,b_3\), as shown in Fig. 2.

Apparently, G is not a chordal bipartite graph, since G has a cycle C of length 6 but without a chordal. We can easily check that G is a triad convex bipartite graph, with the associated triad T, where \(V(T)=\{a_0,a_1,a_2,a_3\}\) and \(E(T)=\{(a_0,a_1),(a_0,a_2),(a_0,a_3)\}\), respectively. The proof is finished.    \(\square \)

Fig. 2.
figure 2

A triad convex bipartite graph G which is not a chordal bipartite graph.

Full size image

We note that this graph G is used to separate tree convex bipartite graphs from chordal bipartite graphs in [18]. Actually, G separates triad convex bipartite graphs and star convex bipartite graphs from chordal bipartite graphs, as shown above.

Lemma 4

There is a chordal convex bipartite graph which is not a triad convex bipartite graph.

Proof

Let \(G=(A,B,E)\) with \(A=\{a_0, \ldots ,a_4\}\), \(B=\{u_1,\ldots ,u_4,w_1,\ldots ,w_4\}\) and \(E=\{(w_i,a_i),(a_i,u_i),(u_i,a_0)|1\le i\le 4\}\). That is, the graph G is four paths \(P_i=w_ia_iu_ia_0\) (\(1\le i\le 4\)) with a common end \(a_0\), as shown in Fig. 3.

Apparently, G is a chordal bipartite graph, since G contains no cycle at all. To show that G is not a triad convex bipartite graph, by symmetry of G, it is enough to show that none of \(w_1,a_1,u_1,a_0\) is the center of the associated triad T. Indeed, if \(w_1\) is the center of T, since \(N_G(a_0)=\{u_1,u_2,u_3,u_4\}\), then \(u_1,u_2,u_3,u_4\) must be grouped into a subpath P in T. Since \(N_G(a_i)=\{w_i,u_i\}\) for \(2\le i\le 4\), each of \(w_2,w_3,w_4\) must be consecutive to the path P, but this is impossible, since P only has two ends. If \(a_1\) is the center of T, since \(N_G(u_i)=\{a_i,a_0\}\) for \(2\le i\le 4\), then each of \(a_2,a_3,a_4\) must be consecutive to \(a_0\) in T, but this is impossible, since \(a_0\) has at most two neighbors in T. If \(u_1\) is the center of T, then by Pigeonhole Principle, two of \(w_1,u_2,u_3,u_4\) must be on a subpath of T, but this is impossible, since \(N_G(a_1)=\{w_1,u_1\}\) and \(N_G(a_0)=\{u_1,u_2,u_3,u_4\}\), any two of \(w_1,u_2,u_3,u_4\) must be consecutive to \(u_1\) simultaneously and thus can not be on a subpath of T. If \(a_0\) is the center of T, then by Pigeonhole Principle again, two of \(a_1,a_2,a_3,a_4\) must be on a subpath of T, but this is impossible, since \(N_G(u_i)=\{a_i,a_0\}\) for \(1\le i\le 4\), each of \(a_1,a_2,a_3,a_4\) must be consecutive to \(a_0\) in T. The proof is finished.    \(\square \)

Fig. 3.
figure 3

A chordal bipartite graph G which is not a triad convex bipartite graph.

Full size image

6 Conclusions

We have shown that MEB is \(\mathcal {NP}\)-complete for star convex bipartite graphs, but polynomial time solvable for tree convex bipartite graphs whose associated trees have a constant number of leaves. In particular, MEB is \(O(n^3)\) polynomial time solvable for triad convex bipartite graphs. We also have show that the enumeration algorithm may not work for circular convex bipartite graphs, and triad convex bipartite graphs are incomparable with respect to chordal bipartite graphs.

We list some open problems. First, it is unknown that whether MEB is \(\mathcal {NP}\)-complete for comb convex bipartite graphs. Second, it is unknown that whether MEB is tractable for circular convex bipartite graphs. Third, it is unknown that whether the \(O(n^5)\) time bound of MEB for triad convex bipartite graphs can be lowered to \(O(n(\log n)^k)\) or \(O(n^2(\log n)^k)\).