<p>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}$? </p>

<p>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$.</p>

<p>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 <em>A new algorithm for optimal constraint satisfaction
and its implications</em> by Ryan Williams.</p>

CC BY-SA 3.0
2013-05-08T09:36:14.217Z
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$?
Yixin Cao
CC BY-SA 3.0
2013-05-08T17:56:43.047Z
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. http://www.cs.cmu.edu/~ryanw/2-csp-final.pdf
Joe
CC BY-SA 3.0
2013-05-08T19:47:29.597Z
In this case, I would like to suggest you to revise your question to make it more specific.
Yixin Cao
<reference-request><graph-algorithms>
Min Weight Complete bipartite subgraph
Joe
# Min Weight Complete bipartite subgraph

(Asked by: username_0 on 2013-05-08)

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.

**Tags:** reference-request, graph-algorithms
> **Comments:**
> **username_1**: 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$?  
> **username_0**: 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. http://www.cs.cmu.edu/~ryanw/2-csp-final.pdf  
> **username_1**: In this case, I would like to suggest you to revise your question to make it more specific.  

---

## 0 answers

