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

Let be a directed graph. Let be the underlying undirected graph of . Let be a path in . Let be an edge along the path . Edge is called *neutral* edge if both and are in . Edge is called *forward* edge if and . Edge is called *backward* edge if and .

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

Balanced ST-Connectivity: Given a directed graph and two distinguished nodes and , decide if there isbalancedpath (of length at most ) between and .

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 ?

**Cash Prize** : I will offer $100 for a proof of . 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 ) 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 . 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 and is of length . The directed simple path from to is of length . There is a cycle of length at the vertex . All the edges (except ) on this cycle are undirected. The balanced path from to is obtained by traversing from to , traversing the cycle clockwise for times and then traversing from to .

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 ?
- Are there directed graphs where every balanced st-path is of super-polynomial size ?
(solved)- More open problems are mentioned in my paper.