数理解析研究所講究録1120 巻 1999 年 161-173

161

指定された全域木を含む最小 2 辺連結部分グラフを求める近似アルゴリズム
Approximating a Smallest
Subgraph
Containing a Specified Spanning bee$2-\mathrm{E}\mathrm{d}\mathrm{g}\mathrm{e}-\mathrm{c}_{0}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{C}\mathrm{t}\mathrm{e}\mathrm{d}$永持仁Hiroshi NAGAMOCHI京都大学大学院情報学研究科〒 606-8501 京都市左京区吉田本町

naga@kuamp.kyoto-u.ac. jp

Abstract:

Given a graph $G=(V, E)$ and a tree $T=(V, F)$ with $E\cap F=\emptyset$ such that
$G+T=$ (V, $F\cup E$ ) is 2-edge-connected, we consider the problem of finding a smallest
2-edge-connected spanning subgraph (V, $F\cup E’$ ) of $G+T$ containing . The problem,
which is known to be-hard, admits a 2-approximation algorithm. However, obtaining
a factor better than 2 for this problem has been one of the main open problems in the graphaugmentation problem. In this paper, we show that the problem is $(1.92+\epsilon)$ -approximable
in $O(n^{1/2}m+n^{2})$ time for any constant, where $n=|V|$ and $m=|E\cup F|$ .
$T$$\mathrm{N}\mathrm{P}$$\epsilon>0$

Key words: approximation algorithm, edge-connectivity, spanning tree, spanning subgraph,graph augmentation

1

Introduction$H_{0}$

Given a 2-edge-connected undirected multigraph $H=(V, E)$ with vertices and $m$ edges
and a spanning subgraph $H_{0}=(V, E_{0})$ , we consider the problem of finding a smallest 2-edgeconnected spanning subgraph $H_{1}=(V, E_{1})$ that
contains. Note that the problem can be regarded as a graph augmentation problem of finding a smallest subset $E’\subseteq E-E_{0}$ of edges toaugment
to a 2-edge-connected graph $H_{1}=$(V, $E_{1}=E_{0}\cup E’$ ). The problem is shown to be-hard [3] even if. In the case of,
the problem, which is called the minimum 2-edgeconnected spanning subgraph problem (2-ECSS),
has been extensively studied and several approximation algorithms are known [1, 2, 7]. The currently best approximation ratio for 2-ECSS isdue to Cheriyan et al. [1]. On the other hand, if
is connected,
can be assumed to be a span$H$ning tree of
without loss of generality (since$n$$H_{0}$$H_{0}$$E_{0}=\emptyset$$\mathrm{N}\mathrm{P}$$E_{0}=\emptyset$$\frac{17}{12}$$H_{0}$$H_{0}$

every 2-edge-connected component incan becontracted into a single vertex without losing theproperty of the problem). Let us call the problem with a tree
the minimum 2-edge-connected
subgraph problem containing a spanning tree (2ECST), which is shown to be-hard by Frederickson and J. J\’aJ\’a [4] (even if the height of a spanning treeis 2 and every edge in $E-E_{0}$ connects
two leaf vertices of). The 2-ECST has an application to the problem of realizing rectangular
dual graphs in floor-planning [10]. In the special case of $H$ being a complete graph, 2-ECST is
the problem of augmenting a tree
to a 2-edgeconnected graph by adding a minimum number of
new edges, for which Eswaran and Tarjan [3] presented a linear time algorithm (which creates nomultiple edges). If $H$ is a general graph, we are
permitted to add toonly edges from $E-E_{0}$ .
For general 2-ECST, there is a 2-approximation
algorithm $[4, 6]$ , which relays on the minimum$H_{0}$$\mathrm{N}\mathrm{P}$$H_{0}$$H_{0}$$H_{0}$$H_{0}$

162
branching algorithm. In this paper, we present a$(1.92+\epsilon)$ -approximation algorithm for 2-ECST,
is an arbitrary constant. Our algowhererithm is based on the maximum matching algorithm and a certain decomposition of a tree. Its
running time is $O(n^{1/2}m+n^{2})$ , where $n=|V|$and $m=|E|$ .
$\epsilon>0$

among vertices in on . The parent of a nonroot vertex is denoted by $p(u)$ . For a vertex,$u\in V$ , let $Ch(u)$ denote the set of children of
and $D(u)$ denote the set of all descendents of(including ). For two vertices $v\in V$ , we saythat is lower than (or is higher than ) if
) if$u\in D(v)-v$ . We write $v\prec u$ (resp.,$u\in D(v)-v$ (resp., $u\in D(v)$ ). For two vertices
and with $u\in D(v)$ or $v\in D(u),$ $\min(u, v)$ (resp.,$\max(u, v))$ denotes the higher (resp., lower) vertex
in $\{u, v\}$ if $u\neq v$ (or any of and if $u=v$ ). For
an edge $e=(u, v)\in E$ , we denote by $lca(e)$ theleast (lowest) common ancestor of end vertices
and in the rooted tree . For a vertex set$V,$ $H\dot{i}gh(x)$ is defined to be the subset of $Ec(X)$such that, for any $e\in E_{G}(X)-H\dot{i}gh(x)$ , there isan $e’\in H_{i}gh(X)$ with $lca(e’)\prec lca(e)$ and for any$e_{2}\in H_{\dot{i}}gh(X)$ , neither $lca(e_{1})\prec lca(e_{2})$twonor $lCa(e_{2})\prec lca(e_{1})$ (thus $H_{i}gh(X)$ contains
those edges with the highest $lca(e))$ .
The subgraph $T[D(u)]$ of induced by $D(u)$ iscalled the subtree at (which is connected). A
vertex is called a leaf vertex if has no child,and is called a $ff_{i}nge$ vertex if all the childrenof are leaf vertices. For a vertex $u\in V$ , let
LEAF $(u)$ (resp., FRINGE $(u)$ ) denote the set of
all leaf vertices (resp., fringe vertices) in the subtree $T[D(u)]$ . An edge $f=(u, v)\in F$ with $u\prec v$
is called a leaf edge (resp., fringe edge) of if isa leaf vertex (resp., a fringe vertex). The subtree
is called a leaf tree if is a$T[D(u)]$ at a vertex
$T$

$V$

$u$

$u$

$u$

$u,$

$u$

$u$

$u$

$v$

$v$

$v\preceq u$

$u$

2

$v$

Definitions

may be simply written as
A singleton set
implies proper inclusion while, andor $”=$ ”. For an undirected graphmeans$H=(V, E)$ and an edge set $E’$ , we denote by$H+E’$ (resp., $H-E’$ ) the graph obtained from
$E’$ . The$H$ by adding (resp., removing) edges invertex set (resp., edge set) of a graph $H$ may bedenoted by $V(H)$ (resp., $E(H)$ ). For a subset, let denote $V-X$ , and $H-X$ means thegraph obtained from $H$ by removing the vertices
in $X$ together with the incident edges. A maximal
2-edge-connected subgraph $H[X]$ of $H$ induced
by a subset $X\subseteq V$ is called a 2-edge-connectedcomponent.
Let $G=(V, E)$ be an undirected graph, and$T=(V, F)$ be a tree on the same vertex set ,where $E\cap F=\emptyset$ is assumed, but there possibly
exits a pair of edges $e\in E$ and $f\in F$ such thatand have the same end vertices. For a subset$V(E’)$ denotes the set of end vertices ofedges in $E’$ . For a subset $X\subset V,$ $E_{G}(X)$ denotes
the set of edges in $E$ connecting a vertex in $X$
and a vertex in $V-X$ . In particular, $E_{G}(u)$ is theset of edges in $E$ which are incident to a vertex$u\in V$ . For two vertices $u,$ $v\in V$ , let $P_{T}(u,v)$
denote the path connecting and in . We
say that an edge $e=(u, v)\in E$ covers an edge
, and that an edge set$f\in F$ if $P\tau(u, v)$ contains
if each edge incovers an edge set$E’$$F’$ is covered by an edge in. Clearly, $T+E’$ is
if and only
2-edge-connected for a subset$\{x\}$$”\subseteq"$$”\subset"$$x$$”\subset"$$\overline{X}$$X\subseteq V$

$V$

$e$

$f$

$E’\subseteq E,$

$u$

$v$

$F^{l}\subseteq F$$E’\subseteq E$

if $E’$ covers $F$ .
We choose an arbitrary vertex $r\in V$ as theroot of , which defines a parent-child relation
$T$

$v$

$u$

$T$

$v$

$X\subseteq$$e_{1},$

$e$

$T$

$u$

$u$

$u$

$u$

$v$

$v$

$u$

$u$

fringe vertex.
We call a subtree $T[D(v)]l$ -closed in if has. Clearly,
no edge between LEAF $(v)$ and$T=T[D(r)]$ is l-closed.
$G$

$G$

$\overline{D(v)}$

$T$

$f$

$E^{l}\subseteq E$$u$Decomposing the problem

3

In this section, we describe how a given instance$(T=(V, F),$ $G=(V, E))$ of the 2-ECST problem can be decomposed into smaller problem in, we define
stances. For a subset$F’\subseteq F$$\bullet$as the size of the smallest set
that covers $F’$ (where $E’$ does not necessarily$\beta(F’)$$E’\subseteq E$

163$\bullet$cover edges in $F-F’$ ),4

as the set of all edges in $E$ that coverat least one edge in ,Let
and $F_{fringe}$ be respectively the sets ofleaf edges and fringe edges in $T[D(v)]$ . In this section, we introduce some lower bounds on
and.

$E\langle^{p^{r}}\rangle$$F^{l}$

as the set of all edges in $F$ covered by(where trivially).

$\overline{F’}$$\bullet$$F’\subseteq\overline{F’}$$E\langle F’\rangle$(For example, if we consider the setof allleaf edges in an -closed subtree $T[D(v)]$ , then anyedge $e=(u, u’)\in E\langle p_{laf}e\rangle$ satisfies$D(v)$ , and hence
is contained in $T[D(v)].)$
Assume that there are subsets$F$ suchthat$F_{leaf}$$l$$\{u, u^{l}\}\subseteq$$\overline{F_{leaf}}$$F_{1},$ $F_{2},$$E(F_{i})\cap E(F_{j}\rangle=\emptyset,$$F_{k}\subseteq$$\ldots,$

Lower bounds$F_{l\epsilon af}$$\beta(F_{lea}f)$$\beta(F_{lea}f\cup F_{f^{ri}})nge$

LEMMA 4.1 (lower bound) Let $G=(V, E)$ be
a graph and $T=(V, F)$ be a tree rooted at with
. For a non-leaf vertex in , let
be the set of all leaf edges in the subtree $T[D(v)]$ ,and letbe the set of all edges $e=(u, u’)\in E$
with $u’\in LEAF(v)$ . Then$r$

$E\cap F=\emptyset$

$v$

$T$

$F_{leaf}$$E_{leaf}$$u,$$1\leq\dot{i}<j\leq k$(hence). Since there is no edge $e\in E$
that can cover two edges from distinct
and ,it holds$\beta(F_{lf}ea)\geq|LEAp(v)|-|M^{*}|$,$F_{i}\cap F_{j}=\emptyset$$F_{i}$$F_{j}$$\beta(F)\geq\beta(F_{1})+\beta(F_{2})+\cdots+\beta(F_{k})$.

Suppose that we are able to compute an edge set
that covers
and satisfies
for some constant . Then $E^{apx}=E_{1}^{apx}\cup$
becomes a -approximation solution tothe original problem $(T, G)$ , provided thatcovers the entire $F$ .
Let us consider a procedure for finding suchand. With initial setting $F’:=F,$ $E’:=E$and, we repeat the following procedure until
all edges in $F$ are covered.
$E_{i}^{apx}\subseteq E$$|E_{i}^{apx}|\leq$$F_{i}$$c\beta(F_{i})$$c$$.\cup E_{k}^{apx}$$c$$E^{apx}$$F_{i}$$E_{i}^{apx}$$\dot{i}:=1$

Choose a subset, and computea subsetthat covers
andsatisfies. Let
denote the set of all edges covered by$F_{i}\subset F’$$E_{i}^{a\mathrm{p}x}\subseteq E’$$|E_{i}^{apx}|\leq c\beta(F_{i})$$E_{i}^{a\mathrm{p}x}$$\overline{F_{i}}$$F_{i}’’(\supseteq\overline{F_{i}})$.

Let $F^{l}:=F’-p_{i}\prime l;E’:=E’-E_{i}apx;i:=$. (To remove
from $F’$ effectively,
we contract all vertices in
into asingle vertex if the graph $(V(F_{i}’;), F’’i)$ isconnected.)$\dot{i}+1$

whereis a maximum matching in the$(v),$
graph (LEAF).
$M^{*}\subseteq E$$E\iota_{ea}f$

Proof: Omitted.

$\square$Let us derive a stronger lower bound on. For this, we introduce primeedges of type-l and type-2. For a leaf tree $T[D(u)]$with exactly two leaf vertices $\{w, w^{l}\}=Ch(u)$ ,we call an edge $g=(w, w’)\in E$ a prime edge oftype-l. Let $f=(v^{ll}, v)’\in F(v’’\prec v’)$ be an edge
insuch that FRINGE $(v^{l})-v’$ contains ex’
actly one fringe vertex , and LEAF $(v)$contains
exactly three leaf vertices
and(where$\{u_{1}, u_{2}\}=Ch(v)$ and $u_{3}\in Ch(v’)$ are assumed
without loss of generality). We call edges
andprime edges of type-2 if$\beta(\mathrm{f}\mathrm{i}eaf\cup F_{fe})ring$

$T$

$v$

$u_{1},$ $u_{2}$$u_{3}$$(u_{3}, u_{1})$$(u_{3}, u_{2})$for $\dot{i}=1,2,$
and $w\in D(v^{l})-u_{3}$ for all$\{(u_{1}, u_{2}), (u_{i}, u_{3})\}\subseteq E_{G}(u_{i})$$(u_{i}, w)\in E_{G}(u_{i})$(1).

$F_{i}’’$$V(F_{i}^{;\prime})$$\square$

Importantly,
implies
for any choice ofin the-th iteration.
$F’$
Ifbecomes empty after the -th iteration,
covers $F$ and is a c-approximation
solution.
$\overline{F_{i}}\subseteq F_{i}^{ll}$$F_{i+1}$$E(F_{i}\rangle\cap E\langle F_{i1}+\rangle=\emptyset$$(\dot{i}+1)$$i^{*}$$Eapx_{\cup}\ldots E1i*p\cup xa$

See Fig. 1 (whereis a prime edge of type-lby definition). In this case, the edge $f=(v^{\prime l},v’)\in$$F$ iscalled a pseudo-fringe edge, and the vertices
in $D(v’)-u_{3}-D(v)$ are called pseudo-fringe vertices. We denote by PFRINGE $(u)$ the set offringe and. vertices in $T[D(u)]$ .
$(u_{1}, u_{2})$$\mathrm{P}^{\mathrm{S}\mathrm{e}\mathrm{u}\mathrm{d}-\mathrm{f}\mathrm{r}}\mathrm{O}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{e}$LEMMA 4.2 (lower bound) Let $G=(V, E)$ be
a graph and $T=(V, F)$ be a tree rooted at with
$r$

164

in $T[D(v)]$ can be found by the next procedure(P1).

in the(P1) Compute a maximum matching, and choose an arbigraph ( $Ch(v),$trary edge $e_{w}\in E_{G}(w)$ for each unmatchedvertex $w\in ch(v)-V(M^{*})$ (where $E_{G}(w)\neq$by the 2-edge-connectivity of $T+E$ ). Re$M^{*}$$E\iota eaf^{)}$$\emptyset$

tain $E_{v}^{opt}=M^{*}\cup\{e_{w}|w\in ch(v)-V(M^{*})\}$
as part of the solution to cover the current. Contract all vertices in $Ch(v)\cup\{v\}$ into asingle vertex both in and , and delete
any resulting self-loops (where the vertex
becomes a new leaf vertex in the resultingtree).
$T$$v’$: Definition of prime edges of type-2, andpseudo-fringe edges and vertices.

. For a vertex $v\in V-LE\mathrm{A}F(r)$-be the set of all edges$e=(u, u’)\in E$ with $u,$ $u’\in LEAF(v)$ , Eprime
be the set of prime edges of type-l and type-2 in$E_{leaf},$
be the set of leaf edges in $T[D(v)]$ ,be the set of fringe or pseudo-fringe
andedges in $T[D(v)]$ . Then for’

FRINGE $(r)$ , let$E_{leaf}$$F_{leaf}$$F_{f^{ri}nge}$$F_{v}=\mathrm{f}\mathrm{i}eaf\cup F_{frine}\mathit{9}$$\beta(F_{v})\geq\frac{2}{3}|LEAF(v)|-\frac{1}{3}|M*|$

Obviously,$E_{v}^{opt}$

covers$F_{leaf}$, and satisfies$|E_{v}^{opt}|=$$|M^{*}|+|ch(v)|-2|M*|=|LEAF(v)|-|M^{*}|$ . By

Lemma 4.1, $|E_{v}^{opt}|=\beta(F_{le}af)$ is the minimum.
among all subsets of $E$ that cover$\square$$F_{leaf}$

For a fringe vertex , let $u\in Ch(v)$ . Vertex
is called isolated if is not adjacent via edges in$E_{G}(u)$ to any sibling (i.e., other child) of. Note. Vertex is calledthat is isolated; we must use the unique edge
$E_{G}(u)$to cover the leaf edge $f=(v, u)$ . Forina nontrivial , let $E_{G}(u)=\{e_{1}=(u, v_{1}),$ $e_{2}=$$(u, v_{2}),$$e_{p}=(u, v_{p})\}$ , where $p=|Ec(u)|\geq 2$ .
An edge $e_{i}=(u, v_{i})$ with $v_{i}=v$ is called redundant if $E_{G}(u)$ contains some $e_{j}=(u, v_{j})$ with. If all edges in $E_{G}(u)$ are multiple edges of$(v, u)$ , then we choose an arbitrary edge (say)$E_{G}(u)$$i=2,$ $\ldots,p$and call the other edges
inour alsimple,
originally
redundant. (Even if isgorithm will repeat contracting some vertices andmay produce multiple edges in the resulting $G.$ )It is not difficult to see that there is an optimal
that covers $F$ without using any
subsetredundant edge.
$u$

$v$

$u$

$v$

$\mathrm{i}\mathrm{f}|Ch(v)|=1$

$u$

,

$G$

$v’$

$\mathrm{B}1$$E\cap F=\emptyset$

$T$

$u$

$tr\dot{i}v\dot{i}al\mathrm{i}\mathrm{f}|Ec(u)|=1$

is a maximum matching in thewheregraph (LEAF $(v),$ $Eleaf-Eprime$ ).
$M^{*}\subseteq E$$u$$\ldots,$

Proof: Omitted.

$\square$has
We call a subtree $T[D(v)]lf$ -closed if
no edge between LEAF $(u)\cup PFRINcE(u)$ and. Clearly, $T=T[D(r)]$ is $lf$ -closed. A
subtree $T[D(v)]$ is called minimally $lf$ -closed if$T[D(v)]$ is $lf$ -closed and there is no proper subtree $T[D(u)]$ of $T[D(v)]$ which is $lf$ -closed.
$G$$\overline{D(u)}$5Some reducible cases

In this section, we show four cases where we canreduce the size of a given instance $(T, G)$ without
loss of generality.
Case-l. There is an -closed leaf tree $T[D(v)]$ :. In this case, a smallest set
Now
of all leaf edges
that covers the set$l$$\overline{F_{leaf}}=F_{leaf}$$E_{v}^{opt}\subseteq E$$F_{leaf}$$v_{j}\neq v$$e_{1}$$e_{i},$$G$$E^{opt}\subseteq E$

Case-2. There is a leaf tree $T[D(v)]$ such that
$T[D(v)]$ is not -closed and there is an isolated
leaf vertex $u\in Ch(v)$ (this includes the case of$|Ch(v)|=1)$ : There is the parent $v’=p(v)$ of(since is not the root by the
$l$

$v$

$v$

$\mathrm{n}\mathrm{o}\mathrm{n}- l- \mathrm{c}1_{0}\mathrm{S}\mathrm{e}\mathrm{d}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s}$165

of $T[D(v)])$ . Let
denote the set of all isolated$Ch(v)$
vertices in.
For each non-trivial leaf vertex(if any),
we first remove all redundant edges in $E_{G}(u)$ from
. For each trivial leaf vertex $u’\in I_{v}$ such that
$E_{G}(u’)=\{(u’, v)\}$ (if any), we retain the edge$(u’, v)$ as part of the solution to cover the original
and contractand into a vertex both inand . Now if there remains an isolated vertex$u”\in I_{v}$ , then any edge in $E$
covering the leafedge $f=(v, u”)$ also covers the fringe edge $f’=$;$(v’, v)$ of , because $E_{G}(u)’$ contains no redundantedge. Thus $\beta(F)=\beta(F-f’)$ . For this reason,
we contract the end vertices of the fringe edge$f’=(v^{l}, v)$ into a single vertex both inand ,and delete any resulting self-loops. The procedurein Case-2 is described as follows.
$I_{v}$$u\in I_{v}$

$G$

$T$

$u’$

$T$

$v$

$G$

$v$

$T$

$G$

$\{u_{1}, u_{2}, u3\}$. Consider an arbitrary subsetthat covers all edges in . Suppose that $E’$ contains no edge between $Ch(v)$ and. That is,
all leaf edges in $T[D(v)]$ are covered by (at least)
two edges $e_{1}=(u_{i}, u_{j}),$ $e_{2}=(u_{j}, u_{h})\in E^{l}$ . Since$T[D(v)]$ is not -closed, $E$ contains an edge
between a vertex $u\in Ch(v)$ and. If there
is such an edge $e_{0}=(w, u_{i})$ (resp., $e_{0}=(w,$),
then we easily see that $\tilde{E}=(E^{l}-e_{1})\cup\{e_{0}\}$(resp., $\tilde{E}=(E’-e2)\cup\{e_{0}\}$ ) covers all edges in. If all such edges are incident to , then by$|E_{G}(ui)|\geq 2,$ $E$ contains an edge $e_{3}=(u_{i}, u_{h})$.
$\tilde{E}=(E’-\{e_{1},e_{2}\})\cup\{e_{0},e_{3}\}$In this case,coversall edges in . In any case, we can assume that atleast one edge between $Ch(v)$ andis used in. For this reason, we contract the end verticesof the fringe edge $f’=(v’, v)$ into a single vertex
both inand , and delete any resulting selfloops. The procedure in Case-3 is summarized asfollows.
$T$$\overline{D(v)}$$l$$e_{0}$$w\in\overline{D(v)}$$u_{h})$$T$$e_{0}$

move all redundant edges in $E_{G}(u)$ from .
For each trivial leaf vertex
such that$E_{G}(u’)=\{(u’, v)\}$ , retain the edge $(u’, v)\in$$E_{G}(u’)$ and contractand into . If there
remains an isolated vertex in , then contract $v’=p(v)$ and into a vertex.
$G$$u_{j}$$T$$\overline{D(v)}$$E^{l}$$T$(P2) For each non-trivial leaf vertex $u\in I_{v}$ , re-$E’\subseteq E$$G$$u’\in I_{v}$

$u’$

$v$

$v$

$I_{v}$$v$$\square$Case-3. There is a leaf tree $T[D(v)]$ such thatis not -closed, $|Ch(v)|=3$ holds, and$Ch(v)$ contains no isolated vertex: We first remove all redundant edges incident to $u\in Ch(v)$ .
If there is a trivial vertex$Ch(v)$ (i.e.,$|E_{G}(u)|=1)$ , then choose such a vertex . Now
the edge $e\in E_{G}(u)$ connects
and a sibling$u’\in Ch(v)$ of(
is not isolated). To cover$f=(v,u)$the leaf edge
, the edge $e=(u, u’)$ must
be used. Therefore, we retain the edge $(u, u’)$ as
part of the solution, and contract $\{u, u’, v\}$ intoa single vertex both in and , deleting any
resulting self-loops.
On the other hand, if $|Ec(u)|\geq 2$ holds for all$u\in Ch(v)$ , then we claim that the fringe edge$f’=(v’, v)\in F$ , where $v’=p(v)$ , can be contracted without loss of generality. Let $Ch(v)=$$T[D(v)]$

$l$

$u$

$\in$

$u$

$u$

$\grave{\mathrm{s}}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{e}u$

$u$

$v$

$T$

$G$

(P3) Remove all redundant edges incident to $u\in$$Ch(v)$ . If there is a trivial vertex $u\in Ch(v)$ ,retain the edge $(u, u^{l})\in E_{G}(u)$ and contract
into a single vertex . Otherwise,
contract the fringe edge $f^{l}=(v’, v)$ .
$\{u, u^{l}, v\}$$v$

Given a solution $E’$ to the instance $(T’, G’)$ resulting from contracting $f’$ , we can modify $E’$ (ifnecessary) so that $f’$ is also covered in the original
instance $(T, G)$ without increasing the size of $E’$ .
$\square$’Case-4. There is an edge $f’=(vv)\prime\prime,$insuch that FRINGE $(v’)-v^{;}$ contains
exactly one fringe vertex(where its leaf tree
$T[D(v)]$ is not -closed and no child in $Ch(v)$ isisolated), LEAF $(v’)$ contains exactly three leaf
verticesand(where $\{u_{1}, u_{2}\}\cdot=Ch(v)$and $u_{3}\in Ch(v’)$ are assumed without loss of genera..lity), and there is an edge $(u_{3}, u_{2})\in E$ , but $f’$is not a pseudo-fringe edge. See Fig. 2.
Since
is assumed to be a non-isolated vertex, it has edge $(u_{1}, u_{2})\in E_{G}(u_{1})$ . We showthat if no edge in
is incident to any vertex, then we can retainas$T$$(v^{\mu}\prec v’)$

$v$

$l$

$u_{1},$ $u_{2}$$u_{3}$$u_{1}$$E_{G}(u_{1})$$\overline{D(v)\prime}\cup\{u_{3}\}$$(u_{1}, u_{2})$166
and , deleting any resulting
vertex both inself-loops.
The remaining case is that $(u_{1}, u_{3})\in E_{G}(u_{1})$ .
Since $f’$ is not a pseudo-fringe edge (i.e., (1) does
not hold), there is an edge $(u_{2}, w^{l})\in E_{G}(u_{2})$ withand in this case we can also contract $f’$by applying the above argument exchanging theand . The procedure in Case-4 isroles ofsummarized as follows.
$G$

$T$

$w’\in\overline{D(v’)}$$u_{1}$$\mathbb{E}2$: Illustration for a subtree $T[D(v)’]$ in Case-4.

be apart of the solution to cover $T$ . Let
smallest edge set $E^{*}\subseteq E$ covering $F$ , and ascontains an edge $(u_{1}, w)\in E$ withsume that. To$w\in D(v’)-u_{3}$ , but do not containhas some
cover the leaf edge $(v, u_{2})\in F,$$\in
E_{G}(u_{2})-(u_{1},u_{2})$. It
edge $e^{l}=(u_{2}, w’)$is clear that $(E^{*}-(u_{1}, w))\cup\{(u_{1}, u_{2})\}$ (resp.,$(E^{*}-\{(u_{1}, w), e\}/)\cup\{(u_{1,2}u), (u_{2}, u_{3})\})$ still covers $F$ if $w’\not\in D(v^{l})-v’$ (resp., if $w^{l}\in D(v)’-v’$ ).
Thus, removal edges in $E_{G}(u_{1})-(u_{1}, u_{2})$ from $E$, and we can contract $D(v)$never increases
as partinto a single vertex after retainingof the solution to cover $T$ .

$u_{2}$(P4) If no edge in $E_{G}(u_{1})$ is incident to any vertex
as part of, then retain
the solution to cover $T$ and contract $D(v)$into a single vertex. Otherwise contract edge$(u_{1}, u_{2})$$\overline{D(v’)}\cup\{u_{3}\}$$f’=(v”’, v)$ .

$E^{*}$$E^{*}$$(u_{1}, u_{2})$$E^{*}$

to the instance $(T’, G^{;})$ reGiven a solution(ifsulting from contracting $f’$ , we can modify$f’$
origiis also covered in thenecessary) so that$(T,
G)$
without increasing the size of
nal instance$E^{**}$$E^{**}$$E^{**}$.
$\square$$\beta(F)$$(u_{1}, u_{2})$contains an edge $(u_{1}, w)$
Assume that
. For the edge
such that $w=u_{3}$ or$f’=(v^{l\prime}, v’)$ , we next claim that $\beta(F)=\beta(F-fJ)$holds if there is an edge $(u_{1}, w)\in E_{G}(u_{1})$ with. To see this, consider the instance$(T’, G’)$ obtained from the current $(T, G)$ by coninto a single vertex, and let
tracting $v”$ and$E^{**}\subseteq E$
be a smallest edge set covering the(i.e., $F-f’$ ). Assume thatedges in(otherwise we are done).
in
does not coverThus, the edges in $T[D(v)’]$ are covered by twoby the minimality of) inedges (sayand an edge
. For the edge $e_{3}=(u_{3},$, we see$e_{4}=(u_{1}, w)\in E_{G}(u_{1})$ withthat $(E^{**}-\{e_{1}, e_{2}\})\cup\{e_{3}, e_{4}\}$ covers all edges in. Therefore, $\beta(F)=\beta(F-f’)$ and we contract
into a single
the end vertices of edge
$E_{G}(u_{1})$$w\in\overline{D(v’)}$$w\in\overline{D(v^{l})}$$v’$$E^{**}$$T^{l}$$f^{l}$$e_{1},$$|E^{**}|$

3: Definition of lower-, middle- and upper-parts of a chain $P\tau(u_{1}, uk)$ .

$e_{2}$$T$

6

Structure of $T+E$$E^{**}$$u_{2^{)},}$$w\in\overline{D(v’)}$$T$$f’=(v^{\prime\prime/}, v)$

A leaf vertex is called a thorn vertex if its parent is not a fringe vertex, and a vertex is calleda branch vertex if $u=r$ or $Ch(u)$ contains atleast two non-leaf vertices. Let THORN $(v)$ denote the set of all thorn vertices in $T[D(v)]$ . Note
$u$

167

that the number of branch vertices is at most$|FRINGE(v)|$ . For each branch vertex , a path
$P_{T}(u, u)/$ with $u’\in D(u)$ is called a chain ofif
is a fringe or branch vertex and $P_{T}(u, ul)-\{u, u’\}$contains no fringe or branch vertex. (Thus any
in a chain has exactly one noninternal vertex
The number of chains inleaf vertex in$T[D(v)]$is at most $2|FRINGE(v)|-1$ .
a tree$u$$u^{l}$

$u$

than
and
incident towhere$x_{1}$$x_{2}$(some other edge $e\in E$ may be
or $P\tau(p(x_{1}),p(x2)))$ . See Fig. 4,
are not swing edges.

$x_{1},$ $x_{2}$$g_{1},$ $g_{2},g_{3}$$u^{n}$$Ch(u^{\prime l}).)$In what follows, we assume that $T+E$ is 2-edgeconnected and $T[D(v)]$ is a minimally 1 -closed
subtree of . In this case, is the root of $T[D(v)]$and is treated as a branch vertex. Consider aof $T[D(v)]$ , wherechain$V(P_{T}(u_{1},u_{k}))=\{u_{1},\ldots, u_{k}\}$(see Fig. 3).
forsuch
be the lowest vertex inLet
are covered bythat all the edges ina single edge $(t, t’)\in E$ (where $a\geq 2$ since
exists by the 2-edge-connectivity ofsuch$T+E)$ , and call the subpath $P_{T}(u_{1a}, u)$ the upper. The edge $(t, t’)\in E$
part of chain
is called the upper-edge of thethat defineschain, where $lca((t, t’))\preceq u_{1}\preceq t$ holds andmay belong to $D(u_{k})$ . Similarly the highest versuch that the edges intex
are covered by a single edge $(S, S^{/})\in$$E$ with $s\in LEAF(u_{k})\cup PFRINGE(u_{k})-u_{k}$(where $u_{b}=u_{k}$ if no such $(S,$ $S’)$ exists), and callthe subpath $P_{T}(u_{b}, uk)$ the lower-part of chain$P_{T}(u_{1}, uk)$ .
If $u_{b}\neq u_{k}$ , the edge $(S, S^{J})\in E$
that covers the lower-part is called the lower-edgeof chain $P_{T}(u_{1}, uk)$ , where possibly belongs to, then there must be a thorn. If$z_{0}\in
D(u_{b})-(D(u_{k})\cup\{u_{b}\})$
such that anvertex$e\inE$connects
and a vertex inedge(otherwise $T[D(u_{b})]$ would be $lf$ -closed). We saythat a subpath $P_{T}(u_{i}, uj)$ has a thorn vertex if
the parent $p(w)$ is contained in $P_{T}(u_{i}, uj)$ .

$\backslash \backslash$$4\wedge \mathrm{f})\mathrm{p}\mathrm{f}\mathrm{i}\Pi i\mathrm{f},\mathrm{i}\mathrm{f})\mathfrak{n}$of.qwin$\sigma\epsilon\wedge\sigma P..\mathrm{S}\Pi_{-}$

$f$

$T$

$v$

$P_{T}(u_{1}, u_{k})$$u_{1}\prec\cdots\prec u_{k}$$\{u_{1}, \ldots, u_{k}\}$$u_{a}$$P_{T}(u_{1}, u_{a})$$\backslash \backslash$

5: Definition of binding edges$\epsilon!\mathrm{d}\sigma \mathrm{e}$$a$$(t, t^{l})$in the ca..qe of$e_{\mathit{9}}$of a swing$(\mathrm{R}1)_{-}$$P_{T}(u_{1}, u_{k})$$u_{a}$$t$$u_{b}$$\in$$\{u_{1}, .

‘.

, u_{k}\}$$P_{T}(u_{b}, u_{k})$: Definition of binding edges
edge in the case of (B2).
$\mathrm{H}6$$e_{\mathit{9}}$of a swing

$g$

$s’$

$\overline{D(u_{1})}$$u_{1}\prec u_{b}$$z_{0}$$\overline{D(u_{b})}$$w$

Consider an edge $g–(X_{1}, X_{2})\in E$ such thatboth parents $p(x_{1})$ and $p(x_{2})$ belong to the same
chain $P_{T}(u_{1}, u_{k});p(x_{1})\preceq p(x_{2})$ is assumed without loss of generality. In this case, we denote theparents $p(x_{1})$ and $p(x_{2})$ by up $(g)$ and $dwn(g)$ , respectively. Such edge is called a swing edge ifpath $P\tau(p(x1),p(X_{2}))$ has no thorn vertex other$g$$\backslash \backslash 7$$g$: Definition of a succeeding tree of a solo edge.

,
Ifthen the sub$P\tau(u_{a}+1,ub-1)$
is called the middle-part ofpath$P_{T}(u_{1},
uk)$
chain
. In this case, for a swing edge
$g=(x_{1}, x_{2})\in E$ with $u_{a+1}\preceq up(g)\preceq dwn(g)\vee\preceq$, we call an edge $e_{g}=(w,\backslash y)\in E$ a bindingedge of if
satisfies one of the following (B1)and (B2).
$\preceq$$u_{a+1}$$u_{b-1}$$g$$e_{g}$$u_{b-1}$

168(B1) $w,$ $y\in THORN(v)$ and up $(e_{g})\prec up(g)\preceq$$dwn(g)\prec dwn(e_{g})$ (see Fig. 5).

has an edge
(A2) Every fringe vertex$\{w,w’\}\subseteq Ch(u)$ .
$(w,w’)\in E$ such that(B2) $\{w\}=\{w, y\}\cap THORN(v),$ $p(w)\prec up(g)\preceq$
and path $P_{T}(p(w), \max(dwn(g),y))$ has a
THORN $(v)-\{X_{1,2}X, w\}-$thorn vertex$D(u_{k})$ , where possibly $y\in D(u_{k})$ (see Fig. 6).

In this section, we assume that the following
condition holds in a given minimally $lf$ -closed tree$y$$z_{g}\in$

Notice that for any binding edge $e_{g}=(w, y)$ , itmust hold $p(w)\in D(u_{1})-u_{1}$ in cases (B1) andin case (B1) by the choice of(B2) andand .
A swing edge $g\in E$ is called a solo edge if$y\not\in D(u_{k})$$u$$T[D(v)]$

$e$

$=$

.

(A3) For any solo edges $g\in E$ on the middlepart of a chain in $T[D(v)]$ , its succeeding tree
$T[D(v)g]$ has at most five leaf vertices (i.e.,$|LEAF(v_{g})|\leq 5)$.

$u_{b}$$u_{a}$(B3) $u_{a+1}\preceq up(g)\preceq dwn(g)\preceq u_{b-1}$ , andno binding edge in (B1) or (B2).

$g$

has

$t_{\min}$$t_{\min}$$u_{b}$$z_{0}.$$v_{g}\prec t_{\min}$$g$$v_{g}$$g$Covering minimally $lf$ -closed
subtrees7

Let $T[D(v)]$ be a minimally $lf$ -closed subtree
in (where we can assume that is not a fringevertex in $T$ by Case-l). Such a $T[D(u)]$ always
exits, since $T=T[D(r)]$ is $lf$ -closed. In this section, we consider how to choose edges from $E$ tocover all edges in the $T[D(v)]$ .
$T$

$v$

$g,$

For a solo edge $g=(x_{1}, x_{2})\in E$ defined on the
chain $P_{T}(u_{1}, uk)$ , we define the succeeding tree
be the highest vertex inof as follows. Let$P\tau(dwn(g), uk)-\{dwn(g), uk\}$ such that there is athorn vertex $z\in THoRN(v)-\{x_{1}, X_{2}\}$ incident
and the minimal. (By definition ofto$lf$ -closedness of $T[D(v)]$ , there exists such thorn) Let $f=(v_{g}, t_{\min})\in F$ be the edge
vertex(possibly $v_{g}=dwn(g)$ ). We callwiththe succeeding vertex of , and callthis vertex
the subtree $T[D(v)g]$ the succeeding tree of . See
Fig. 7.
$g$(We discuss in section 8 the case in which condition (A3) does not hold.) If there are three
disjoint solo edges $g’,$ $g”$ on a path from andin $T[D(v)]$ . For the highest
to a leaf vertex
edge among these three edges, it is easy to seethat $|LEAV(v_{g})|\geq 6$ for its succeeding vertex .
Thus, if (A3) holds, then there are at most two
disjoint solo edges in the path from to any fringevertex in $T[D(v)]$ .
We sketch a procedure COVER for computingthat covers all edges in a mina subset
beimally $lf$ -closed subtree $T[D(v)]$ . Let$T[D(v)]$de, andthe set of leaf edges in$e=(u,u’)\inE$
withnote the set of all edges$u,$ $u’\in LEAF(v)$ , and $E_{prime}\subseteq E_{leaf}$ be the setof prime edges. The procedure consists of the following three phases, where the details of Phases-2
and 3 are described in the next subsections.

$v$

$w$

$g$

$v_{g}$$v$$E^{apx}\subseteq E$$F_{leaf}$$E_{leaf}$

Procedure COVER
If $|LEAF(v)|\leq 3$ , then it is easy to find a subthat covers $T[D(v)]$ and satisfies
set$E^{a\mathrm{p}x}\subseteq E$$\frac{3}{2}\beta(F_{leaf}\cup F_{f^{ri}nge}).\mathrm{I}\mathrm{n}$$4$what follows, $|LEAF(v)|\geq$

is assumed.

Phase-l (Covering all leaf edges in $T[D(v)]$ ):in theCompute a maximum matchinggraph (LEAF $(v),$ $E\iota eaf-Erimpe$ ), and denote by$W$ the set of unmatched vertices in LEAF $(v)$ . A
prime edge $g\in E_{prime}$ is called an unmatched
are unprime edge if both end vertices of) the set
(resp.,
matched, and denote byof all unmatched prime edges of type-l (resp., of
type-2). For each unmatched prime edge $(w, w’)$
$M^{*}\subseteq E$

7.1

OutlineAssume that none of Cases-1,2,3 and 4 holds in$T[D(v)]$ . Thus $T[D(v)]$ satisfies that
(A1) Every fringe vertex satisfies $|Ch(u)|\neq 1,3$ ,and each non-root and non-fringe vertex $v’\in$$D(v)$ with $|LEAF(v’)|=3$ satisfies (1),
$u$

$g$

$M_{1}’$$M_{2}^{l}$169

of type-2, where $w\prec w’$ , we see by (1) that
there is an unmatched prime edge $(w, w”)$ of
type-2 such that $w”$ is the sibling of $w’$ (also$(w’, w^{\mu})\in M_{1}’)$ . For each such pairof unmatchedprime edges $(w, w^{l})$ and, we choose arbitrarily one of them, and denote by
the resulting set of unmatched prime edges of type-2 (hence$(w, w^{\prime l})$$M_{2}’’$$|M_{2}^{\prime l}|=|M_{2}’|/2)$.

For each vertex $w\in W-V(M_{1’}\cup M_{2}^{l})$ (whereby the 2-edge-connectivity of $T+E$ ),choose an edge $e_{w}\in E_{G}(w)$ as follows. If isincident to a binding edgein (B1) or (B2) fora swing edge with $w\prec up(g)$ , then let $e_{w}=e_{g}$(by choosing one arbitrarily if there is more thansuch binding edge). Otherwise, let $e_{w}\in High(w)$ .
For each $g=(u, u’)\in M_{1}’$ , we choose anedge
as follows. If no unmatched primeedge of type-2 is adjacent to , then let$H_{\dot{i}}gh(\{u, u^{J},p(u)\})$ .
Otherwise, if an unmatchedprime edge $(w, u)$ of type-2 is adjacent to ,then let $e^{(g)}\in H_{\dot{i}}gh(D(p(w)))$ . Denote $E_{1}=$The solution $E^{apx}=E_{1}\cup E_{2}\cup E_{3}$ covers all theedges in $T[D(v)]$ , as will be shown in the next subsection. We first note that $|E_{1}|=|LEAF(v)|-$holds, because by $|W|=|LEAp(v)|-2|M*|$ ,we have $|E_{1}|=|M^{*}|+|M_{1}^{l}|+|M_{2}’’|+|\{e^{(g)}|$$|M^{*}|$$g\in M_{1}’\}|+|\{e_{w}|w\in W-V(M_{1}’\cup M_{2}’)\}|=$$|LEAF(v)|-|M^{*}|$ . Hence we have$|E^{apx}|\leq|LEAF(v)|-|M^{*}|+|E_{2}|+|E_{3}|$.

$E_{G}(w)\neq\emptyset$$w$

Let us assume thatandare chosen so thatthe next two properties hold.
$E_{2}$$E_{3}$$e_{g}$$g$

PROPERTY 7.1 $|E_{2}|+|E_{3}|\leq|M^{*}|$ .
PROPERTY 7.2 For some constant$\theta)(|E_{2}|+|E_{3}|)\leq|LEAF(v)|$$\square$$\theta\geq 0,$

$(2+$

.

$\square$$e^{(g)}$$e^{(g)}\in$

$g$

$g$

$M^{*\prime\prime\prime}\cup M_{1}\cup M_{2}\cup\{e^{(}g)|g\in M_{1}’\}\cup\{e_{w}|w\in$$W-V(M_{1}/\cup M)2J\}$

For the setof all leaf and fringe edges in$T[D(v)]$ , we see by Lemma 4.2 that$\frac{1}{3}(2|LEAF(v)|-|M^{*}|)$ . Therefore,$F_{v}$$\beta(F_{v})\geq$$\frac{|E^{apx}|}{\beta(F_{v})}$$\leq$.
$\leq$

Phase-2 (Merging-connected components in $T+E_{1}$ ): Consider all nontrivial 2edge-connected components in $T+E_{1}$ . To reduce
the number of those components, we choose anappropriate set $E_{2}\subseteq E-E_{1}$ of edges which combine different components in $T+E_{1}$ .
$2-\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}$$\frac{3(|LEAp(v)|-|M*|+|E_{2}|+|E_{3}|)}{2|LEAp(v)|-|M*|}$$\frac{3|LEAF(v)|}{2|LEAF(v)|-(|E_{2}|+|E_{3}|)}$(by Property 7.1 and by $|LEAF(v)|$$+|E_{2}|+|E_{3}|\leq 2|LEAF(v)|$which follows from Property 7.2)$\leq$$\frac{3|LEAF(v)|}{2|LEAF(v)|-\frac{1}{2+\theta}|LEAF(v)|}$(by Property 7.2)

Phase-3 (Making $T[D(v)]$ 2-edgeconnected): For each 2-edge-connected component
in $T+(E_{1}\cup E_{2})$ containing an edge
, we choose an edge $e^{(B)}\in High(X)$ forin$X=V(B)\cap(LEAF(v)\cup FRINGE(v))$ . Let
be the set of the edges
chosen for all thosecomponents B. (To be precise, Phase-3 of our algorithm may divide some 2-edge-connected component into several components (without separating two end vertices of any edge in) or
may treat some 2-edge-connected components asa single component before computi ng
for each$B.$component ) Output $E^{apx}=E_{1}\cup E_{2}\cup E_{3}$ .
$B$$M^{*}$$E_{3}$$=$$\frac{6+3\theta}{3+2\theta}=2-\frac{\theta}{3+2\theta}$,

which is strictly smaller than 2 unless $\theta=0$ . We
design Phases-2 and 3 such that Property 7.1 andProperty 7.2 with some $\theta>0$ hold.

$e^{(B)}$$M_{1}’\cup M_{2}’’$$e^{(B)}$$\square$

7.2

Phases-2 and 3

In this subsection, we describe the details of
Phases-2 and 3, and then prove some propertiesof the obtained setsand .
$E_{2}$

Phase-2 (Merging
ponents in $T+E_{1}$ ):$E_{3}$$2-\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}$-connected com-170

A matching edge $g=(z, z’)\in M^{*}$ with$z^{l}\in THORN(v)$ is called upward in a chain

Step 1.
$z,$

in $T[D(v)]$ if$P_{T}(u_{1}, uk)$

(B4) both and are incident to $P_{T}(u_{1}, uk)$ , andon, of and is incident to $P_{T}(u_{1,a}u)$, where $P_{T}(u_{1}, ua)$ is the upper-part of$z^{l}$

$z$

$z’$

$z$

$\mathrm{e}$-, we choose a binding edge
In the case(even if there is more than one
for eachbinding edge). Initially set $E_{merge}:=\emptyset$ , and let$A=\{A_{1}, \ldots , A_{h}\}$ be the set of all small compo. The binding edge ofnents satisfying
the swing edge in an $A_{i}\in A$ is called merging if$(\mathrm{c})-(1)$$g$$e_{g}$$(\mathrm{c})-(1)$$e_{g}$$g$$u_{1}$

to the current graph $T+(E_{1}\cup$$Eupper\cup Emerge)$ merges at least three 2-edgeconnected components, each of which contains at least one matching edge, into a single(B5) adding$P_{T}(u_{1,k}u)$(note that is not upward if $p(z)=u_{k}$ or $p(z’)=$. A chain $P_{T}(u_{1}, uk)$ is called active if it has
at least one upward matching edge and $P_{T}(u_{1}, ua)$does not belong to a single 2-edge-connected component in $T+E_{1}$ . A branch vertex is also called
active if it has an active chain $P_{T}(u_{1}, uk)$ .
$P_{T}(u_{1}, uk)$in
For each active chain $P$. For each
$T[D(v)]$ , we choose its upper-edge
active branch vertex , let $E_{upper}(v^{l})$ be the set ofchosen for all active chains
the upper-edges$P=P\tau(v^{J}=u_{1}, u_{k})$ of. Let $E_{upper}$ denote thefor all active branch vertices
union of.
$g$$u_{k})$$u_{1}$$e_{g}$

2-edge-connected component.
We repeatedly apply the following procedure until
no new merging edge is found.

$=$

MERGE Find an $A_{i}\in A$ such that theof the matching edge
binding edge
is merging in the current graphinto$T+$ (
Eupper $\cup E_{merge}$ ). Add$e^{(P)}$$v^{l}$$A_{i}$$e^{(P)}$$E_{1}\cup$

$v’$

Eer)p
Step 2. Consider the graph $T+$ (A 2-edge-connected component in this graph iscalled small if it contains a matching edge $g=$$(X_{1}, x_{2})\in M^{*}$ , but has no leaf vertex other than$e_{g_{i}}$$E_{merge}$ , letting $A:=A-A_{i}$$E_{up\mathrm{P}^{er}}(v’)$$v’$$g_{i}$$e_{\mathit{9}i}$.

$\square$

Let $E_{2}’:=E_{u}pper\cup E_{merge}$ .

$E_{1^{\cup}}$$\cdot$$A$and .
By (A1) and (A2) and $M^{*}\cap E_{prime}=\emptyset$ , thein a small component
and
two leaf vertices
are both thorn vertices. From definitions(B3), the matching edge $g=(x_{1}, X_{2})$ in a small
component satisfies one of the following cases.
$x_{2}$$x_{1}$$x_{1}$$C$$M^{*}$$E_{3}:=\emptyset$.

$x_{2}$$(\mathrm{B}1)-$$A$

Phase-3 (Making $T[D(v)]$ 2-edgeconnected): Consider all 2-edge-connected comin $T+(E_{1}\cup E_{2}’)$ containing an edge
ponents, and apply the following steps after lettingin-connected compoStep 3. Consider thenents $C$ in $T+(E_{1}\cup E_{2}’)$ such that
$2- \mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}$$A$

is not a swing edge, i.e., the path
$P_{T}(p(x1),p(X_{2}))$ between the parents $p(x_{1})$ and$p(x_{2})$ contains a branch vertex. (In the following(b) and (c), is assumed to be a swing edge.)(b) One of the parents $p(x_{1})$ and $p(x_{2})$ belongs to
the lower-part of a chains.
(c) Both $p(x_{1})$ and $p(x_{2})$ belong to the middlepart of the same chain, where
(a)

$g$

(1)

$E(C)\cap M^{*}\neq\emptyset$

and $|E(C)\cap M^{*}|=|E(c)\mathrm{n}E_{2}’|$ .

$g$

has a binding edge $e_{g}=(w, y)\in E$ satisfying one of (B1) and (B2), or$g$

By procedure MERGE, this can occur only whenholds and the edges in $E(C)\cap$
are all upward, where each $e\in E(C)\cap M^{*}$
corresponds to an upper-edge $e’\in E(C)\cap$ Eupper
by Step 1.
For each of such components $C$ , we partition,$E(C)\cap M^{*}$ into subsets
such that the upward matching edges in eachare defined on some chains $P\tau(v_{i}, u)$ ofdethe same branch vertex . For each , letnote the graph which consists of upward edges in$E(C)\cap E\prime 2\subseteq E_{upper}$$M^{*}$$M_{up}^{*}(v_{1}),$$g$

is a solo edge.

$M_{up}^{*},(v_{q})$$M_{up}^{*}(v_{i})$$v_{i}$(2)$\ldots$$v_{i}$$C_{v_{i}}$171(for notational convenience),and choose an edge $e^{(B)}\in High(V(M^{*}(upvi)))$ forcomponent $B=C_{v_{i}}$ . In this case,is adjacent to an upward matching edge.
$e^{(P)}\in
E_{upper}(v_{i})$Letbe the upper-edge of $P=$
$P_{T}(v_{i}, u);$ that has the matchingedge . See
Fig. 8. If $lca(e^{()})B\prec v_{i}$ , then we replaceby:(LEAF $(v)\cup FRINGE(v)$ ) , where $V(A(P_{i}))$ denote the set of all vertices in the small components
in $A(P_{i})$ . Let
be the set of all these components $B=A(P_{i})$ computed in this step.
For t,he final $E_{upper}$ andcomputed in theabove procedure, we denote $E_{2}=E_{upper}\cup E_{merge}$
and $E^{apx}=E_{1}\cup E_{2}\cup E_{3}$ .

$M_{up}^{*}(v_{i})\cup E_{uppr}e(v_{i})$$)$$e^{(B)}$$B^{S5}$$g^{l}\in M_{up}^{*}(v_{i})$$E_{3}$$g’$$e^{(P)}$$\square$$e^{(B)}$$E_{3}:=E_{3}\cup\{e^{(B}\})$,$E_{upper}(v_{i}):=E_{u}pper(v_{i})-\{e\}(P)$updating $C_{v_{i}}:=C_{v_{i}}+e^{(B)}-e^{(P)}$ . (Otherwise(i.e., if $v_{i}\preceq lca(e^{()})B$ ) we do nothing by setting
to be empty.) Let
denote the set of all$B=C_{v_{i}}$these components
computed in this step.
$e^{(B)}$$B^{S3}$,

We now show that the obtained $E^{apx}$ covers alledges in $\tau 1D(v)]$ (for this we do not need condition (A3) .
$)$LEMMA 7.1 Let $G=(V, E)$ be a graph and $T=$
(V, $F$ ) be a tree rooted at with $E\cap F=\emptyset$ suchthat $T+E=(V, F\cup E)$ is 2-edge-connected. Let$T[D(v)]$ be a minimally $lf$ -closed subtree satisfying conditions $(A1)$ and $(A2)$ . Then the subset$E^{apx}=E_{1}\cup E_{2}\cup E_{3}\subseteq E$
obtained by the procedure COVER covers all edges in $T[D(v)]$ .
$r$

Proof: Omitted.

$\square$Now we estimate the size of, we first show$E^{apx}$. For each$B\in B^{S3}\cup B^{S4}\cup B^{S5}$$|E(B)\cap M^{*}|\geq|E(B)\cap E_{2}|+|E(B)\cap E_{3}|$$\mathrm{B}8:\mathrm{n}\mathrm{l}\mathrm{u}\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$for Step 3.

. (2)By construction of Phase-2, any edges inarechosen so that if the resulting
component $C$ has edges from, then $C$ hasat least $p+1$ matching edges, except for the casein Step 3. In Step 3, each component $C$ with$|E(B)\cap M^{*}|=|E(B)\cap E_{2}^{l}|$ is divided into several
components $B=C_{v_{i}}$ , for which an upper-edge$E(B)\cap E_{2}’$ is discarded or no edge
is add to. Each $e^{(B)}\in E_{3}$ is chosen for a component $B$
which contains a matching edge in. Therefore,(2) holds, and we have Property 7.1$E_{2}’$$2- \mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}- \mathbb{C}\mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{e}\mathrm{d}$Step 4.
Consider the remaining 2-edgeconnected components in $T+(E_{1}\cup E_{2}’)$ not considered in Step 3. For each component $B$ that
contains an edge in, but is not a small component satisfying (b), let $E_{3}:=E_{3}\cup\{e^{(B)}\}$by choosing an edge $e^{(B)}\in H_{\dot{i}}gh(X)$ for $X=$
$V(B)\cap(LEAF(v)\cup FRINcE(v))$ . Letbethe set of all these components $B$ computed inthis step.
$M^{*}$$B^{S4}$

Step 5. Finally, we partition the set of all
small components satisfying (b) into subsets$A(P_{1}),$$A(P_{q})$such that all components ineach $A(P_{i})$ are defined on the same chain . We
treat each $A(P_{i})$ as a single component $B$ . For
each component $B=A(P_{i})$ , let $E_{3}:=E_{3}\cup\{e^{(B)}\}$by choosing an edge $e^{(B)}\in High(V(A(Pi))\cap$$\ldots,$$P_{i}$$p$$E_{2}’$$e^{(B)}$$E_{3}$$M^{*}$$|M^{*}|\geq|E_{2}|+|E_{3}|$.

If the minimally $lf$ -closed subtree
fies condition (A3), then we can show the next
property.
$T[D(v)]\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{S}}-$

CLAIM 7.1 $(2 +\theta)(|E_{2}|+|E_{3}|)\leq|LEAF(v)|$holds for.
$\theta=\frac{2}{7}$172
Proof: Omitted.

口

LEMMA 8.2 For a solo edge $g\in E$ defined on abe the succeedchain $P_{T}(u_{1}, u_{k})(u_{1}\prec u_{k})$ , let
ing vertex of . Assume that $T[D(v_{g})]$ satisfies
condition $(A1)-(A3)$ . For $|LEAF(v_{g})|\geq 6$ andthat cov, an edge set
any fixed
and has size $|E^{+}|\leq(1.92+\epsilon)\beta(F_{g})$ canbe found in the same time complexity of COVER.
applied to$v_{\mathit{9}}$Therefore, from the argument at the end of section 7.1, we have the following result.
LEMMA 7.2 Let $G=(V, E)$ be a graph and $T=$
(V, $F$ ) be a tree rooted at with $E\cap F=\emptyset$ suchthat $T+E=(V, F\cup E)$ is 2-edge-connected. Let$T[D(v)]$ be a minimally $lf$ -closed subtree satisfying conditions $(A1)-(A3)$ . Then the subset$E^{apx}=E_{1^{\cup E}2^{\cup}3}E\subseteq E$ obtained by the procedure
COVER satisfies $|E^{apx}|\leq 1.92\beta(F_{v})$ for the setof leaf and $(pseud_{\mathit{0}}-)pinge$ edges in $T[D(v)]$ .
$r$$F_{v}$

口8

Reduction by COVER

We consider the remaining case in which a given
minimally $lf$ -closed tree $T[D(v)]$ does not satisfy
condition (A3). That is, there is a solo edges$g\in E$ on the middle-part of a chain in $T[D(v)]$such that its succeeding tree $T[D(v)g]$ has at least
six leaf vertices (i.e., $|LEAF(v_{g})|\geq 6$ ). We apply
procedure COVER to find an approximate solution to cover the edges in the tree $T[D(v)g]$ .
LEMMA 8.1 For a solo edge $g=(x_{1}, x_{2})\in E$ defined on a chain $P_{T}(u_{1}, uk)(u_{1}\prec u_{k})$ in a $\min-$be the sucimally $lf$ -closed tree $T[D(v)]$ , let
be the highest verceeding vertex of , and letthat are intex among all vertices in$D(v_{g})-v_{g}$via an edge incident to a vertex in$E$ (see Fig. 7).
$F_{g}=E(T[D(v_{g})])$
andThen for$x= \min(w^{*}, up(g))$ , it holds$v_{g}$$g$$w^{*}$$P_{T}(u_{1}, u_{k})$$g$$E^{+}\subseteq E$$\epsilon>0$$ers\overline{F_{g}}$$T[D(v\mathit{9})]$Proof: Omitted.

口such thata solo edges$|LEAV(v_{g})|\geq 6$ for its succeeding vertex, thenwe can apply Lemma 8.2 to find a $(1.92 +\epsilon)-$approximation solution to cover the edges in thetree $T[D(v)g]$ .

isIf there$g$$v_{g}$

9

Entire description

We are now ready to describe the entire algorithm. Given a graph $H=(V, E’)$ and a subset$X\subseteq V$ , we denote by $H/X$ the graph obtained
from $H$ by contracting $X$ into a single vertex anddeleting all the resulting self-loops.
APPROX
Input: A graph $G=(V, E)$ and a tree $T=(V, F)$rooted at with $E\cap F=\emptyset$ such that $T+F=$(V, $F\cup E$ ) is 2-edge-connected, and.
a constantthat covers $F$ and has
Output: A subset
size $|E’|\leq(1.92+\epsilon)\beta(F)$ .
;contains more than one vertex do
while
while one of Cases-1,2,3 and 4 holds do, (P4)
Execute proceduresin Cases-1,2,3,4, respectively, and add
to $E’$ the edges retained by the procedure
end;(A1) and (A2) hold. $*/$
Choose a minimally $lf$ -closed subtree $T[D(v)]$ ;if condition (A3) holds in $T[D(v)]$ thenwhich
Compute an edge set
covers edges in $T[D(v)]$by procedure COVER;$r$$\epsilon>0$$E^{l}\subseteq E$$E’:=\emptyset$$T$$\overline{F_{g}}-F_{g}\subseteq\{f_{1}, f_{2}\}\cup E(P\tau(X, v_{g}))$

where
.

$f_{1}$

and$f_{2}$,

are the two leaf edges adjacent to$g$

Proof: Omitted.

$\backslash$.

$\square$$(\mathrm{P}1),(\mathrm{P}2),(\mathrm{P}3)$$/*_{\mathrm{W}\mathrm{h}\mathrm{i}1}\mathrm{e}^{*}/$

that covers $F_{g}=$Given an edge set$E(T[D(v_{g})])$ , we note here that an edge set$E”$ can be constructed to coverat most threeby adding toand one to coveredges (two edges to cover$E^{l}\subseteq E$$F_{\mathit{9}}\cup\{f1, f_{2}\}\cup$$E^{l}$$E(P_{T}(X,v)g)(\supseteq\overline{F_{g}})$$\{f_{1}, f_{2}\}$$E(P_{T(}X, v_{\mathit{9}})))$.

$/*\mathrm{C}_{0\mathrm{n}}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{S}$$E^{apx}\subseteq E$173$E’:=E’\cup Eapx$ ;For $X=$ {the end vertices of edges$f\in F$ covered by}, $T:=T/X$
and $G:=G/X$ ;else $/*\tau[D(v)]$ has a solo edge such thatits succeeding tree $T[D(vg)]$
contains at least six leaf vertices. $*/$
Choose such succeeding tree $T[D(v_{g})]$ ;{all edges in $T[D(v_{g})1$ };Compute an edge set
which
by Lemma 8.2 withcovers;constant$E’:=E/\cup E^{+}$ ;For $X=$ {the end vertices of edges $f\in F$
covered by}, $T:=T/X$ and $G:=G/X$
end;
Output $E’$ (after modifying , if necessary,so that the edgesin Cases-3
and 4 are also covered in without increasing
the size of $E’$ ).

graphs via matching,” Proc. 37th IEEE Symp.
on Found. Comp. Sci. (1996) 292-301.

$E^{apx}$$g$$F_{v_{g}}:=$$E^{+}\subseteq E$[3] K. P. Eswaran and R. E. Tarjan: “Augmentation problems,” SIAM J. Computing, 5 (1976)
653-665.

[4] G. N. Frederickson and J. J\’aJ\’a: “Approximation algorithms for several graph augmentation problems,” SIAM J. Computing, 10(1981) 270-283.

$\overline{F_{v_{g}}}$$\epsilon>0$$E^{+}$$/*_{\mathrm{W}\mathrm{h}\mathrm{i}\mathrm{l}\mathrm{e}}*/$$E^{l}$$f^{\prime_{\mathrm{C}\mathrm{o}\mathrm{n}}}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{e}\mathrm{d}$$T$[5] D. Harel and R. E. Tarjan: “Fast algorithms
for finding nearest common ancestors,” SIAM
J.
(1984) 338-355.
$C_{ompu}t_{\dot{i}ng}.’13$[6] S. Khuller and R. Thurimella: “Approximation algorithms for graph augmentation,”
Proc. 19th International Colloquium on Automata, Languages and Programming Conference (1992) 330-341.

$\square$By using the least common ancestor algorithm$[5, 9]$ and the maximum matching algorithm [8],the above algorithm can be implemented to run

in $O(n^{1/2}m+n^{2})$ time.
THEOREM 9.1 Given a graph $G=$ (V, $E$ ) anda tree $T=$ (V, $F$ ) with $E\cap F=\emptyset$ such that
$T+E=(V, F\cup E)$ is, the problem of finding a smallest 2-edge-connected spanning subgraph $H=(V, F\cup E’)$ containing $T$ is$(1.92+\epsilon)$ -approximable in $O(n^{1/2}m+n^{2})$ time
, where $n=|V|$ andfor any fixed constant$m=|E\cup F|$ .
$\mathit{2}- edge- Connec\theta ed$$\epsilon>0$[7] S. Khuller and U. Vishkin: “Biconnectivity
approximations and graph carvings,” J. $ACM$,
41 (1994) 214-235.

[8] S. Micali and V. V. Vazirani: “An $O(\sqrt{|V|}|E|)$
algorithm for finding maximum matching in
general graph,” Proc.
IEEE Symp. $on$
Found. Comp. Sci. (1980) 17-27.
$\mathit{2}\mathit{1}st$[9] B. Schieber and U. Vishkin: “On finding lowest common ancestors: simplification and parallelization,” SIAM J. Computing, 17 (1988)
1253-1262.

$\square$

参考文献[1] J. Cheriyan, A. Seb\"o and Z. Szigeti: “An
improved approximation algorithm for minimum size 2-edge connected spanning subgraphs,” Lecture Notes in Computer Science,
1412, Springer-Verlag,(1998) 126136.
$\mathrm{I}\mathrm{P}\mathrm{C}\mathrm{O}’ 98$[2] J. Cheriyan and R. Thurimella: “Approximating minimum-size -connected spanning sub$k$[10] S. Tsukiyama, K. Koike and I. Shirakawa:“An algorithm to eliminate all complex triangles in a maximal planar graph for use in VLSI
floor-plan,” Proc. ISCAS’86 (1986) 321-324.