st-connectivity – My Brain is Open

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.

Share this:

Like this: