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