### Volume 2014

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

Thomas Thierauf
University of Aalen
Germany
thomas.thierauf AT htw-aalen.de

and

Fabian Wagner
University of Ulm
Germany
fabian.wagner AT uni-ulm.de

April 14, 2014

#### 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)