Balanced ST-Connectivity

About these ads

7 thoughts on “Balanced ST-Connectivity

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

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s