Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. $$M^+=\max\limits_{(U_1,U_2)}\left\{\sum_{e=\{u,v\}\in E\,:\,u\in U_1,v\in U_2}w_e\ :\ U_1\cup U_2=V,\ U_1\cap U_2=\emptyset\right\},$$ $$M^-=\min\limits_{(U_1,U_2)}\left\{\sum_{e=\{u,v\}\in E\,:\,u\in U_1,v\in U_2}w_e\ :\ U_1\cup U_2=V,\ U_1\cap U_2=\emptyset\right\}.$$ I'm interested in possible ratios between the difference $M^+-M^-$ and $\sum_{e\in E}\lvert w_e\rvert$. From Corollary 3.7 in the paper Some results on the strength of multilinear functions it follows that $M^+-M^-\geqslant\frac{1}{n-1}\sum_{e\in E}\lvert w_e\rvert$. Taking complete bipartite graphs and choosing the weights independently and uniformly at random from $\{\pm 1\}$ we find that there are graphs with $M^+-M^-=o(1)\sum_{e\in E}\lvert w_e\rvert$.

  1. Are there better lower bounds known? Maybe under additional assumptions on the weight fun (for instance if $w_e\in\{1,-1\}$ for all $e$)?
  2. What are known constructions with $M^+-M^-\leqslant f(n)\sum_{e\in E}\lvert w_e\rvert$ for some "small" function $f$? For instance, can we replace the $o(1)$ in the random construction by $O(1/n)$?

Cross posted on MO.

  • $\begingroup$ If we have, say, a line graph (or a cycle) with all equal weights, then isn't the difference zero? Or I'm missing something. $\endgroup$
    – usul
    Oct 7 '14 at 17:56
  • $\begingroup$ @usul A path is bipartite: you can cut all the edges. So the difference is not zero, it's $n-2$ for an $n$-node path. $\endgroup$ Oct 7 '14 at 18:12
  • 2
    $\begingroup$ The random construction you describe gives $M^+ - M^- = O(n^{3/2})$ and the sum of the absolute values of the weights is $n(n-1)/2$. So $f(n) = O(1/\sqrt{n})$. $\endgroup$ Oct 7 '14 at 18:23
  • 1
    $\begingroup$ FYI, you're not supposed to simultaneously cross-post: meta.cstheory.stackexchange.com/a/231/5038. A standard guideline would be to only cross-post on here and MO if you get no answer on the original site after a week or so. $\endgroup$
    – D.W.
    Oct 8 '14 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.