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!).

**PSD flows**

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.

going with the spirit, the following is also worth studying (it has applications to fast algorithms for Sparsest Cut):

following the notation in this post, we now only allow those F, the “flow matrix”, that can be written as the sum of t-perfect matchings (assume no. of nodes is even) F=M_1+…+M_t. (M_i is the adjacency matrix of the i-th perfect matching.) Further each M_i comes with a “congestion matrix” C_i. Thus, C_F=C_1+…+C_t. It is also given that each C_i[u,v] <= c for some fixed constant c for every edge u,v in G independent of i.

the problem is to understand how much restriction does this actually put on the max-PSD value when we only allow such F,C pairs, rather than arbitrary F,C as in the current definition.

Comment by nisheeth vishnoi — February 24, 2009 @ 3:06 am