ECCC-Report TR09-029https://eccc.weizmann.ac.il/report/2009/029Comments and Revisions published for TR09-029en-usThu, 09 Apr 2009 00:00:00 +0300
Revision 1
| Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space |
Fabian Wagner,
Thomas Thierauf
https://eccc.weizmann.ac.il/report/2009/029#revision1We 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.
Thu, 09 Apr 2009 00:00:00 +0300https://eccc.weizmann.ac.il/report/2009/029#revision1
Paper TR09-029
| Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space |
Fabian Wagner,
Thomas Thierauf
https://eccc.weizmann.ac.il/report/2009/029We 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.
Mon, 06 Apr 2009 09:49:01 +0300https://eccc.weizmann.ac.il/report/2009/029