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.
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.