Chicago Journal of Theoretical Computer Science

Volume 2014

Article 2

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

Reachability in $K_{3,3}$-free and $K_5$-free Graphs is in Unambiguous Logspace

Thomas Thierauf
University of Aalen
thomas.thierauf AT


Fabian Wagner
University of Ulm
fabian.wagner AT

April 14, 2014


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.

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

DOI: 10.4086/cjtcs.2014.002

[] Article 1 [] Article 3
[back] Volume 2014 [back] Published articles
[CJCTS home]