Balanced ST-Connectivity

Today’s post is about a new open problem arising from my recent paper  (available on ECCC). The problem is as follows :

Let G(V,E) be a directed graph. Let G'(V,E') be the underlying undirected graph of G. Let P be a path in G'. Let e = (u,v) be an edge along the path P. Edge e is called neutral edge if both (u,v) and (v,u) are in E. Edge e is called forward edge if (u,v) \in E and (v,u) \notin E. Edge e is called backward edge if (u,v) \notin E and (v,u) \in E.

A path (say P) from s \in V to t \in V in G'(V,E') is called balanced if the number of forward edges along P is equal to the number of backward edges along P. A balanced path might have any number of neutral edges. By definition, if there is a balanced path from s to t then there is a balanced path from t to s. The path P may not be a simple path. We are concerned with balanced paths of length at most n.

Balanced ST-Connectivity : Given a directed graph G(V,E) and two distinguished nodes s and t, decide if there is balanced path (of length at most n) between s and t.

In my paper, I proved that SGSLOGCFL, a generalization of Balanced ST-Connectivity, is contained in DSPACE(lognloglogn). Details about SGSLOGCFL are in my paper.

Theorem 1 : SGSLOGCFL is in DSPACE(lognloglogn).

Open Problem : Is SGSLOGCFL \in L ?

Cash Prize : I will offer $100 for a proof of SGSLOGCFL \in L. I have spent enough sleepless nights trying to prove it. In fact, an alternate proof of Theorem 1 (or even any upper bound better than O({\log}^2n)) using zig-zag graph product seems to be a challenging task.

Usually people offer cash prizes for a mathematical problem when they are convinced that :

  • it is a hard problem.
  • it is an important problem worth advertising.
  • the solution would be beautiful, requires new techniques and sheds new light on our understanding of related problems.

My reason is “All the above”. Have Fun solving it !!

A cute puzzle : In Balanced ST-Connectivity we are only looking for paths of length at most n. There are directed graphs where the only balanced st-path is super-linear. The example in the following figure shows an instance of Balanced ST-Connectivity where the only balanced path between s and t is of length \Theta(n^2). The directed simple path from s to t is of length n/2. There is a cycle of length n/2 at the vertex v. All the edges (except (v,u)) on this cycle are undirected. The balanced path from s to t is obtained by traversing from s to v, traversing the cycle clockwise for n/2 times and then traversing from v to t.

Puzzle : Are there directed graphs where every balanced st-path is of super-polynomial size ?

Update : The above puzzle is now solved.

Open Problems

  • Is SGSLOGCFL \in L ?
  • Are there directed graphs where every balanced st-path is of super-polynomial size ? (solved)
  • More open problems are mentioned in my paper.