Please indicate whether each of the following statements is TRUE or FALSE and provide a brief justification

I provided my answers in the "answer your own question" bit.

I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though?

a) Suppose f is a flow of value 50 from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to 50.

b) Suppose f is a flow of value 100 from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to 100.

c) Suppose f is a flow of value 20 from s to t in a flow network G and there is an s-t cut of capacity 20. Then there are no s --> t paths in the residual graph Gf.

d)Suppose f is a flow of value 100 from s to t in a flow network G and there is an s-t cut of capacity 100. Then there are no s --> t paths in the residual graph Gf.

e) Given a flow network where all the edge capacities are even integers, the Ford-Fulkerson algorithm will require at most C/2 iterations, where C is the total capacity leaving the source s.

f) Let G be a directed graph with n nodes and edge weights that might be negative, but no negative cycles. The shortest path from node s to node t has at most n-1 edges.

I think this is true. I know that there is no negative cycle, so the shortest path will not have any loop. But I'm not really sure how I know this...like how did we logic that out

g) P!=NP True. This is just a fact. But worth noting it has neither been proved nor disproved?

• Your question is too broad, and still "check my answer". Your last question is about open problem, so off-topic here. (It also takes one answer for granted, but it was not proved, so the game is still on). – Evil Dec 14 '18 at 11:42
• I'm voting to close this question as off-topic because it is a request for assignment grading. – David Richerby Dec 14 '18 at 14:40

Condensed A/B and C/D into two general t/f statments with explanations:

A/ B Suppose f is a flow of some value X from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to X.

This is FALSE. HOWEVER, if the flow were maximum, then the amount of max-flow is equal to size of min-cut making it TRUE

C/D Suppose f is a flow of some value X from s to t in a flow network G and there is an s-t cut of capacity X. Then there are no s --> t paths in the residual graph Gf.

TRUE. Once the max-flow is computed then there is not path from s to t in the residual graph.

e) Given a flow network where all the edge capacities are even integers, the Ford-Fulkerson algorithm will require at most C/2 iterations, where C is the total capacity leaving the source s.

TRUE because FF algorithm estimates every possible path from s to t and since every path from s to t will have minimum capacity of 2, FF will take half amount of iteration i.e. C/2 iteration to compute result.

f) Let G be a directed graph with n nodes and edge weights that might be negative, but no negative cycles. The shortest path from node s to node t has at most n-1 edges.

g) P!=NP

TRUE(?)