2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Juho
    Dec 17, 2021 at 19:04

1 Answer 1

2
$\begingroup$

Whenever you think about graphs of bounded diameter, you should consider what happens when you add a universal vertex. A universal vertex is a vertex whose neighborhood is the entire graph.

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

The two problems are equivalent.

$\endgroup$
2
  • $\begingroup$ Thanks. Your saying that we cannot calculate complexity with only having diameter? $\endgroup$ Dec 18, 2021 at 9:53
  • $\begingroup$ Yes, the complexity is the same for graphs with arbitrarily large diameter and of graphs with diameter 2. $\endgroup$
    – Pål GD
    Dec 18, 2021 at 11:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.