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.

7 thoughts on “Balanced ST-Connectivity”

why not at cstheory ?

I will ask on cstheory sometime later.

I might read this post a little late but it sounds pretty interesting. I checked your paper on eccc, I think on page 10 there is a small typo, positive should be changed to nonnegative at line -8. It is also a bit strange to me that you end by defining two problems…

Anyhow, about the open problem related to the shortest balanced st-path, I guess that it is not possible to go above n^2. I will put here my rough idea, maybe you already thought of it and know that it does not work.

Claim 1. If for all i a_i<n and gcd(a_i's)=1, then there are lambda_i such that sum lambda_i a_i =1 and sum |lambdai_i||a_i| is at most n^2.

These a_i are the unbalancedness numbers of the (simple) cycles that are in the same component as s and t.

Claim 2. If d=gcd(a_i) and there is a balanced st path, then d divides the length of every st path.

I guess you see how the proof would follow from here – take a simple st path, take a suitable collection of lambda_i's given by claim 1, connect all these cycles to the path by going there and back for them.

kintali | April 15, 2011 at 3:49 PM

@domotorp : We recently used a similar technique to prove that both balanced paths and positive balanced paths can only be of polynomial length. I will soon make these results public.

Whether SGSLOGCFL is in Logspace is still open.

Reply

Pingback: Graph Isomorphism of Minor-free Graphs « My Brain is Open

Is there a simple reason why you restrict paths to be of length at most n? Naively, it seems a very artificial cutoff, since you are not considering simple paths and the paths can only have polynomial length anyway.

kintali | March 12, 2012 at 2:26 AM

The restriction on path lengths can be removed since the path lengths are polynomial. However, for the purpose of proving space bounds, we may assume that the length of the path is at most n.

Also, we recently proved that SGSLOGCFL is in L. I will blog about it soon.

Reply

My Brain is Open

Computational Complexity, Polyhedral Combinatorics, Algorithms and Graph Theory

Balanced ST-Connectivity

7 thoughts on “Balanced ST-Connectivity”

Leave a Reply Cancel reply

Share this:

Like this:

Related

7 thoughts on “Balanced ST-Connectivity”

Leave a Reply Cancel reply