<p>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 (<a href="http://www.sciencedirect.com/science/article/pii/S0166218X03003330">Peeters</a>, <em>Discrete Applied Mathematics</em> 131, pages 651-654, 2003).  </p>

<p>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 &gt; 0$ (<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.8586">Feige</a>, STOC 2002; Goerdt and Lanka, ECCC 2004; Ambuhl, Mastrolilli, and Svensson SICOMP 2011).  These results hold even when $G$ is bipartite.</p>

<p>I was wondering whether any results are known for finding the maximum edge biclique in <em>co-comparability graphs</em>.  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.</p>

<p>Specific questions:</p>

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

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

CC BY-SA 3.0
2013-10-27T17:21:04.790Z
Just an observation: the co-comparability graph is perfect by Dilworh's theorem. Maybe this can help.
Sasho Nikolov
CC BY-SA 3.0
2013-10-28T15:58:15.753Z
Thanks for the comment.  Unfortunately, since bipartite graphs are perfect, the $n^\delta$ hardness mentioned above applies to perfect graphs.
Rajmohan Rajaraman
CC BY-SA 3.0
2013-10-28T19:00:34.333Z
Good point, I had not noticed the hardness holds for bipartite graphs.
Sasho Nikolov
<cc.complexity-theory><graph-algorithms><approximation-algorithms>
Complexity and approximability of maximum edge biclique problem on co-comparability graphs
Rajmohan Rajaraman
# Complexity and approximability of maximum edge biclique problem on co-comparability graphs

(Asked by: username_0 on 2013-10-26)

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](http://www.sciencedirect.com/science/article/pii/S0166218X03003330), *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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.8586), 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?

**Tags:** cc.complexity-theory, graph-algorithms, approximation-algorithms
> **Comments:**
> **username_1**: Just an observation: the co-comparability graph is perfect by Dilworh's theorem. Maybe this can help.  
> **username_0**: Thanks for the comment.  Unfortunately, since bipartite graphs are perfect, the $n^\delta$ hardness mentioned above applies to perfect graphs.  
> **username_1**: Good point, I had not noticed the hardness holds for bipartite graphs.  

---

## 0 answers

