  In this paper, we study a generalization of the classical minimum cut prob-
lem, called Connectivity Preserving Minimum Cut (CPMC) problem, which seeks a
minimum cut to separate a pair (or pairs) of source and destination nodes and
meanwhile ensure the connectivity between the source and its partner node(s).
The CPMC problem is a rather powerful formulation for a set of problems and
finds applications in many other areas, such as network security, image
processing, data mining, pattern recognition, and machine learning. For this
important problem, we consider two variants, connectiv- ity preserving minimum
node cut (CPMNC) and connectivity preserving minimum edge cut (CPMEC). For
CPMNC, we show that it cannot be ap- proximated within {\alpha}logn for some
constant {\alpha} unless P=NP, and cannot be approximated within any poly(logn)
unless NP has quasi-polynomial time algorithms. The hardness results hold even
for graphs with unit weight and bipartite graphs. Particularly, we show that
polynomial time solutions exist for CPMEC in planar graphs and for CPMNC in
some special planar graphs. The hardness of CPMEC in general graphs remains
open, but the polynomial time algorithm in planar graphs still has important
practical applications.
