Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-029 | 9th April 2009 00:00

Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space

RSS-Feed




Revision #1
Authors: Fabian Wagner, Thomas Thierauf
Accepted on: 9th April 2009 00:00
Downloads: 1468
Keywords: 


Abstract:

We show that the reachability problem for directed graphs that are either K_{3,3}-free or K_5-free is in unambiguous log-space, UL \cap coUL. This significantly extends the result of Bourke, Tewari, and Vinodchandran that the reachability problem for directed planar graphs is in UL \cap coUL. Our algorithm decomposes the graphs into biconnected and triconnected components. This gives a tree structure on these components. The non-planar components are replaced by planar components that maintain the reachabilty properties. For K_5-free graphs we also need a decomposition into fourconnected components. A careful analysis finally gives a polynomial size planar graph which can be computed in log-space. We show the same upper bound for computing distances in K_{3,3}-free and K_5-free directed graphs and for computing longest paths in K_{3,3}-free and K_5-free directed acyclic graphs.


Paper:

TR09-029 | 3rd April 2009 00:00

Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space





TR09-029
Authors: Fabian Wagner, Thomas Thierauf
Publication: 6th April 2009 09:49
Downloads: 1639
Keywords: 


Abstract:

We show that the reachability problem for directed graphs
that are either K_{3,3}-free or K_5-free
is in unambiguous log-space, UL \cap coUL.
This significantly extends the result of Bourke, Tewari, and Vinodchandran
that the reachability problem for directed planar graphs
is in UL \cap coUL.

Our algorithm decomposes the graphs into biconnected and triconnected components.
This gives a tree structure on these components.
The non-planar components are replaced by planar components
that maintain the reachabilty properties.
For K_5-free graphs we also need a decomposition into fourconnected components.
A careful analysis finally gives a polynomial size planar graph which can be computed
in log-space.

We show the same upper bound for computing distances
in K_{3,3}-free and K_5-free directed graphs
and for computing longest paths
in K_{3,3}-free and K_5-free directed acyclic graphs.



ISSN 1433-8092 | Imprint