I have 2 max-flow function f1,f2 that are different from one another (atleast on a single edge). I know they give each edge a natural even value.

I constrct 2 types of average functions:

A)$ g (e) = (f1(e)+f2(e))/2$

B) $h(e)=f1(e)*1/3 + f2(e)*2/3$

I want to prove or disproof their being max flow functions too.

My thoughts are to prove its true in both cases. I think for g I can look at the min-cut. I know the flow in the min-cut must be the same at that cut's capacity. So it means each edge in the cut is flowed like its capacity. Then the average is flowing the same for these edges... So g is a max flow too.

I feel the same argument shows h is max flow too. I believe it can be generelized for any fraction?

I would also like to hear whats the thoughts on my proof for g amd h? Am i right? Or did i mistake?

  • $\begingroup$ Try the following: (1) the average of flows is a flow, (2) the flow rate of an average of flows is the average of their flow rates. $\endgroup$ Feb 18 '21 at 15:37
  • $\begingroup$ By flow rate you mean the flow's size |f1|? $\endgroup$
    – Eric_
    Feb 18 '21 at 15:40
  • 1
    $\begingroup$ Right. I wasn't sure how this quantity is called. $\endgroup$ Feb 18 '21 at 15:41
  • $\begingroup$ An approach that might yield an easy proof (I haven't tried it) involves writing down the associate LP problem for max flow. Then you can show that the objective value is unaffected and that all constraints are satisfied. $\endgroup$
    – Steven
    Feb 18 '21 at 17:40
  • $\begingroup$ @Steven This sounds like Yuval Filmus's hint with extra steps. Btw Eric, you can generalize this to any convex combination of max flows being a max flow. $\endgroup$
    – Tassle
    Feb 18 '21 at 17:44

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.