Published by the Department of Computer Science, The University of Chicago.

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 reachability properties. For $K_5$-free graphs we also need a decomposition into 4-connected components. Thereby we provide a logspace reduction to the planar reachability problem.

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.

• The article: PDF (327 KB)
• Source material: ZIP (278 KB)
• BibTeX entry for this article (306 bytes)

Submitted May 30,2012, revised October 14, 2013, and February 8, 2014, final form received March 14, 2014, published March 28,2014.

© 2014 Thomas Thierauf and Fabian Wagner
Licensed under a Creative Commons Attribution License

Article 1

Article 3

Volume 2014

Published articles