Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-024 | 26th February 2009 00:00

On the Power of Isolation in Planar Structures


Authors: Raghav Kulkarni
Publication: 21st March 2009 10:24
Downloads: 3957


The purpose of this paper is to study the deterministic
{\em isolation} for certain structures in directed and undirected
planar graphs.
The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and
\cite{dkr08} isolate a perfect matching in bipartite planar graphs.
One natural question raised by
their work is: ``How far is the reach of the deterministic isolation in planar structures ?''

Our first observation is that the restriction of planarity is in fact, fairly general,
in the sense that efficiently isolating certain planar structures would
significantly bring down the complexities of some fundamental problems in general graphs.
For example, we show that efficiently isolating a cycle
cover in directed planar graphs would imply {\em {\sf Bipartite-Matching}
$\in$ NC}, efficiently isolating a minimum weight perfect matching in undirected
planar graphs would imply that non-deterministic log-space computations
can be made unambiguous, i.e., {\em NL = UL} and efficiently isolating a {\em Red-Blue path} in
directed planar graphs would imply $NP \subseteq \oplus P.$

Further, we show that such efficient
isolations are indeed possible in {\em bipartite} planar
graphs, thus leaving non-bipartiteness as the only bottleneck to break.
A deceptively simple combinatorial puzzle comes out of our investigations where
a positive solution to the puzzle would have strong consequences like $NL = UL.$
Our main tools are some new simple bijections, which might
be of an independent interest combinatorially.

ISSN 1433-8092 | Imprint