8
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Just an observation: the co-comparability graph is perfect by Dilworh's theorem. Maybe this can help. $\endgroup$
    – Sasho Nikolov
    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$
    – Rajmohan Rajaraman
    Oct 28, 2013 at 15:58
  • $\begingroup$ Good point, I had not noticed the hardness holds for bipartite graphs. $\endgroup$
    – Sasho Nikolov
    Oct 28, 2013 at 19:00

0

Reset to default

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.