4
$\begingroup$

Suppose we are given a large bipartite graph with weighted edges, and a small parameter $d$ (e.g. $d$ is 3 or 4). What is known about the run-time to find the minimum weight complete bipartite subgraph $K_{d,d}$?

I'm looking for an algorithm that beats the trivial $n^{O(d)}$ algorithm. I would like $o(n^d)$ or a fixed parameter version: $O(f(d)\cdot n^c)$ for some computable function $f$ and constant $c$.

I expect that the former should be possible, since a related question of finding $3r$-cliques in $O(n^{\omega r})$ time is possible using matrix multiplication. See A new algorithm for optimal constraint satisfaction and its implications by Ryan Williams.

$\endgroup$
3
  • 1
    $\begingroup$ This question might be revised to make it clearer. Let $d$ be the size you want ($K_{d,d}$). When $d$ is part of the input, then it is NP-hard even without the weight condition (see GT24, \emph{balanced complete bipartite subgraph problem}, in GJ). On the other hand, there is a triial polynomial algorithm of runtime $n^{O(d)}$ when $d$ is fixed. So, are you asking for the parameterzied complexity of this problem, that is, the existence of an algorithm in time $f(d)\cdot n^c$? $\endgroup$
    – Yixin Cao
    May 8, 2013 at 9:36
  • $\begingroup$ I would be happy with either $o(n^d)$, or the fixed parameter version. The former I expect should be possible, since a related question of finding $3r$-cliques in $O(n^{\omega r})$ time is possible with matrix multiplication. cs.cmu.edu/~ryanw/2-csp-final.pdf $\endgroup$
    – Joe
    May 8, 2013 at 17:56
  • $\begingroup$ In this case, I would like to suggest you to revise your question to make it more specific. $\endgroup$
    – Yixin Cao
    May 8, 2013 at 19:47

0

Your Answer

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

Browse other questions tagged or ask your own question.