# tcs math – some mathematics of theoretical computer science

## February 16, 2009

### Open question: PSD flows

Filed under: Math, Open question — Tags: , , — James Lee @ 1:03 pm

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 $G=(V,E)$ be a finite, undirected graph, and for every pair $u,v \in V$, let $\mathcal P_{uv}$ be the set of all paths between $u$ and $v$ in $G$.  Let $\mathcal P = \bigcup_{u,v \in V} \mathcal P_{uv}$.  A flow in G is simply a mapping $F : \mathcal P \to \mathbb R_{\geq 0}$.  We define, for every edge $(u,v) \in E$, the congestion on $(u,v)$ as

$\displaystyle C_F(u,v) = \sum_{p \in \mathcal P: (u,v) \in p} F(p)$

which is the total amount of flow going through $(u,v)$.  Finally, for every $u,v \in V$, we define

$F\displaystyle \lbrack u,v\rbrack = \sum_{p \in \mathcal P_{uv}} F(p)$

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 $D$ units of flow from every vertex to every other, while not putting more than one unit of flow through any edge, i.e.

$\displaystyle \mathsf{mcf}(G) = \textrm{maximize } \left\{ \vphantom{\bigoplus} D : \forall u,v, F[u,v] \geq D \textrm{ and } \forall (u,v) \in E, C_F(u,v) \leq 1.\right\}$

In order to define a PSD flow, it helps to write this in a slightly different way.  If we define the symmetric matrix

$A_{u,v} = F[u,v] - D + {\bf 1}_{\{(u,v) \in E\}} - C_F(u,v)$

then we have

Claim 1: $\mathsf{mcf}(G) = \max \{ D : A_{u,v} \geq 0 \}$.

To see that this is true, we can take a matrix with $A_{u,v} \geq 0$ for all $u,v \in V$ and fix it one entry at a time so that $F[u,v] \geq D$ and $C_F(u,v) \leq 1$, without decreasing the total demand satisfied by the flow.

For instance, if $(u,v) \in E$ and $C_F(u,v) > 1+\varepsilon$, then it must be that $F[u,v] > D+\varepsilon$, so we can reroute $\varepsilon$ units of flow going through the edge $(u,v)$ to go along one of the extraneous flow paths which gives the excess $F[u,v] > D + \varepsilon$.  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 $L(A)_{i,i} = \sum_{j \neq i} A_{i,j}$ and off-diagonal entries $L(A)_{i,j} = - A_{i,j}$.  It is easy to check that

$\displaystyle \langle x, L(A)\, x \rangle = \sum_{i,j} A_{i,j} (x_i-x_j)^2.$

Hence if $A_{u,v} \geq 0$ for all $u,v \in V$, then certainly $L(A) \succeq 0$ (i.e. L(A) is positive semi-definite).  The PSD flow problem is precisely

$\displaystyle \max \{ D : L(A) \succeq 0 \}$

where $A$ is defined as above.  Of course, now we are allowing $A$ 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 $\delta \in [0,1]$, and write

$\displaystyle A_{u,v}^{(\delta)} = F[u,v] - D + \delta \cdot {\bf 1}_{(u,v) \in E} - C_F(u,v).$

Requiring $A_{u,v}^{(\delta)} \geq 0$ for every $u,v \in V$ simply induces a standard flow problem where each edge now has capacity $\delta$.  In the case of normal flows, because we can decouple the demand/congestion constraints as in Claim 1, we can easily relate $\max \{ D : A_{u,v}^{(\delta)} \geq 0\,\forall u,v \in V\}$ to $\max \{ D : A_{u,v} \geq 0\,\forall u,v \in V\}$ (the first is exactly $\delta$ times the second, because we can just scale a normal flow down by $\delta$ and now it satisfies the reduced edge capacities).

Question: Can we relate $\max \{ D : L(A^{(\delta)}) \succeq 0 \}$ and $\max \{ D : L(A) \succeq 0 \}$?  More specifically, do they differ by some multiplicative constant depending only on $\delta$?

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 $X_{u,v} = F[u,v] - D$ and let $Y_{u,v} = {\bf 1}_{(u,v \in E)} - C_F(u,v)$.

Question: Can we relate $\max \{ D : L(A) \succeq 0 \}$ to $\max \{ D : L(X) \succeq 0 \textrm{ and } L(Y) \succeq 0 \}$?

In the next post, I’ll discuss consequences of this question for constructing integrality gaps for the Sparsest Cut SDP.