This post is about a beautiful twist on flows that arises when studying (the dual) of the Sparsest Cut SDP. These objects, which I’m going to call “PSD flows,” are rather poorly understood, and there are some very accessible open problems surrounding them. Let’s begin with the definition of a normal flow:
Let be a finite, undirected graph, and for every pair , let be the set of all paths between and in . Let . A flow in G is simply a mapping . We define, for every edge , the congestion on as
which is the total amount of flow going through . Finally, for every , we define
as the total amount of flow sent from u to v.
Now, in the standard (all-pairs) maximum concurrent flow problem, the goal is to find a flow F which simultaneously sends units of flow from every vertex to every other, while not putting more than one unit of flow through any edge, i.e.
In order to define a PSD flow, it helps to write this in a slightly different way. If we define the symmetric matrix
then we have
Claim 1: .
To see that this is true, we can take a matrix with for all and fix it one entry at a time so that and , without decreasing the total demand satisfied by the flow.
For instance, if and , then it must be that , so we can reroute units of flow going through the edge to go along one of the extraneous flow paths which gives the excess . Similar arguments hold for the other cases (Exercise!).
So those are normal flows. To define a PSD flow, we define for any symmetric matrix A, the Laplacian of A, which has diagonal entries and off-diagonal entries . It is easy to check that
Hence if for all , then certainly (i.e. L(A) is positive semi-definite). The PSD flow problem is precisely
where is defined as above. Of course, now we are allowing to have negative entries, which makes this optimization trickier to understand. We allow the flow to undersatisfy some demand, and to overcongest some edges, but now the “error” matrix has to induce a PSD Laplacian.
Scaling down the capacities
Now, consider some , and write
Requiring for every simply induces a standard flow problem where each edge now has capacity . In the case of normal flows, because we can decouple the demand/congestion constraints as in Claim 1, we can easily relate to (the first is exactly times the second, because we can just scale a normal flow down by and now it satisfies the reduced edge capacities).
Question: Can we relate and ? More specifically, do they differ by some multiplicative constant depending only on ?
This is a basic question whose answer is actually of fundamental importance in understanding the Sparsest Cut SDP. I asked this question in its primal form almost 4 years ago (see question 3.2 here).
Note that the answer is affirmative if we can decouple the demand/congestion constraints in the case of PSD flows. In other words, let and let .
Question: Can we relate to ?
In the next post, I’ll discuss consequences of this question for constructing integrality gaps for the Sparsest Cut SDP.