# Edmonds Karp time complexity based on graph's diameter

Suppose we have a graph such that we want to apply a maximum flow algorithm(for example Edmonds Karp) on it. And suppose we only know that graph's diameter is 70 so we want to calculate that's time comlexity .
As you know , Edmonds Karp time complexity is O(V.E^2).

We can conclude that we must know V and E of the graph to compute it's worst case time complexity. But I don't know how to find vertices or edges of the graph based on the diameter . Any ideas?

• You can't, i.e., the difference between the number of vertices can be arbitrarily larger than the diameter of the graph. For example, take a star graph: it has diameter $d=2$ but you can make the star as large as you like to grow $n-d$, where $n$ is the order of the graph.
– Juho
Dec 17, 2021 at 19:04

Suppose that you are given an instance $$G, s, t$$ with $$n$$ vertices and $$m$$ edges. Multiply all capacities with $$2(n+m)$$. Then you add a universal vertex with capacities 1 on every edge. The diameter of this new graph is 2, but to find the maximum flow, you have to compute the maximum flow of the original graph. If you take the final flow and divide it by $$2(n+m)$$ and floor it, you get the maximum flow of $$G$$.