# Min Weight Complete bipartite subgraph

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.

• 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$? Commented May 8, 2013 at 9:36
• 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
– Joe
Commented May 8, 2013 at 17:56
• In this case, I would like to suggest you to revise your question to make it more specific. Commented May 8, 2013 at 19:47