%% Camera ready version for ESA 2005
%============================================================
\documentclass{llncs}
%============================================================
%\usepackage{latexsym} % \Box
\usepackage{amsmath}
\usepackage{graphicx} % eps figures
\usepackage{comment} % \begin{comment} ... \end{comment}
\usepackage{times}
%\usepackage{bbm}
%\usepackage{fullpage}
%\usepackage{cite} % tries to abbreviate long citation lists
\usepackage{hyperref} %%% A cool package - it's for submission draft only ... it gives some links
%%% that you can use even while working with the .dvi file
%%% If can't compile ... then compile once again (it needs two passes when call for the first time)
%%% If still doesn't work then just comment this line; it's not really needed,
%%% it's for convenience only
\let\epsilon\varepsilon
\def\ignore#1{}
%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}{Lemma}
\newcommand{\OPT}{\ensuremath{\text{\rm OPT}}}
\def\MST{{\rm MST}}
\def\Augment{{\rm Augment}}
%\newenvironment{proof}{\par\vspace*{-\parsep}\noindent{\bf
%Proof:}}{{\nolinebreak~\hfill$\Box$}\par\medskip}
%% Intra-author comments:
\def\Artur #1{\Comment{$\cal A.C.$ --- #1}}
\def\Hairong#1{\Comment{$\cal H.Z.$ --- #1}}
\def\Andre #1{\Comment{$\cal A.B.$ --- #1}}
\def\Mic #1{\Comment{$\cal M.G.$ --- #1}}
%% Choose one:
%\let\Comment\footnote % visible comments
\let\Comment\ignore % hidden comments
%% Title ideas:
%% 1. SODA04 title with addition of ``Weighted''
\ignore{Approximation Schemes for Minimum 2-Edge-Connected and
Biconnected Subgraphs in Weighted Planar Graphs}
%% 2. shorter version of the above:
\ignore{Approximate Minimum 2-Connected Subgraphs in Weighted
Planar Graphs}
%% 3. ICALP 2005 title
\title{Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in
Weighted Planar Graphs\thanks{Research supported in part by NSF
grants CCR-0208929 and ITR-CCR-0313219.}}
%% 4. ICALP 2005 title - shorter as above - but if we use times then the
%previous one is better
\ignore{Approximate Minimum 2-Connected Subgraphs in Weighted
Planar Graphs\thanks{Research supported in part by NSF grants
CCR-0208929 and ITR-CCR-0313219.}}
\author{
Andr\'{e} Berger\thanks{%
Department of Mathematics and Computer Science, Emory
University, Atlanta GA 30322, USA.
Email: \textsf{aberge2@emory.edu}, \textsf{mic@mathcs.emory.edu}.
Research supported in part by NSF grant CCR-0208929.}
\and
Artur Czumaj\thanks{%
Department of Computer Science,
New Jersey Institute of Technology,
Newark NJ 07102, USA.
Email: \{\textsf{czumaj,hairong}\}\textsf{@cis.njit.edu}.
Research supported in part by NSF grants
ITR-CCR-0313219 and CCR-0105701.}
\and
Michelangelo Grigni\footnotemark[1]
\and
Hairong Zhao\footnotemark[2]
}
\author{
Andr\'{e} Berger \inst{1}
\and
Artur Czumaj \inst{2}
\and
Michelangelo Grigni \inst{1}
\and
Hairong Zhao \inst{2}
}
\institute{Department of Mathematics and Computer Science, Emory
University, Atlanta GA 30322, USA. Email: \textsf{\scriptsize
aberge2@emory.edu}, \textsf{\scriptsize mic@mathcs.emory.edu}.
\and
Department of Computer Science, New Jersey Institute of
Technology, Newark NJ 07102, USA. Email: \{\textsf{\scriptsize
czumaj,hairong}\}\textsf{\scriptsize @cis.njit.edu}. }
\date{}
\begin{document}
\maketitle \thispagestyle{empty}
\begin{abstract}
We present new approximation schemes for various classical
problems of finding the minimum-weight spanning subgraph in
edge-weighted undirected \emph{planar graphs} that are resistant
to edge or vertex removal. We first give a PTAS for the problem of
finding minimum-weight 2-edge-connected spanning subgraphs where
duplicate edges are allowed. Then we present a new greedy spanner
construction for edge-weighted planar graphs, which augments any
connected subgraph $A$ of a weighted planar graph $G$ to a
$(1+\epsilon)$-spanner of $G$ with total weight bounded by
$\text{weight}(A)/\epsilon$. From this we derive quasi-polynomial
time approximation schemes for the problems of finding the
minimum-weight 2-edge-connected or biconnected spanning subgraph
in planar graphs. We also design approximation schemes for the
minimum-weight 1-2-connectivity problem, which is the variant of
the survivable network design problem where vertices have
non-uniform (1 or 2) connectivity constraints. Prior to our work,
for all these problems no polynomial or quasi-polynomial time
algorithms were known to achieve an approximation ratio better than
$2$.
\begin{comment}
We present new approximation schemes for various classical
problems of finding the minimum-weight spanning subgraph in
edge-weighted undirected \emph{planar graphs} that are resistant
to edge or vertex removal. We give a new greedy spanner
construction for edge-weighted planar graphs, which augments any
connected subgraph $A$ of a weighted planar graph $G$ to a
$(1+\epsilon)$-spanner of $G$ with total weight bounded by
$\text{weight}(A)/\epsilon$. From this we derive quasi-polynomial
time approximation schemes for the problems of finding the
minimum-weight 2-edge-connected or biconnected spanning subgraph
in planar graphs. We also design approximation schemes for the
minimum-weight 1-2-connectivity problem, which is the variant of
the survivable network design problem where vertices have
non-uniform (1 or 2) connectivity constraints. Prior to our work,
for all these problems no polynomial or quasi-polynomial time
algorithms were known to achieve approximation ratio better than
$2$.
\end{comment}
\end{abstract}
%=====================================
\section{Introduction}
\label{sec:introduction}
%\subsection{The 2-ECSS and 2-VCSS Problems}
\label{sec:problems}
The \emph{survivable network design problem} is to design graphs
that resist edge and/or vertex removal. This is a fundamental
problem in algorithmic graph theory with numerous applications in
computer science and operations research
%\cite{-GM90,-GMS92,-GMS95,-K96,-MS89,-BOOK-S92}.
(see, e.g., \cite{-GMS95,-K96,-BOOK-S92}). The classical
\emph{$k$-connectivity} problems are perhaps the most extensively
studied problems in network design. We are given a graph $G$ with
$n$ vertices and a nonnegative weight $w(e)$ on each edge $e$, and
we want to find a $k$-edge or $k$-vertex connected \emph{spanning}
subgraph $S$, such that its total edge weight $w(S)$ equals
$\OPT$, the minimum possible. It is well-known that all
non-trivial variants of the survivable network design problem are
$\mathcal{NP}$-hard and therefore the main research interest lies
in the design of efficient approximation algorithms (see, e.g.,
\cite{-K96} for a survey).
In this paper we consider approximation algorithms for the most
basic case of the survivable network design problem in which the
resulting subgraphs should be resistant to the removal of a
\emph{single} edge or vertex. The two classical problems here are
to find a minimum-weight 2-edge-connected (2-EC) spanning subgraph
(a 2-ECSS) of $G$, or a 2-vertex-connected (2-VC or biconnected)
spanning subgraph (a 2-VCSS) of $G$. We also consider a standard
relaxation of the 2-ECSS problem of finding a minimum weight 2-EC
spanning sub-\emph{multigraph} (2-ECSSM) $H$ of $G$, meaning that
an edge of $G$ can be used multiple times in $H$ (consequently its
weight is also counted multiple times in $H$). Another classical
extension is the \emph{1-2-connectivity problem}: each vertex $v$
is assigned a connectivity type $r_v \in \{1,2\}$. The problem is
to find a minimum weight spanning subgraph such that for any pair
of vertices $v, u \in V$, there are at least $r_{uv} = \min\{r_u,
r_v\}$ edge-disjoint or vertex-disjoint paths between $v$ and $u$.
We denote the 1-2-edge-connectivity by \{1,2\}-EC, and
1-2-vertex-connectivity by \{1,2\}-VC. We also consider the
relaxed 1-2-edge-connectivity problem where each edge may be used
more than once.
All the problems mentioned above have been extensively studied in
the literature. Since all these problems are $\mathcal{NP}$-hard,
the main research has been devoted to design efficient
approximation algorithms, see the survey \cite{-K96} and more
recent advances \cite{-CVV03,-G02,-G03,-JRV03,-KN04}.
%
\begin{comment} % EVERYBODY SHOULD KNOW THIS! SO WHY WASTE SPACE?
A \emph{$c$-approximation algorithm} always produces a
\emph{$c$-approximate} solution, which is a solution $S$ such that
$w(S) \le c \cdot\OPT$; the constant $c \ge 1$ is the
\emph{approximation guarantee} of the algorithm.
\end{comment}
%
In general, we would prefer to design a \emph{polynomial-time
approximation scheme (PTAS)}, which is a $c$-approximation
algorithm taking both $G$ and $c$ as inputs, and running in
polynomial time for each fixed $c > 1$. However, all the problems
we consider in this paper are max-SNP-hard \cite{-CL99}, even for
unweighted graphs or when duplicate edges are allowed; therefore
they do not have a PTAS unless $\mathcal{P} = \mathcal{NP}$. But
this does not preclude a PTAS for restricted classes of graphs:
indeed, there exist PTAS's for all these problems in
\emph{geometric graphs} in low dimensions \cite{-CL99,-CLZ02}, and
also for the 2-ECSS and 2-VCSS problems in \emph{unweighted planar
graphs} \cite{-CGSZ04}.
%
In fact, the approximation schemes of \cite{-CGSZ04} allow
\emph{weighted} planar graphs,
%
%\begin{comment}
but then the algorithms will either run in time
$n^{O(\tfrac{w(G)}{\epsilon \cdot \OPT})}$ to ensure an
$(1+\epsilon)$-approximate solution or they run in polynomial time with
an approximation guarantee of 1+$O(\tfrac{w(G)}{\epsilon \cdot
\OPT})$. Since the ratio $w(G)/\OPT$ could be arbitrarily large,
these algorithms are in general not PTAS's for weighted planar
graphs. \Andre{I rewrote the sentence. I didn't find clear what
$\lambda$ would be; and in SODA2004 we stated it with running time
$n^{w(G)/\OPT}$}
%\end{comment}
%
\begin{comment} % Artur: I think the description above is better
% than what we had before - in our SODA'04 paper
% we must work as my text describes: you decide
% about the running time and then you'll get
% the bound as I wrote. If you knew the value of
% $\OPT$ then the old text would make some sense,
% but we don't know $\OPT$ and also even if you
% knew, the next text should sound better (even
% though it's longer)
but then those algorithms run in time $n^{O((1/\epsilon)
(w(G)/\OPT))}$, where $\epsilon = c - 1$. The ratio $w(G)/\OPT$
appearing in the exponent could be arbitrarily large.
\end{comment}
For both the 2-ECSS and 2-VCSS problems in weighted planar graphs,
the best known polynomial-time or even quasi-polynomial-time
approximation guarantee is still 2 \cite{-KV94,-PS97}, which is
achieved by polynomial-time algorithms working for general
weigh\-ted graphs. On the other hand, besides the PTAS for
unweighted planar graphs \cite{-CGSZ04}, there are better constant
approximation guarantees known for general unweighted graphs. For
example, there exists a $\frac54$-approximation algorithm for the
unweighted 2-ECSS problem~\cite{-JRV03}, and a
$\frac43$-approximation algorithm for the unweighted 2-VCSS
problem \cite{-VV00}.
A similar phenomenon can be seen for the 1-2-connectivity
problems. For both, the unweighted \{1,2\}-ECSS and the unweighted
\{1,2\}-VCSS problem, Krysta \cite{-K03} gives
$\frac32$-approximation algorithms. If the graph is weighted, the
best known result for \{1,2\}-ECSS is a 2-approximation algorithm,
due to Jain \cite{-J01}, which in fact solves the more general
problem where $r_v \le k$ for any $k$. For the weighted
\{1,2\}-VCSS problem, Fleischer \cite{-F01} gives a
2-approximation algorithm, which actually solves the
\{0,1,2\}-VCSS problem. A PTAS for the geometric version of these
problems is presented in~\cite{-CLZ02}.
The discrepancy between approximation guarantees of the unweighted
and weighted versions of these problems is a phenomenon that is
known also for general graphs.
%Both problems have been extensively studied, and
%the approximation guarantees achievable for unweighted graphs are
%significantly better than those for weighted graphs.
A striking discrepancy is known for the $k$-VCSS problem ($k \gg
2$), which admits a $(1+1/k)$-approximation for the unweighted
case \cite{-CT00}, while for the weighted version of the problem
the best known approximation guarantee is $O(\ln k \cdot
\min\{\sqrt{k}, \tfrac{n}{n-k} \ln k\})$~\cite{-KN04} for any $k$,
and is $O(\ln k)$ when $n \ge
6 \, k^2$ \cite{-CVV03}. % $O(\log n)$ (see also ).
\Mic{More details on the constants in this gap.} In general, a
PTAS for unweighted graphs in some family does not seem to imply a
PTAS for weighted graphs in the same family. In particular, the
existence of polynomial-time or even quasi-polynomial-time
approximation schemes for these problems in weighted planar graphs
has remained as a major open question in the area.
%=====================================
\subsection{New Contributions and Techniques}
We present efficient approximation schemes for all the above
mentioned problems in weighted planar graphs. Our approximation
algorithms depend in a crucial way on our new construction of
\emph{light spanners} for planar graphs.
%================================================================
Let $G$ be a weighted graph. We use $d_G(u,v)$ to denote the
weighted shortest path distance between the vertices $u$ and $v$
in $G$. An \emph{$s$-spanner} of $G$ is a spanning subgraph $H$
of $G$ such that $d_H(u,v) \le s\cdot d_G(u,v)$ for all $u,v$. A
spanner provides an approximate representation of the shortest
path metric (1-connectivity) in $G$, but it may be much lighter
than $G$.
Alth{\"o}fer et al. \cite{-ADDJS93} designed a simple greedy
algorithm that for an arbitrary graph~$G$ computes an $s$-spanner
$H$ of $G$ for any $s > 1$. In the case of \emph{planar} graphs,
it is shown in \cite{-ADDJS93} that this spanner has weight $w(H)
\le (1+2/(s-1))\MST(G)$, where $\MST(G)$ is the weight of a
minimum spanning tree in $G$.
%
\begin{comment}
For general graphs, a simple greedy algorithm \cite{-ADDJS93}
computes an $s$-spanner $H$ for any $s > 1$, and in \emph{planar}
graphs this spanner has weight $w(H) \le (1+2/(s-1))\MST(G)$,
where $\MST(G)$ is the weight of a minimum spanning tree in $G$.
\end{comment}
%
Since $\MST(G) \le \OPT$ for all the problems we consider, this
bounds the ratio $w(H)/\OPT$ in terms of just~$s$. If all weighted
graphs in a graph family have spanners with such a bound on
$w(H)/\OPT$ (depending only on $s$), then we say the family has
\emph{light spanners} for this problem. Light spanners are known
to be very useful for solving various optimization problems on
graphs. For example, planar graphs have light spanners for
metric-TSP: the first step in the metric-TSP PTAS for weighted
planar graphs \cite{-AGKKW98} is to replace the input graph with
an accurate enough $s$-spanner (using \cite{-ADDJS93}), thus
effectively bounding $w(G)/\OPT$ for the remainder of the
algorithm. Spanners are also used in complete geometric graphs to
design efficient PTAS's for geometric TSP and related problems
\cite{-RS98}, and to design PTAS's for the 2-edge and
2-vertex-connectivity problems \cite{-CL00,-CLZ02}.
By combining the spanner constructed in \cite{-ADDJS93} with the
planar separator decomposition approach tuned to analyze
2-connected graphs \cite{-CGSZ04}, we show that one can design a
PTAS for the 2-ECSSM problem and a PTAS for the \{1,2\}-ECSSM
problem. However, this approach of replacing the input graph with
an $s$-spanner fails for the 2-ECSS and 2-VCSS problems. The
reason is that a spanner does not have to be 2-connected, thus may
not contain the optimal or a near optimal solution in most cases.
Naturally, one may think to use light \emph{fault-tolerant}
spanners (see, e.g., in \cite{-LNS98}), which are subgraphs that
persist as $s$-spanners even after deleting a constant number of
vertices or edges. Unfortunately, this concept is not useful in
our setting, since simple examples show that light fault-tolerant
spanners do not exist in weighted planar graphs, not even for a
single edge deletion.
%==================================================================
To solve the problem mentioned above, we present our main
contribution: a new greedy spanner construction which produces a
light planar spanner with certain desirable properties.
Specifically, given a weighted planar graph $G$, a connected
spanning subgraph $A$ of $G$ and $s>1$, it computes an $s$-spanner
$H$ of $G$. $H$ contains $A$ as a subgraph and has total weight
$w(H)=O(1/(s-1) \cdot w(A))$.
%%%%% Why MST ???
%If $A$ is a minimum spanning tree of $G$, then the algorithm
%resembles the result of Alth{\"o}fer et al.~\cite{-ADDJS93} for
%planar graphs.
%
Thus if we feed the algorithm with $\alpha$-approximate
solutions $H$ to the various connectivity problems in a weighted
planar graph $G$, then we obtain an $O(\alpha /
(s-1))$-approximation $H^*$ for that problem, which at the same
time is an $s$-spanner for $G$. Furthermore, we can show that
while $H^*$ need not contain an $(1+\epsilon)$-approximate solution
$S$, we do put a bound on the number of edges of $S$ ``crossing''
each face of $H^*$ (Lemma \ref{lemma:cross}).
Using our new spanner construction technique and the planar
separator decomposition, we design approximation schemes for the
2-ECSS and 2-VCSS, \{1,2\}-ECSS and \{1,2\}-VCSS problems, which
find solutions with weight at most $(1 + \epsilon) \cdot \OPT$ in
$n^{O(\log n \, \log(1/\epsilon) / \epsilon)}$ time; these are
\emph{quasi-polynomial time approximation schemes} (QPTAS's).
\paragraph{\bf Organization.}
We first present a PTAS for the 2-ECSSM problem in Section
\ref{sec:2ecssm}. This section contains also a description of the
main algorithmic approach used in our approximation schemes, which
is a combination of the use of spanners, a recursive approach driven
by a variant of the planar separator theorem, and dynamic
programming. Next, in Sections \ref{sec:spanner} and \ref{sec:H*},
we describe our new construction of spanners and discuss the
special properties of the spanners. In Section \ref{sec:scheme},
we present quasi-polynomial approximation schemes for the 2-ECSS
and the 2-VCSS problems. Finally in Section \ref{sec:12extension},
we consider \{1,2\}-ECSS and \{1,2\}-VCSS problems: we show a PTAS
for the \{1,2\}-ECSSM problem, and a QPTAS for each of the
\{1,2\}-ECSS and \{1,2\}-VCSS problems.
\begin{comment}
We present a new greedy spanner construction for weighted planar
graphs which generalizes the construction from~\cite{-ADDJS93} in
the case of planar graphs. Using this construction we obtain
efficient approximation schemes for all the above mentioned
connectivity problems in weighted planar graphs. No
quasi-polynomial-time algorithms with an approximation guarantee
better than $2$ was known for any of these problems before.
Let $G$ be a weighted graph and let $d_G(u,v)$ denote the
weighted shortest path distance between the vertices $u$ and $v$
in $G$. An \emph{$s$-spanner} of $G$ is a spanning subgraph $H$
of $G$ such that $d_H(u,v) \le s\cdot d_G(u,v)$ for all $u,v$. A
spanner provides an approximate representation of the shortest
path metric (1-connectivity) in $G$, but it may be much lighter
than $G$.
Alth{\"o}fer et al. \cite{-ADDJS93} designed a simple greedy
algorithm that for an arbitrary graph $G$ computes an
$s$-spanner~$H$ of~$G$ for any $s > 1$. In the case of
\emph{planar} graphs, it is shown in \cite{-ADDJS93} that this
spanner has weight $w(H) \le (1+2/(s-1))\MST(G)$, where $\MST(G)$
is the weight of a minimum spanning tree in $G$. Light spanners
are known to be very useful for solving some optimization problems
on graphs. For example, the first step in the metric-TSP PTAS for
weighted planar graphs~\cite{-AGKKW98} is to replace the input
graph with an accurate enough $s$-spanner (using \cite{-ADDJS93}),
thus effectively bounding $w(G)/\OPT$ for the remainder of the
algorithm. Spanners are also used in complete geometric graphs to
design efficient PTAS's for geometric TSP and related problems
\cite{-RS98}, and to design PTAS's for the 2-edge and
2-vertex-connectivity problems \cite{-CL00,-CLZ02}.
We use the spanner from~\cite{-ADDJS93} to obtain a PTAS for the
2-ECSSM problem in Section~\ref{sec:2ecssm} and a PTAS for the
$\{1,2\}$-ECSSM problem in Section~\ref{sec:12extension}. However,
since a $s$-spanner need not be 2-connected, this approach fails
for the 2-ECSS and 2-VCSS problems. Moreover, light
\emph{fault-tolerant} spanners (see, e.g., in \cite{-LNS98}),
which are subgraphs that persist as $s$-spanners even after
deleting some constant number of vertices or edges, do not exist
in weighted planar graphs, not even for a single edge deletion.
The new greedy spanner construction as described in
Section~\ref{sec:spanner} will help us find 2-connected spanning
subgraphs with certain additional properties. In particular, given
a weighted planar graph $G$, a connected spanning subgraph $A$ of
$G$ and $s>1$, it computes a $s$-spanner $H$ of $G$. $H$ contains
$A$ as a subgraph and has total weight $w(H)=O(1/(s-1) \cdot
w(A))$. If $A$ is a minimum spanning tree of $G$, then the
algorithm resembles the result of Alth{\"o}fer et
al.~\cite{-ADDJS93} for planar graphs. However, we can feed the
algorithm with approximate solutions to the various connectivity
problems. Therefore, for any connectivity problem for which we can
find an $\alpha$-approximation in a weighted planar graph $G$, we
can also find an $O(\alpha / (s-1))$-approximation for that
problem which at the same time is a $s$-spanner for
$G$.\Andre{rephrased sentence}
This approach enables us to use techniques from~\cite{-CGSZ04} to
obtain QPTAS's for the 2-ECSS and 2-VCSS problems in weighted
planar graphs~(Section~\ref{sec:scheme}).
\end{comment}
%
\begin{comment}
In Section \ref{sec:12extension} we briefly discuss how to modify
the algorithm to obtain QPTAS's for the $\{1,2\}$-ECSS and the
$\{1,2\}$-VCSS problems.
\end{comment}
%=======================================
\section{PTAS for the 2-ECSSM Problem}%in Weighted Planar Graphs
\label{sec:2ecssm}
%Before the 2-ECSS problem, we first consider a relaxation: suppose the
%solution $S$ may be a 2-EC spanning sub-multigraph (2-ECSSM),\Mic {It
%is not really a sub-multigraph, since it may use an edge more often
%than it appears in $G$.} meaning that it may use each edge of $G$
%multiple times.
Let $G$ be a connected weighted graph. A 2-ECSSM $H$ of $G$ is a
spanning sub-multigraph of $G$ in which edges can have some
multiplicity and in which every pair of vertices is connected by
at least two edge-disjoint paths. Note that $G$ may not have any
multiple edges at all.
% but a 2-ECSSM may use an edge more often than it appears in $G$.
If an edge is used multiple times in $H$, its weight also
contributes multiple times to the weight of $H$. Since it never
helps to use an edge more than twice, we may cap all edge
multiplicities at two. We now present a PTAS for this problem,
running in $n^{O(1/\epsilon^2)}$ time.
Given $G$ and $\epsilon>0$, we choose $s$ so that $s^2
\le 1 + \epsilon$. We first compute an $s$-spanner $H$ in $G$ by
the greedy spanner algorithm \cite{-ADDJS93}, with weight $w(H) =
O((1/\epsilon) \cdot \OPT)$.
Now we show that there is a $(1+\epsilon)$-approximate 2-ECSSM
that uses only edges from $H$. Suppose $S^*$ is an optimal 2-ECSSM
in $G$ with $w(S^*) = \OPT$. Now we modify $S^*$ such that it uses
only edges from $H$. For each edge $e$ of $S^*$ not in $H$, we
remove $e$ and add a shortest path from $H$ of total weight at
most $s \cdot w(e)$. When we add the path, we add the edges with
multiplicity, but capped at two. The result of all these
modifications is another 2-ECSSM $S$, using only edges from $H$,
each edge used at most twice, with $w(S) \le s \cdot \OPT$.
Next we apply the 2-ECSS $s$-approximation algorithm from
\cite{-CGSZ04} to the graph $H'$, which is $H$ with each edge
duplicated. Since this algorithm forms also a core of our
algorithm for other problems discussed later in Sections
\ref{sec:scheme} and \ref{sec:12extension}, we briefly describe it
here. The algorithms in \cite{-CGSZ04} use a recursive approach
driven by the following planar separator theorem from
\cite{-BGZ04} (see also \cite{-CGSZ04}):
\begin{lemma}
\label{lemma:separator}
Let $G$ be a connected planar graph on $n \ge 3$ vertices
embedded in the plane. Suppose $G$ has non-negative weights on its
vertices, edges and faces, and non-negative costs on its edges.
Let $W$ be the total weight of the graph and let $M$ be its total
cost and assume that no edge has weight more than $(3/4) \cdot W$.
Then for any positive integer $k$, we can find a subgraph $F$ of
$G$ and a closed Jordan curve $J$ in $O(n)$ time such that:
%
\begin{enumerate}
\item $F$ is the union of at most two vertex-disjoint simple
cycles (maybe none). The total cost of the edges on each cycle is
at most $M/k$. If $F$ contains two cycles $A$ and $C$, then
$interior(C)\subset interior(A)$. The interior of $C$ and the exterior of
$A$ (if they exist) both have weight at most $W/2$.
\item Denote by $G'$ the embedded graph that results after
deleting the interior of $C$ and the exterior of $A$ (if they
exist) and contracting each cycle in $F$ to a vertex of weight~0.
Then $J$ is a Jordan curve which intersects edges of $G'$ only at
their endpoints and passes through $O(k)$ vertices (``portals'')
including the new contracted vertices. The interior and exterior
of $J$ both have weight at most $(3/4) \cdot W$.
%\item The set of vertices of $G'$ on $J$ has size $O(k)$.
\end{enumerate}
\end{lemma}
First, we decompose $H'$ according to Lemma \ref{lemma:separator}
(with $k = \Theta((\log n/\epsilon) \cdot \frac{w(H')}{\OPT}) =
\Theta(\log n/\epsilon^2)$) into at most four pieces: the interior
of the cycle~$C$, the exterior of the cycle~$A$, and the interior
and the exterior of the Jordan curve~$J$. By assigning weight to
the new portals and faces properly, we can make sure that each
piece has weight at most a constant fraction of the $H'$. We
continue to decompose the small pieces recursively. It is easy to
see that the depth of the recursion is logarithmic, and the number
of pieces is $O(n \log n)$. By the weighting scheme of the new
portals (\cite{-AGKKW98,-CGSZ04}), one can show that each piece
has a portal set $P$ with size $O(k)$.
We would like to find a low cost spanning subgraph in each piece
and then combine them together to form an almost minimum wight
2-ECSS of $H'$. Of course we do not know the remaining subgraph
outside this piece. Thus, for each piece, we enumerate all the
different ways that some subgraph of $H'$ (outside this piece) may
influence the connectivity constraints within this piece. We call
these the \emph{external types} of the piece, and one can show
that the number of such types is $2^{O(|P|)} =
n^{O(1/\epsilon^2)}$~\cite[Lemma 2.4]{-CGSZ04}, where $P$ is the
set of portals of this piece.
For each piece and each external type, we must find a near
minimum cost subgraph of the piece, so that this subgraph together
with the external type can meet the global connectivity
constraints. We use dynamic programming to solve the subproblems
in each of the pieces.
During the course of the algorithm, we always commit the cycle
edges found in the separator to the solution, which is the only
source of the error in our algorithm. Since the cycle edges has
total cost at most $w(H')/k$ at each level of the recursion and
there are at most $O(\log n)$ levels, by setting appropriately the
leading constant in $k$, we can show that the total error
introduced in the algorithm is $\epsilon \cdot \OPT$. For each
piece, the number of types is bounded by $n^{O(w(H')/(\epsilon
\cdot \OPT))} = n^{O(1/\epsilon^2)}$. There are $O(n \log n)$
pieces. Therefore the algorithm solves $n^{O(1/\epsilon^2)}$
subproblems, each in time $n^{O(1/\epsilon^2)}$.
%
\begin{comment}
(One may check that \cite{-CGSZ04} allows parallel edges, or
alternatively just use a standard reduction from $H'$ back to a
simple graph.)
\end{comment}
%
%The 2-ECSS found in $H'$ is what we want: it is a 2-ECSSM of $G$
%with weight at most $s\cdot w(S) \le (1+\epsilon)\cdot\OPT$. The
%time used is $n^{O((1/(s-1)) (w(H')/\OPT))} =
%n^{O(1/\epsilon^2)}$.
In summary, we have the following theorem.
\begin{theorem}
\label{theorem:PTAS-multigraphs}
Let $\epsilon > 0$ and let $G$ be a connected weighted planar
graph with $n$ vertices. There is an algorithm running in time
$n^{O(1/\epsilon^2)}$ that outputs a 2-ECSSM of $G$ whose weight
is at most $(1 + \epsilon)$ times the minimum.
\end{theorem}
\paragraph{Why this technique fails for other problems:}
The above technique does not work for other problems considered in
this paper,
%for example, for the 2-ECSS problem, because we are not allowed to
%duplicate edges from $G$ in a 2-ECSS.
because there we are not allowed to duplicate edges from $G$ in
the output graph. Instead, our approximation schemes must consider
the possibility that the near-optimal $S$ needs some ``extra''
edges from outside the spanner. In Sections \ref{sec:spanner} and
\ref{sec:H*} we develop a new type of light planar spanners and we
limit the number and arrangement\Andre{which arrangement do we
limit?} of those extra edges outside the spanner.
%=====================================
\section{Augmented Planar Spanners}
\label{sec:spanner}
In this section we present a new greedy algorithm constructing
$s$-spanners in weighted planar graphs, resembling the standard
greedy algorithm \cite{-ADDJS93} for general graphs. Just as in
the standard algorithm, we take a connected weighted graph $G$ and
a parameter $s \ge 1$, and produce an $s$-spanner $H$. Unlike the
general algorithm, our $G$ must be planar, and for each edge $e$
of $G$ not in $H$ we guarantee that $s\cdot w(e)$ is at least the
length of some path in the face of $H$ containing $e$.
\Hairong{Since, $e$ is not it $H$, will 'containing' be
misleading? But I don't have a better word.} We also provide our
algorithm with a third argument: a ``seed'' spanning subgraph $A$,
containing edges that must appear in $H$. In Section \ref{sec:H*}
we will use $A$ to enforce some 2-connectivity properties in the
spanner.
\begin{figure}
\centering
\includegraphics{face-path.eps}
\caption{A non-simple face $f$ in $H$, a chord $e$, and walks
$P_1$ and $P_2$.}
\label{fig:face-path}
\end{figure}
Suppose $G$ is a weighted \emph{plane graph} (that is, an embedded
planar graph) and $H$ is a subgraph. A \emph{chord} $e$ of $H$ is
an edge of $G$ not in $H$. Note that $H$ and $e$ inherit
embeddings from $G$. For each chord $e$ we define $w_H(e)$ as the
length of the shortest walk connecting the endpoints of $e$, along
the boundary of the face of $H$ containing\Hairong{Same as the
previous note.} $e$.
More precisely, if the endpoints of $e$ are disconnected in $H$,
then we define $w_H(e) = +\infty$. Otherwise $e$ connects two
vertices in a component of $H$, and $e$ is embedded in some face
$f$ of this component. The boundary of $f$ is a cyclic walk of
(oriented) edges, with total weight $w(f)$; note that a cut-edge
may appear twice in the boundary (once per orientation), and its
weight would then count twice in $w(f)$. Similarly a cut-vertex
may appear multiple times. The edge $e$ splits the boundary
sequence into two walks $P_1$ and $P_2$, both connecting the
endpoints of $e$, with $w(P_1)+w(P_2)=w(f)$. Now we define
$w_H(e) = \min(w(P_1),w(P_2))$ (see Figure \ref{fig:face-path}).
Given $G$, $s$, and $A$ as above, we compute $H=\Augment(G,s,A)$
as follows:
\begin{tabbing}
xxx \= xxx \= xxx \= xxx \= \kill % set tab stops
\> $\textbf{\Augment}(G,s,A)$: \\
\> \> $H \leftarrow A$ \\
\> \> \textbf{for} all edges $e$ of $G$ in non-decreasing
$w(e)$ order \textbf{do} \\
\> \> \> \textbf{if} $e$ is not in $H$
% the preceding clause is not strictly necessary
\textbf{and} $s \cdot w(e) < w_H(e)$ \textbf{then} \\
\> \> \> \> add $e$ to $H$ \\
\> \> \textbf{return} $H$
\end{tabbing}
Note $A \subseteq H \subseteq G$. If $A$ is empty (has all
vertices of $G$ but no edges), then this is like the general
greedy spanner algorithm \cite{-ADDJS93}, except that we have
$w_H$ in place of $d_H$. \Mic {Note a path in $G$ is approximated
by a path which is ``visible'' from it in $H$.}
\begin{theorem}
\label{thm:spanner}
Let $G$ be a weighted plane graph, $s > 1$, and $A$ a spanning subgraph of $G$.
Then $H = \Augment(G,s,A)$ is an $s$-spanner of $G$. If $A$ is connected, then
$w(H) \le (1+2/(s-1))\cdot w(A)$.
\end{theorem}
\begin{proof}
To show that $H$ is an $s$-spanner it suffices to show that each edge of $G$ is
$s$-approximated in
$H$. For $e$ not in $H$, at the moment it was rejected we had
$w_H(e) \le s\cdot w(e)$. Note that $w_H(e)$ may only decrease
after that, so $d_H(e) \le w_H(e) \le s\cdot w(e)$ at the end of
the algorithm.\Mic {A path in $G$ is approximated by a path which
is ``visible'' from it in $H$. Note this ``$w_H(e) \le s\cdot
w(e)$'' property is also preserved under the contraction of edges
from $H$ (assuming we discard self-loops).}
For the second part we need to show that the weight of all edges
in $H$ but not $A$ is at most $(2/(s-1))\cdot w(A)$. Suppose $e$
is such an edge; then $e$ is not a cut edge in $H$ since $A$ is a
connected spanning subgraph. Therefore $e$ is bounded by two
distinct faces. Let $f$ be either face bounding $e$. We first
claim that $w(f) > (1+s)\cdot w(e)$. To see this, consider the
\emph{last} edge $e'$ added to $f$ whose boundary consists of a
path $P$ plus $e'$. Since $e'$ is added to $H$, we must have that
$s\cdot w(e') < w_H(e')$ and $w_H(e')\le w(P)$. Adding $w(e')$ to
both sides of $s\cdot w(e') < w(P)$, and noting $w(e)\le w(e')$,
we get the claim.
For each face $f$ of $A$, let $E_f$ be the set of edges in $H$
crossing the interior of $f$. Since the sum of $w(f)$ over all
faces of $A$ is $2\cdot w(A)$, it suffices to show that $w(E_f)\le
(1/(s-1))\cdot w(f)$. Note that the edges dual to $E_f$ define a tree
on the faces of $H$ inside $f$. Orient this dual tree away from
some arbitrarily chosen root: now for each $e\in E_f$, we have
chosen an adjacent face $f_e$ of $H$ (only the root was not
picked). For each $e\in E_f$ we know $w(f_e)-2\cdot w(e)
> (s-1)\cdot w(e)$, from the previous paragraph. Summing these
inequalities over all $e\in E_f$, we get at most $w(f)$ on the
left hand side, and exactly $(s-1)\cdot w(E_f)$ on the right.
%\qed
\end{proof}
% So $H$ is an $s$-spanner of $G$ with $w(H) \le (1+2/(s-1))\cdot w(A)$,
% and every chord of $H$ has its weight approximately lower bounded by a
% walk in the face containing it.
%=======================================
\section{Spanners and 2-EC Subgraphs}
\label{sec:H*}
\Mic{We might coin a name for this operation where we add $P_c$
(for some chord $c$) and then delete any other chords inside the
cycle $c+P_c$.}Suppose we are given a weighted plane 2-EC graph
$G$, where we want to find an $(1+\epsilon)$-approximate 2-ECSS.
We first construct an auxiliary subgraph $H^*$, as follows:
%
\begin{enumerate}
\item Compute a 2-approximate 2-ECSS $A$, in polynomial time.
\item Compute $H^* = \Augment(G,\sqrt{2},A)$.
\end{enumerate}
%
The constant $\sqrt{2}$ here is not critical, just convenient. By
Theorem~\ref{thm:spanner}, $H^*$ is a 12-approximate 2-ECSS. Below
we show that for every $\epsilon > 0$, this $H^*$ has nice
intersection properties with some $(1+\epsilon)$-approximate
2-ECSS in $G$.
Given a face $f$ in $H^*$, the chords of $f$ are the edges of $G$
embedded inside this face, according to $G$'s embedding. A
\emph{face-edge} $e$ of $f$ is an abstract edge connecting two
vertices of $f$; unlike a chord, a face-edge is not necessarily an
edge of $G$. (If vertices appear more than once on $f$, we must
specify which appearances we want as the endpoints of $e$.) We say
the face edge $e$ \emph{crosses} a chord $c$ if: $c$ is a chord of
the same face $f$, their endpoints are distinct vertex appearances
on $f$, and they appear in cyclic ``$ecec$'' order around the
boundary of $f$. Note that we may embed $e$ inside $f$ so $e$
intersects only the crossed chords.
Suppose $S$ is a 2-ECSS in $G$, and an edge $c$ of $S$ is not in
$H^*$. Then $c$ is a chord of some face $f$ of $H^*$. Let $P_c$
be the path in $f$ connecting the endpoints of $c$, such that
$w(P_c) \le \sqrt{2}\cdot w(c)$. Then the \emph{chord
move\Hairong{move or remove?} at $c$} is the following
modification of $S$: add to $S$ all the edges of $P_c$ that were
not already in $S$, and remove from $S$ any chords inside the
cycle $c \cup P_c$ (see Figure \ref{fig:chords}(a)). Since $H^*$
is 2-EC, the cycle has no repeated edges, and therefore $S$ is
still a 2-ECSS after the chord move. The chord move is
\emph{improving} if $w(S)$ decreases; this happens whenever
$w(P_c)$ (or $\sqrt{2}\cdot w(c)$) is less than the weight of the
discarded chords. Any non-trivial chord move brings $S$ closer to
$H^*$ (in Hamming distance), thus at most $O(n)$ improving chord
moves apply to any given 2-ECSS $S$.\Mic {Reduced lemma to this
sentence, since we do not really use it.}
\begin{figure}
\[
\begin{array}{ccc}
\includegraphics{chordmove.eps} & ~~~ & \includegraphics{5chords.eps} \\
{\rm (a)} & & {\rm (b)}
\end{array}
\]
\caption{(a) Face $f$ of $H^*$ (oval) with chord $c$, path $P_c$
(bold), and chords removed from $S$ by the chord move at $c$
(dotted). (b) Face $f$ with a face-edge $e$ (dashed) crossed by
five chords from $S$.} \label{fig:chords}
\end{figure}
\begin{comment}
\begin{lemma}
Given $H^*$ as above and a 2-ECSS $S$, we may efficiently compute
another 2-ECSS $S'$ such that $w(S') \le w(S)$, and no chord move
improves $w(S')$.
\end{lemma}
\begin{proof}
Start with $S'=S$. As long as $S'$ has an improving\Hairong{so
improving is with respect to the parameter $s$?} chord move, apply
it. Each move decreases the hamming distance\Hairong{I don't
understand this. Is it possible that $H^*$ and $S'$ contain quite
different set of edges?} between $S'$ and $H^*$ (where we think of
subgraphs as subsets of $E(G)$), so there are at most $O(n)$
improving moves.
%\qed
\end{proof}
\end{comment}
\begin{lemma}
\label{lem:4chords} Let $e$ be a face edge of a face $f$ in $H^*$ and $S$
be a 2-ECSS of $G$. Suppose $C$ is a set of edges of $S$ all of
which are chords crossing $e$, $\sqrt{2}\cdot\min_{c\in C} w(c) >
\max_{c\in C} w(c)$, and no chord in $C$ gives an improving chord
move. Then $|C| \le 4$.
\end{lemma}
\begin{proof}
If not, $S$ has five chords crossing $e$ as in Figure
\ref{fig:chords}(b). But then we have an improving chord move at
$c_3$, since the discarded chords ($\{c_1,c_2\}$ or $\{c_4,c_5\}$)
weigh more than $\sqrt{2}\cdot w(c_3)$.
%\qed
\end{proof}
Now we argue that by accepting a small additive error in our
2-ECSS, we may assume it has only a small number of chords
crossing a given face-edge:
\begin{lemma}
\label{lemma:cross}
Suppose $G$ and $H^*$ are as above, $\epsilon>0$, $S$ is a
2-ECSS, $f$ is a face in $H^*$, and $e$ is a face-edge in $f$.
Then there exists a 2-ECSS $S'$ such that $w(S') \le w(S) +
\epsilon\cdot w(C'_f)$, where $C'_f$ is the set of edges of $S'$
that are chords crossing $e$, $C'_f \subseteq S$, and $|C'_f| =
O(\log(1/\epsilon))$.
\end{lemma}
\begin{proof}
First we may suppose that $S$ has no improving chord move at a
chord crossing $e$, since such a move could only remove some
chords crossing $e$. Let $C_f$ be the set of chords in $S$
crossing $e$. Arrange $C_f$ in ``left to right'' order, according
to how they intersect $e$. Let $c_0\in C_f$ be the chord with
maximum weight. Say that a chord $c \in C_f$ is \emph{short} if
$w(c) \le \epsilon\cdot w(c_0)/(2\sqrt{2})$. Now if there are
short chords to the left of $c_0$, perform a chord move at the
rightmost one, $c_l$. Similarly if there are short chords to the
right of $c_0$, perform a chord move at the leftmost one, $c_r$.
$S'$ is the result of these (at most) two chord moves; note that
$C'_f$ contains no short chords except possibly $c_l$ and $c_r$.
Map each non-short chord $c\in C'_f$ to the real number
$\log(w(c_0)/w(c))$, a point in the real interval $I = [0,
\log(1/\epsilon)+3/2]$. Note that two edges can be mapped to the
same semi-open subinterval of $I$ of length $1/2$ only if the
heavier edge has weight less than $\sqrt{2}$ times that of the
lighter edge. By Lemma \ref{lem:4chords}, at most four edges can
be mapped into the same subinterval of $I$ of length $1/2$. This
implies $|C'_f|=O(\log(1/\epsilon))$.
The chord moves in $f$ increased $w(S')$ by at most $\sqrt{2}
(w(c_l)+w(c_r)) \le \epsilon \cdot w(c_0)$, which is at most
$\epsilon \cdot w(C'_f)$.
%\qed
\end{proof}
\paragraph{Remarks:}
In the 2-VCSS case, the initial $A$ should be a 2-approximate
2-VCSS, so that $H^*$ is a 12-approximate 2-VCSS. Then in the
chord move the cycle has no repeated vertices, therefore $S$
remains a 2-VCSS after the move. In Lemmas \ref{lem:4chords} and
\ref{lemma:cross}, the only properties of $H^*$ that we needed
were that it was 2-EC (or 2-VC), and that $w_{H^*}(e)\le
\sqrt{2}\cdot w(e)$ for each chord $e$.\Mic {These observations
let us use a piece $H'$ in place of $H^*$.}
%====================================================
\section{Approximation Schemes for the 2-ECSS and 2-VCSS Problems}
\label{sec:scheme}
In this section we will show how to use our new spanner
construction to find quasi-polynomial time approximation schemes
for the 2-ECSS and the 2-VCSS problems in weighted planar graphs. We
start with the QPTAS for 2-ECSS problem.
We use a similar framework as that in the PTAS for 2-ECSSM problem
in Section~\ref{sec:2ecssm}. But instead of using the spanner
constructed as in \cite{-ADDJS93}, now we use the augmented
spanner $H^*$ as constructed in Section~\ref{sec:H*}.
We first apply Lemma \ref{lemma:separator} to $H^*$ with $k =
\Theta(\log n /\epsilon)$ to decompose $H^*$. However, different
from the PTAS for the 2-ECSSM problem, $H^*$ may not contain a
near-optimal solution of the 2-ECSS problem. Thus we cannot work
on the pieces of $H^*$ directly.
%
Fortunately, Lemma~\ref{lemma:cross} guarantees that there exists a
near-optimal solution with at most $O(k \log(1/\epsilon))$ edges
crossing the Jordan curve $J$. We guess these crossing edges by
trying all $n^{O(k \log(1/\epsilon))}$ possibilities. We add the
guessed edges to the corresponding pieces, and the vertices of
$H^*$ along $J$ together with the endpoints of the guessed edges
determine the set of portals $P$ for the new pieces. For each
possible new piece with the guessed edges, we assign weights to
the new portals such that each new piece has cost at most constant
fraction of $H^*$ and $O(k)$ portals. Then we recursively
decompose the new pieces.
As in the PTAS for the 2-ECSSM problem, for each piece we define
edge-connecti-vity types which describe how these portals may be
connected outside one of the pieces in a
$(1+\epsilon)$-approximate solution. The number of types for each
piece is $2^{O(k \log (1/\epsilon))}$, exponential in the number
of portals. Then, we use dynamic programming to solve the
subproblems as before and we commit the cycle edges to the
solution.
The approximation scheme for the 2-VCSS problem is similar, and we
only mention the differences: first, we redefine $H^*$ as remarked
at the end of Section \ref{sec:H*}, and then we need to define
vertex-connectivity types using the same techniques as in
\cite{-CGSZ04}.
The error of our final solution comes from two sources. First, we
committed the edges of the cycles that arose from the application
of the separator theorem to the solution. Since each piece in the
decomposition has weight at most constant fraction of its parent
weight, the depth of the recursive calls is $O(\log n)$. As
before, the total error per recursive level is $O((w(H^*)/k)\log
n)$, where $k=\Theta(\log n/\epsilon)$ and $w(H^*) =
O(\OPT/\epsilon)$. By an appropriate choice of the leading
constant defining $k$, this is at most $(\epsilon/2) \cdot \OPT$.
Moreover, each time a face of $H^*$ (or its pieces) is cut by a
Jordan curve, we guess $O(\log(1/\epsilon))$ crossing edges. If
we guess these edges optimally (they were edges in some original
optimal $S^*$), then by Lemma~\ref{lemma:cross} we may pay an
additive error of at most $\epsilon/2$ times the weight of these
guessed edges. Summing over the entire assembly of a possible
solution, the total of these errors is at most $(\epsilon/2) \cdot
\OPT$.
The dominating factor in the running time comes from trying all
$n^{O(k\log(1/\epsilon))}$ possibilities for the guessed edges.
The weights of the subproblems are only a constant times the
weight of their respective parents and therefore a pure recursive
approach (without dynamic programming) leads to a time bound of
$T(n) \le n^{O(k \log(1/\epsilon))} T(c\cdot n)$ ($0 0$ and let $G$ be a 2-EC (2-VC) weighted
planar graph with $n$ vertices. There is an algorithm running in
time $n^{O(\log n \cdot \log (1/\epsilon)/\epsilon)}$ that outputs
a 2-ECSS (2-VCSS) $H$ of $G$ such that $w(H) \le (1 + \epsilon)
\cdot \OPT$.
\end{theorem}
% Using subgraph counting trick (near end of
%icalp04) helps us here again. That is, the number of subgraphs of
%$G$ that can occur (without identifying their portals) is first
%bounded as $n^{O(\log n)}$. Each has at most
%$p=O(k\log(1/\epsilon))$ portals, which could occur anywhere, and
%then $2^{O(p)}$ external types to consider. So overall DP time
%bound is dominated by $n^{O(p)}$, or $n^{O((\log n)(\log
%1/\epsilon)/\epsilon)}$, as claimed.
%
%Old bounds on number of ``external types'' are insignificant
%compared to this factor.
%=======================================
\section{Extensions to the $\{1,2\}$-Connectivity Problem}
\label{sec:12extension}
In this section, we extend our results to the $\{1,
2\}$-connectivity problems in weighted planar graphs. We focus on the
algorithm for the $\{1,2\}$-ECSS problem only. The algorithm for
the $\{1,2\}$-VCSS problem can be obtained similarly.
The algorithms presented are modifications of the respective algorithms
in Sections~\ref{sec:2ecssm}~and~\ref{sec:scheme}.
First, consider the $\{1,2\}$-ECSSM problem, which is a relaxed
version of the $\{1,2\}$-ECSS problem where duplicate edges are
allowed. As in Section \ref{sec:2ecssm}, we can show that there is
a $(1+\epsilon)$-approximate $\{1,2\}$-ECSSM that uses only edges
from a light $(1+\epsilon)$-spanner $H$. So instead of $G$, we can
work on $H$ with duplicated edges.
The main difference from Section \ref{sec:2ecssm} is the dynamic
programming part. We need to redefine the connectivity types to
reflect the non-uniform connectivity requirement. For this, we can
use the connectivity type construction in \cite{-CLZ02}.
Informally, the main difference is that each time we contract a
2-connected component or path, we assign the highest connectivity
requirement among all contracted vertices to the new vertex. This
increases the number of types from $2^{O(|P|)}$ to $2^{O(2|P|)}$,
where $P$ is the set of portals in the given graph. We again
obtain a PTAS with running time $n^{O(1/\epsilon^2)}$.
Now consider the $\{1,2\}$-ECSS problem. We first find a
2-approximate solution $A$ using algorithms from \cite{-J01} (or
\cite{-F01} for $\{1,2\}$-VCSS). Then we augment $A$ into a light
spanner $H^*$ as in Section \ref{sec:H*}. Using similar arguments
as in the proof of Lemma \ref{lemma:cross}, we can show that there
is a $(1+\epsilon)$-approximate $\{1,2\}$-ECSS $S$ so that for
each picked face-edge $e$, only $O(\log(1/\epsilon))$ edges of $S$
cross $e$. Now redefine the connectivity types as above. Finally,
we use dynamic programming to solve the problem. The running time
is still dominated by the number of subproblems $n^{O(\log n \cdot
\log (1/\epsilon)/\epsilon)}$. Hence, we get a QPTAS in this case.
Our results in this section are summarized as follows.
\begin{theorem}
\label{theorem:PTAS-12-multigraphs}
Let $\epsilon > 0$ and let $G$ be a weighted planar graph
with $n$ vertices. There is an algorithm running in time
$n^{O(1/\epsilon^2)}$ that outputs a \{1,2\}-ECSSM of $G$ whose
weight is at most $(1 + \epsilon) \cdot \OPT$.
\end{theorem}
\begin{theorem}
\label{theorem:12EC-QPTAS}
Let $\epsilon > 0$ and let $G$ be a weighted planar graph
with $n$ vertices. There is an algorithm running in time
$n^{O(\log n \cdot \log (1/\epsilon)/\epsilon)}$ that outputs a
\{1,2\}-ECSS $H$ of $G$ such that $w(H) \le (1 + \epsilon) \cdot
\OPT$.
\end{theorem}
\begin{theorem}
\label{theorem:12VC-QPTAS}
Let $\epsilon > 0$, and let $G$ be a weighted planar graph
with $n$ vertices. There is an algorithm running in time
$n^{O(\log n \cdot \log (1/\epsilon)/\epsilon)}$ that outputs a
\{1,2\}-VCSS $H$ of $G$ such that $w(H) \le (1 + \epsilon) \cdot
\OPT$.
\end{theorem}
%=======================================
%\section{Conclusion}
%\label{sec:final}
%Open problems?
%=======================================================================
\begin{thebibliography}{99}
\small
\newcommand{\DCGEOM}{Discrete \& Computational Geometry}
\newcommand{\DAMATH}{Discrete Applied Mathematics}
\newcommand{\FOCS}{IEEE Symposium on Foundations of Computer Science}
\newcommand{\ICALP}{Annual International Colloquium on Automata, Languages and
Programming}
\newcommand{\IPCO}{International Integer Programming and Combinatorial
Optimization Conference}
\newcommand{\JACM}{Journal of the ACM}
\newcommand{\JALGORITHMS}{Journal of Algorithms}
\newcommand{\JGT}{Journal of Graph Theory}
\newcommand{\MATHPROGB}{Mathematical Programming B}
\newcommand{\OR}{Operations Research}
\newcommand{\SICOMP}{SIAM Journal on Computing}
\newcommand{\SIJDM}{SIAM Journal on Discrete Mathematics}
\newcommand{\SODA}{Annual ACM-SIAM Symposium on Discrete Algorithms}
\newcommand{\SoCG}{Annual ACM Symposium on Computational Geometry}
\newcommand{\STOC}{Annual ACM Symposium on Theory of Computing}
\renewcommand{\DCGEOM}{Discrete Comput. Geom.}
\renewcommand{\DAMATH}{Discrete Appl. Math.}
\renewcommand{\FOCS}{FOCS}
\renewcommand{\ICALP}{ICALP}
\renewcommand{\IPCO}{IPCO}
\renewcommand{\JALGORITHMS}{J. Algorithms}
\renewcommand{\JGT}{J.~Graph Theory}
\renewcommand{\MATHPROGB}{Math. Program. B}
\renewcommand{\OR}{Oper. Res.}
\renewcommand{\SICOMP}{SIAM J.~Comput.}
\renewcommand{\SIJDM}{SIAM J. Discrete Math.}
\renewcommand{\SODA}{SODA}
\renewcommand{\SoCG}{???????????????????????????}
\renewcommand{\STOC}{STOC}
\bibitem{-ADDJS93}
I.~Alth{\"o}fer, G.~Das, D.~Dobkin, D.~Joseph, and J.~Soares.
\newblock On sparse spanners of weighted graphs.
\newblock \emph{\DCGEOM}, 9: 81--100, 1993.
\bibitem{-AGKKW98}
S.~Arora, M.~Grigni, D.~Karger, P.~Klein, and A.~Woloszyn.
\newblock A polynomial time approximation scheme for weighted planar graph
TSP.
\newblock \emph{\SODA} 1998, pp. 33--41.
\bibitem{-BGZ04}
A.~Berger, M.~Grigni and H.~Zhao.
\newblock A well-connected separator for planar graphs.
\newblock \emph{Manuscript}, 2004.
\bibitem{-CT00}
J.~Cheriyan and R.~Thurimella.
\newblock Approximating minimum-cost {$k$}-connected spanning subgraphs
via matching.
\newblock \emph{\SICOMP}, 30(2):528-560, 2000.
\bibitem{-CVV03}
J.~Cheriyan, S.~Vempala, and A.~Vetta.
\newblock An approximation algorithm for the minimum-size
$k$-vertex connected subgraph.
\newblock \emph{\SICOMP}, 32(4):1050--1055, 2003.
\bibitem{-CGSZ04}
A.~Czumaj, M.~Grigni, P.~Sissokho, and H.~Zhao.
\newblock Approximation schemes for minimum 2-edge-connected and
biconnected subgraphs in planar graphs.
\newblock \emph{\SODA} 2004, pp. 489--498.
\bibitem{-CL99}
A.~Czumaj and A.~Lingas.
\newblock On approximability of the minimum-cost {$k$}-connected spanning
subgraph problem.
\newblock \emph{\SODA} 1999, pp. 281--290.
\bibitem{-CL00}
A.~Czumaj and A.~Lingas.
\newblock Fast approximation schemes for {Euclidean} multi-connectivity
problems.
\newblock \emph{\ICALP} 2000, pp. 856--868.
\bibitem{-CLZ02}
A.~Czumaj, A.~Lingas, and H.~Zhao
\newblock Polynomial-time approximation schemes for the Euclidean
survivable network design problem.
\newblock \emph{\ICALP} 2002, pp. 973--984.
\bibitem{-F01}
L.~Fleischer.
\newblock A $2$-approximation for minimum cost $\{0,1,2\}$ vertex
connectivity.
\newblock \emph{\IPCO} 2001, pp. 115--129.
%\bibitem{-FJW01}
%L.~Fleischer, K.~Jain, and D.~P. Williamson.
%\newblock An iterative rounding $2$-approximation algorithm for the element
% connectivity problem.
%\newblock \emph{\FOCS} 2001, pp. 339--347.
\bibitem{-G02}
H.~N. Gabow.
\newblock An ear decomposition approach to approximating the
smallest 3-edge connected spanning subgraph of a multigraph.
\newblock \emph{\SODA} 2002, pp. 84--93.
\bibitem{-G03}
H.~N. Gabow.
\newblock Better performance bounds for finding the smallest
$k$-edge connected spanning subgraph of a multigraph.
\newblock \emph{\SODA} 2003, pp. 460--469.
\begin{comment}
\bibitem{-GGW98}
H.~N. Gabow, M.~X. Goemans, and D.~P. Williamson.
\newblock An efficient approximation algorithm for the survivable network
design problem.
\newblock \emph{\MATHPROGB}, 82:13--40, 1998.
\end{comment}
\begin{comment}
\bibitem{-GM90}
M.~{Gr\"{o}tschel} and C.~L. Monma.
\newblock Integer polyhedra arising from certain network design problems with
connectivity constraints.
\newblock \emph{\SIJDM}, 3(4):502--523, 1990.
\end{comment}
\begin{comment}
\bibitem{-GMS92}
M.~{Gr\"{o}tschel}, C.~L. Monma, and M.~Stoer.
\newblock Computational results with a cutting plane algorithm for designing
communication networks with low-connectivity constraints.
\newblock \emph{\OR}, 40(2):309--330, 1992.
\end{comment}
\bibitem{-GMS95}
M.~{Gr\"{o}tschel}, C.~L. Monma, and M.~Stoer.
\newblock Design of survivable networks.
%\newblock In M.~O. Ball, T.~L. Magnanti, C.~L. Monma, and
% G.~L. Nemhauser, editors, \emph{Handbooks in Operations Research and
% Management Science}, volume 7: Network Models, chapter~10, pp. 617--672.
% North-Holland, Amsterdam, 1995.
\newblock In M.~O. Ball et al., eds., \emph{Handbooks in Operations
Research and Management Science}, vol 7: \emph{Network Models}, chapter~10,
pp. 617--672. North-Holland, Amsterdam, 1995.
\bibitem{-J01}
K.~Jain.
\newblock A factor {$2$} approximation algorithm for the
generalized {Steiner} network problem.
\newblock \emph{Combinatorica}, 21(1):39--60, 2001.
\bibitem{-JRV03}
R.~Jothi, B.~Raghavachari, and S.~Varadarajan.
\newblock A $5/4$-approximation algorithm for minimum
$2$-edge-connectivity.
\newblock \emph{\SODA} 2003, pp. 725--734.
\bibitem{-K96}
S.~Khuller.
\newblock Approximation algorithms for finding highly connected
subgraphs.
\newblock In D.~S. Hochbaum, ed., \emph{Approximation Algorithms
for $\mathcal{NP}$-Hard Problems}, %chapter~6, pages 236--265.
%PWS Publishing Company,
pp. 236--265, 1996.
\bibitem{-KV94}
S.~Khuller and U.~Vishkin.
\newblock Biconnectivity approximations and graph carvings.
\newblock \emph{\JACM}, 41(2):214--235, March 1994.
\bibitem{-KN04}
G.~Kortsarz and Z.~Nutov.
\newblock Approximation algorithm for $k$-node connected subgraphs
via critical graphs.
\newblock \emph{\STOC} 2004, pp. 138--145.
\bibitem{-K03}
P. Krysta.
\newblock Approximating minimum size {1,2}-connected networks,
\newblock \emph{\DAMATH}, 125:267--288, 2003.
\bibitem{-LNS98}
C.~Levcopoulos, G.~Narasimhan, and M.~H.~M. Smid.
\newblock Efficient algorithms for constructing fault-tolerant geometric
spanners.
\newblock \emph{\STOC} 1998, pp. 186--195.
\begin{comment}
\bibitem{-MS89}
C.~L. Monma and D.~F. Shallcross.
\newblock Methods for designing communications networks with certain
two-connected survivability constraints.
\newblock \emph{\OR}, 37(4):531--541, July 1989.
\end{comment}
\bibitem{-PS97}
M.~Penn and H.~{Shasha-Krupnik}.
\newblock Improved approximation algorithms for weighted 2- and 3-vertex
connectivity augmentation problems.
\newblock \emph{\JALGORITHMS}, 22:187--196, 1997.
\bibitem{-RS98}
S.~B. Rao and W.~D. Smith.
\newblock Approximating geometrical graphs via ``spanners'' and ``banyans''.
\newblock \emph{\STOC} 1998, pp. 540--550.
\bibitem{-BOOK-S92}
M.~Stoer.
%-\newblock \emph{Design of Survivable Networks}, volume 1531 of
% \emph{Lecture Notes in Mathematics}.
%\newblock Springer-Verlag, Berlin, 1992.
%- \emph{Lect. Notes in Math.}, Springer-Verlag, 1992.
\newblock \emph{Design of Survivable Networks}.
\newblock \emph{Lect. Notes in Math.} 1531, Springer-Verlag, 1992.
\bibitem{-VV00}
S. Vempala and A. Vetta
\newblock Factor $4/3$ approximations for minimum 2-connected
subgraphs.
\newblock \emph{APPROX} 2000, pp. 262--273.
\end{thebibliography}
\end{document}