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.

About these ads

1 Comment »

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


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 72 other followers

%d bloggers like this: