# Complexity and approximability of maximum edge biclique problem on co-comparability graphs

A subgraph $H$ of a given graph $G$ is called a biclique of $G$ if $H$ is a complete bipartite graph. Given a graph $G$, finding a maximum edge biclique is known to be NP-complete (Peeters, Discrete Applied Mathematics 131, pages 651-654, 2003).

In fact, it is also known that it is unlikely we can obtain an $n^{\delta}$-approximation for this problem in polynomial time, for some constant $\delta > 0$ (Feige, STOC 2002; Goerdt and Lanka, ECCC 2004; Ambuhl, Mastrolilli, and Svensson SICOMP 2011). These results hold even when $G$ is bipartite.

I was wondering whether any results are known for finding the maximum edge biclique in co-comparability graphs. There are several equivalent definitions of a co-comparability graph. One of them is a graph whose vertices are the elements of a partial order, and the edges are given by pairs of elements that are incomparable in the partial order.

Specific questions:

(1) Is the maximum edge biclique problem polynomially solvable for co-comparability graphs?

(2) If no polynomial time optimal algorithm is known, what is the best approximation algorithm known?

• Just an observation: the co-comparability graph is perfect by Dilworh's theorem. Maybe this can help. Oct 27, 2013 at 17:21
• Thanks for the comment. Unfortunately, since bipartite graphs are perfect, the $n^\delta$ hardness mentioned above applies to perfect graphs. Oct 28, 2013 at 15:58
• Good point, I had not noticed the hardness holds for bipartite graphs. Oct 28, 2013 at 19:00