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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.