ECCC-Report TR09-024https://eccc.weizmann.ac.il/report/2009/024Comments and Revisions published for TR09-024en-usSat, 21 Mar 2009 10:24:02 +0200
Paper TR09-024
| On the Power of Isolation in Planar Structures |
Raghav Kulkarni
https://eccc.weizmann.ac.il/report/2009/024The 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.
Sat, 21 Mar 2009 10:24:02 +0200https://eccc.weizmann.ac.il/report/2009/024