数理解析研究所講究録 1461 巻 2005 年 96-110

98
Approximation Algorithms for Optimization Problems
Related to the Edge Dominating Set
京都大学 \sim 清報学研究科

1

福永 拓郎 (Takuro Fukunaga)
永持 仁 (Hiroshi Nagamochi)
Graduate School of Informatics,
Kyoto University

Introduction,
anddenote the sets of nonnegative integers, rational numbers and real numbers,
respectively. Moreover, let $G=(V, E)$ be a simple undirected graph. We say that an edgeor , and define an edge dominating set (EDS) to be a$e=(u, v)$ dominates edges incident to
set $F$ of edges such that each edge in $E$ is dominated by at least one edge in $F$ . Given a cost
together with , the EDS problem asks to find an EDS with the minimum cost.
vectorThis problem is one of the fundamental covering problems such as the well-known vertex coverproblem and has some useful applications $[2, 18]$ . The problem with a cost vector with $w(e)=1$
for all $e\in E$ is called the cardinality case; otherwise the problem is called the cost case. The-hard even for some restricted classes of graphs such as planar or bipartite
cardinality case isgraphs of maximum degree 3 $[10, 18]$ , Moreover, it is proven that the cardinality case is hard to. In addition to theseapproximate within any constant factor smaller than 7/6 unlesshardness, some polynom ially solvable cases are also found for the cardinality case [10, 13, 17].
For the cost case, the problem is approximate within factor of $2r$ if there is an r-approximation
algorithm for the minimum cost vertex cover problem [3], where currently $r\leq 2$ is known. Furthermore, Carr et al. [3] presented a 2.1-approximation algorithm. Their algorithm constructs an
instance of the minimum cost edge cover problem from the original instance and finds an optimaledge cover for the resulting instance. A key property for this method is that an edge cover inthe resulting instance is also an EDS for the original instance and that its cost is at most 2.1
times of the minimum cost of an EDS in the original instance. The property is proved based ona relation between the fractional edge dominating set polyhedron and the edge cover polyhedron.
The former is a polyhedron containing all incidence vectors of EDSs, which may not be the convex
hull of these vectors. In contrast the edge cover polyhedron is the convex hull of all incidence
vectors of edge covers, which is shown to be an integer polyhedron [16]. Afterwards, Pujito andNagamochi [6] gave a 2-approxim ation algorithm by using a refined EDS polyhedron. Moreover,K\"onemann et al. proposed 3-approximation algorithms for the problem of finding a minim um cost
EDS which forms a tree or a tour [11].
In this PaPer, we discuss the approximability of the following four probJem related to the
EDS problem.

Let$\mathbb{Z}_{+}$$\mathbb{R}_{+}$$\mathbb{Q}_{+}$

$u$

$v$

$G$

$w\in \mathbb{Q}_{+}^{E}$$w$$\mathrm{N}\mathrm{P}$$\mathrm{P}_{--}^{-}\mathrm{N}\mathrm{P}[4]$$\mathrm{s}$problem This is a capacitated version of the
The $(b, c)$ edge dominating set, a capacity
EDS problem. We are given a graph $G=(V, E)$ , a demand vectorif. A set $F$ of edges in is called avectorand acost vector
each $e\in E$ is adjacent to at least $b(e)$ edges in $F$ , where we allow to contain at most
. If $b(e)=1$
multiple copies of edge . The problem asks to find a minimum cost
for all $e\in E$ , this problem is equivalent to the EDS problem.
$((b, c)-\mathrm{E}\mathrm{D}\mathrm{S})$$b\in \mathbb{Z}_{+}^{E}$$w\in \mathbb{Q}_{+}^{E}$$c\in \mathbb{Z}_{+}^{E}$$G$$(b, \mathrm{c})-\mathrm{E}\mathrm{D}\mathrm{S}$

$F$

$e$

$\mathrm{c}(e)$$(b, c)- \mathrm{E}\mathrm{D}\mathrm{S}$97

The $EDS$ problem in hypergraphs (HEDS problem) This is an extension of the EDS to a
. The
hypergraph. We are given a hypergraph $H=(V_{\dot{l}}E)$ , and a cost vector
problem asks to find a minimum cost hyperedge set $F$ such that each hyperedge $e\in E$ iseither contained in $F$ or adjacent to a hyperedge in .
$w\in \mathbb{Q}_{+}^{E}$$\mathrm{n}F$

The $(d, c)$ -edge cover with degree constraints over subsets This is an extension of the edgeof vertex, a family
cover. We are given a graph $G=(V, E)$ , a cost vector
to find a
problemasks. The, and a capacity vector
sets, a demand vector
$S\in
S$
$(V,
F)$
$F$
is
at leastoverminimum cost edge set such that the sum of degrees in graph$F$multiple copies of edge .
$b(S)$ , where
can contain at most
$S\subseteq 2^{V}$$w\in \mathbb{Q}_{+}^{E}$$b$$c\in \mathbb{Z}_{+}^{E}$$\in \mathbb{Z}_{+}^{S}$$e$$\mathrm{c}(e)$problem, we
The $(b, c)$ -edge packing problem This is a packing problem. As in the. A set $F$ of edges in is called aand,are given $G=(V, E)$ ,$F$
to$(b, c)$ -edge packing if each $e\in E$ is adjacent to at most $b(e)$ edges in $F$ , where we allow
contain at most $c(e)$ multiple copies of edge . The problem asks to find a maximum cost$(b, c)$ -edge packing.
$(b, \mathrm{c})- \mathrm{E}\mathrm{D}\mathrm{S}$$b\in \mathbb{Z}_{+}^{E}$$G$$w\in \mathbb{Q}_{+}^{E}$$c\in \mathbb{Z}_{+}^{E}$$e$

The first two problems are proposed and analyzed by O. Parekh in [15]. The third problem isshown in [7] and the fourth problem is proposed in [8], In this paPer, we introduce these results
and give more detailed analysis.
The paper is organized as follows. Section 2 introduces notations used in this paper. Sections
6,
4 and 5 describe the above four problems and propose the approximation algorithms for
3,them, respectively.

2

Preliminaries,
Let $G=(V, E)$ denote a simple
the fc-th harmonic number
We denote byundirected graph with a vertex set and an edge set . An edge $e=(u, v)\in E$ in is defined asa pair of distinct vertices and . Let $H=(V, E)$ denote a hypergraph, where an edge is definedby a set of two or more vertices and an edge in $H$ may be called a hyperedge. For a vertex ,denotes the set of edges incident
denotes the set of edges incident to . For an edge ,,denotes theto vertices contained in , i.e., $\delta(e)=\{e’\in E|e\cap e’\neq\phi\}$ . For a subset
inedges
contained$E[S]$
denotes the set of
set of edges $e=(u,v)$ with $u\in S$ and $v\in V-S$ , and.
,vector,, i.e., $E[S]=\{e\in E|e\underline{\subseteq}S\}$ . Let be an $|E|$ -dimensional nonnegative real
$E$ , we denote$x(e)$of. For a subset
We indicate the entry in corresponding to an edge by$e’\in F$ corresponds to an edge $e\in E$ ,$= \sum_{e\in F}x(e)$ . For an edge set $F$ such that each edge
, $x\langle F\rangle(e’)=x(e)$ for all $e’\in F$ .
denotes a projection of to $F$ ,$\sum_{i=1}^{k}\frac{1}{i}$$\theta_{k}\in \mathbb{Q}_{+}$

$u$

$G$

$E$

$V$

$v$

$v$

$e$

$v$

$\delta(v)$$\delta(e)$$\delta(S)$$S\underline{\mathrm{C}}V$$e$$\mathrm{i}.\mathrm{e}.$$S$$x\in \mathbb{R}_{+}^{E}$

$x$

$F$

$e$

$x$

$\mathrm{x}(\mathrm{F})$3(b,$c)-\mathrm{E}\mathrm{D}\mathrm{S}$$\mathrm{i}.\mathrm{e}.$$x$$x\langle F\rangle\in \mathbb{R}_{+}^{F}$

problem(d,$c)$ -edge cover and polytopes, a capacity vector
For a graph $G=(V, E)$ , a demand vector
is given as, an integer program of the

3.1

(b,

$\mathrm{c})- \mathrm{E}\mathrm{D}\mathrm{S}$$b\in \mathbb{Z}_{+}^{E}$$w\in \mathbb{Q}_{+}^{E}$$c\in \mathbb{Z}_{+}^{E}$and a cost vector$(b, c)- \mathrm{E}\mathrm{D}\mathrm{S}$minimizesubject to$w^{T}x$$x(e)\leq c(e)$$x(\delta(e))\geq b(e\rangle$$x\in \mathbb{Z}_{+}^{E}$.

for each $e\in E$ ,for each $e\in E$ ,

(1)

a8

.
satisfying (1) is called a
A vector
Let us define a polytope EDS(G, , ) as the set of vectors$(b, c)- \mathrm{E}\mathrm{D}\mathrm{S}$$x\in \mathbb{Z}_{+}^{E}$

$b$

(a)
(b)

$c$

$0\leq x(e)\leq c(e)$$x(\delta(e))\geq b(e)$such that$x\in \mathbb{R}_{+}^{E}$for each $e\in E$ ,for each $e\in E$ .

This is the feasible region of an LP relaxation of problem (1). Thus the cost of an optimal solution
in EDS(G, , ) is a lower bound on the minimum cost of a given instance $(G, b, c, w)$ .
We now review some results on the $(d, c)$ edge cover problem., which is another important
covering problem. This problem consists of a simple undirected graph $G=(V, E)$ , a demand. An integer
and a cost vector
vectordefined on , a capacity vector
for each $v\in V$ and $x(e)\leq c(e)$ for
vectoris called a $(d, c)$ -elge cover if
each $e\in E$ . The objective of the $(d, c)$ -edge cover problem is to find a minimum cost $(d, c)$ edge
cover which is formulated as
$b$

$c$

-

$V$

$d\in \mathbb{Z}_{+}^{V}$$w\in \mathbb{Q}_{\dashv}^{E}$$c\in \mathbb{Z}_{+}^{E}$$x(\delta(v\rangle)\geq d(v)$$x\in \mathbb{Z}_{+}^{E}$

minimizesubject to$w^{T}x$for each $e\in E$ ,for each $v\in V$ ,$x(e)\leq c(e)$$x(\delta(v))\geq d(v)$$x\in \mathbb{Z}_{+}^{E}$(2).

There exists a polynomial time algorithm for this problem [14]. Furthermore, it is known [16] that
this problem has an equivalent linear program formulation, where the convex hull of all feasible
solutions is characterized by the following set of inequalities:
(c)
(d)
(e)

Let

3.2

$0\leq x(e)\leq c(e)$$x(\delta(v))\geq d(v)$$x(E[U])+x( \delta(U))-x(F)\geq\lceil\frac{d\{U]- c(F)}{2}\rceil$$\mathrm{E}\mathrm{C}(G, d, c)$for each $e\in E$ ,for each $v\in V$ ,,for each$U\underline{\mathrm{C}}V$$F\subseteq\delta(U)$with odd $d(U)-c(F)$ .

denote the polytope represented by these inequalities.

Approximation algorithm

Given an instance $(G, b, c, w)$ of the
problem, we first construct an instance of the $(d, c)-$edge cover and then computes an optimal solution for it as an approximate solution to the input
instance. Formal description is given in Algorithm 1. A parameter is given to the algorithm.
If the input instance is infeasible, then there exists an edge $e\in E$ with $c(\delta(e))<b(e)$ . Then,the LP relaxation to be solved in Step 1 is also infeasible. Hence DOMINATE(f) stops in Step 1
at that time.
. For an edge $e=(u, v)\in E$ , let us suppose $x^{*}(\delta(u)-E’)\geq$
We first show that is a$(6, c)-\mathrm{E}\mathrm{D}\mathrm{S}$$f$$\overline{x}$$x^{*}(\delta(v)-E’)$$(b, c)- \mathrm{F}_{\lrcorner}\mathrm{D}\mathrm{S}$. Then,$\overline{x}(\delta(u)-E’)\geq d_{x}*(u)\geq b(e)-c(\delta(e)\cap E’)$

The above first inequality holds since
the definition of. Since$\overline{x}\langle E-E’\rangle$

is a-edge cover, and the second one holds by, it holds$d_{x^{*}}$$\overline{x}(\delta(e)\cap E’\rangle=c(\delta(e)\cap E’)$$d_{x^{*}}$.

$x(\delta(e))\geq x(\delta(u)-E’)+x(\delta(e\rangle\cap E’)\geq b(e)$.

We can easily check that
also holds. Hence, is a
and algorithm
DOMINATE(f) outputs a feasible solution.
We then analyze the approximation factor of algorithm DOMINATE(/) by establishing a
relation between EDS(G, , ) and. In the following discussion, we suppose that$0\leq\overline{x}(e)\leq c(e)$

$b$

$c$

$\mathrm{E}\mathrm{C}(G, d_{x}*, c)$$\overline{x}$$(b, c)- \mathrm{E}\mathrm{D}\mathrm{S}$89

Algorithm 1

DOMINATE(/)

problem.
Input: An instance (G, b, c, w) of the (b,to instance (G, b, c, w) and a real f $>0$ .
Output: A (b,$c)- \mathrm{E}\mathrm{D}\mathrm{S}$$c)- \mathrm{E}\mathrm{D}\mathrm{S}$to the linear program that minimizes $\min w^{T}x$
Step 1: Compute an optimal solution.
subject to $x\in$ EDS(G, , ). If it is infeasible, outputs “infeasible”. Moreover, let$b(e’):=$$E’:=E’\cup\{e\}$$\overline{x}(e):=c(e)$
and
set
$e\in
E$
,
with $fx^{*}(e)>c(e)$ , let
Step 2: For each$\max\{0,b(e’)-c(e)\}$ for all $e’\in\delta(e)$ .
$:=0$ if $x^{*}(\delta(u)-E’)\geq$
Step 3: For each edge $e=(u, v)\in E$ , let $b_{x}’*(u, e):=b(e)$ and$x^{*}(\delta(v)-E’)$ , and let $b_{x^{*}}’(u, e):=0$ and $b_{x^{*}}’(v, e):=b(e)$ otherwise.
.
Step 4: For each vertex $v\in V$ , let$(d_{x}*,c)$-edge cover for $G’=(V, E-E’)$ and $w\{E-E’\rangle$ .
to a minimum cost
Step 5: Set).
to (GyThen output as$x^{*}\in \mathbb{R}_{\dashv}^{E}$$b$$E’:=\emptyset$$c$$b_{x^{*}}’(v,$$e\rangle$$d_{x}* \langle v):=\max_{e\in\delta(v)}b_{x^{*}}’(v, e)$$x\langle E-E’\rangle$$\overline{x}$$\mathrm{a}$$b,$ $c,$ $w$$(b, c)- \mathrm{E}\mathrm{D}\mathrm{S}$because, if $b(e)=0$ for all edges $e\in E$ , DOMINATE(f)for at least one edge
apparently outputs the optimal solution $x=0^{E}$ . Moreover, we consider the case of $c=+\infty$ atfirst. In this case, parameter makes no effect on the choice of $E’$ in the algorithm and it always.
holds$b(e)\geq 1$$e\in F_{\lrcorner}$$f$$E’=\emptyset$) andLemma 1. Let be a vector in EDS(G $=(V$, $E$ ),vectorDOMINATE(f).
Thenalgorithm
Step
by
4 of
from
.
(d) for$b,$ $+\infty$$x$$d_{x}\in \mathbb{Z}_{+}^{V}$$2x\in \mathbb{R}_{\mathrm{T}}^{E}|$$x$be a vector constructedsatisfies conditions (c) and$\mathrm{E}\mathrm{C}(G, d_{x}, +\infty)$oo) because
Proof: Let $x\in$ EDS $(G,b, +\infty)$ . Then vector $2x$ satisfies condition (c) for EC( ,$2x(\delta(v))\geq d_{x}(v)$
$2x$
,
(d),
satisfiesthat). We now show
holds by (a) for EDS(G,for all $v\in V$ . Let be a vertex in . Then there is an edge $e=(u, v)\in E$ such that
holds. Therefore,$dx(v)=b_{x}’(v, e)$ . If $b_{x}’(v, e)=0$ , then we have $2x(\delta(v))\geq 0$ $=d_{x}(v)$ since$x(\delta(e))\geq b(e)$$x(\delta(v))\geq
x(\delta(u))$
Now
hold.
$b_{x}^{J}(v,e)=b(e)$andlet us assume $b_{x}’(v, e)>0$ . Then$x(\delta(v))+x(\delta(u))=x(\delta(e))+x(e)\geq
b(e)+x(e)$, which implies
holds by (b) for
holds. Then we have$G$$d_{x},$$+$$\mathrm{i}.\mathrm{e}.$$6,$ $+\infty$$x\in \mathbb{R}_{+}^{E}$

$V$

$v$

$x\in \mathbb{R}_{+}^{B}$$\mathrm{E}\mathrm{D}\mathrm{S}(G, b, +\infty)$$2x(\delta(v))\geq x(\delta(u))+x(\delta(v\rangle)\geq b(e)+x(e)\geq b(e)=b_{x}’(v, e)=d_{x}(v)$Therefore, (d) also holds for$2\mathrm{a}$.
$\square$.

If $c=+\infty$ , condition (e) for$\mathrm{E}\mathrm{C}(G, b, c)$is equivalent tofor each$x(E[U])+x( \delta(U))\geq\lceil\frac{d(U)}{2}\rceil$This is because $d(U)-c(F)=-\infty$ for$F\neq\emptyset$$U\underline{\mathrm{C}}V$

with odd $d(U)$ .

.

Lemma 2. For a simple undirected graph $G=(V, E)$ and a demand vector
satisfying conditions (c) and (d) for$\min_{v\in Vb(v)\neq 0},d(v)$ . Then for any vectorx’$d\in \mathbb{Z}_{+}^{V}$$\in \mathbb{R}_{\dashv-}^{E}$

vector$y=(1+ \frac{1}{2\lfloor 3\beta/2\rfloor+1})x’\in \mathbb{R}_{+}^{E}$

satisfies condition (e) for$\mathrm{E}\mathrm{C}(G, d, +\infty)$.

, let $\beta=$$\mathrm{E}\mathrm{C}(G,d, +\infty)$

,

100

be a subset of $V$ such that $d(U)$ is odd. It suffices to show that (e) holds for
Proof: Let
contains a vertex such that $d(v)=0$ , then (e) follows inductively from that
$x=y$ and . If$y(E[U’])+y(\delta(U’))\geq\lceil d(U’)/2\rceil$ for $U’=U-\{v\}$ since $y(E[U])+y(\delta(U\rangle)\geq y(E[U’])+y(\delta(U’))$
and $d(U)=d(U’)$ hold. Hence we assume without loss of generality that $d(v)\geq\beta$ for all $v\in U$ .
Moreover, if $|U|=1$ , then (e) is implied by (d) since for $U=\{v\}$ , $y(E[U])+y(\delta(U))=y(\delta(v))\geq$$x’(\delta(v))\geq d(v)\geq\lceil d(v)/2\rceil$ .
We now consider the case of $|U|=2$ . Let $U=\{v_{1}, v_{2}\}$ . Since$d(U)=d(v_{1})+d(v_{2})$ is odd, $d(v_{1})\neq d(v_{2})$ holds, where we assume without loss of generality$d(v_{1})>d(v_{2})$ . Then
$U$

$U$

$U$

$v$

$\lceil\frac{d(U)}{2}\rceil=\lceil\frac{d(v_{1})+d(v_{2})}{2}\rceil\leq d(v_{1})$.

We have$x’(E[U])+x’(\delta(U\rangle\rangle\geq x’(\delta(v1))$

because$E[U]\mathrm{U}\delta(U)\supseteq\delta(v_{1})$. Since$y(E[U])+y(\delta(U))$$x’$satisfies $x’(\delta\{v1))\geq d(v1)$ by (d), we have$\geq$$x’(E[U]\rangle+x’(\delta(U))$$\geq$$x’( \delta(v_{1}))\geq d(v_{1})\geq\lceil\frac{d(v_{1})+d(v_{2})}{2}\rceil=\lceil\frac{d(U)}{2}\rceil$.

In what follows, we assume that $|U|\geq 3$ and $d(v)\geq\beta$ for all $v\in U$ .
, we haveholds for all $v\in U$ by (d) for
Since$\mathrm{E}\mathrm{C}(G, d, +\infty)$$x’\langle\delta(v))\geq d(v)$$2x’(E[U])+x’( \delta(U))=\sum_{v\in U}x’(\delta(v))\geq d(U)$,for which it holds$x’(E[U])\succ$ $x’( \delta(U))\geq\frac{d(U)+x’(\delta(U))}{2}\geq\frac{d(U)}{2}$.

To show (e), we only have to prove that,$\frac{\lceil d(U)/2]}{d(U)/2}=1+\frac{1}{d(U)}\leq 1+\frac{1}{2\lfloor 3\beta/2\rfloor+1}$

or eq uivalently$d(U)\geq 2\lfloor 3\beta/2\rfloor+1$.

Prom the assum ption, $d(U)\geq 3\beta$ holds. Moreover, since $d(U)$ is odd, $d(U)\geq 3\beta+1$ if
This implies (3).
Theorem 1. Let
solution of a cost within a factor of$\beta=\min_{\mathrm{e}\in E,b(e)\neq 0}b(e)$$(b, +\infty)- \mathrm{E}\mathrm{D}\mathrm{S}$problem$3\beta$

is even.
$\square$. Algorithm DOMINATE(/) delivers an approximate$\rho=2$ $(1+ \frac{1}{2\lfloor 3\beta/2\rfloor+1}$

to the(3))$( \leq\frac{8}{3})$101
be a vector obtained by algorithm DOMINATE(f). We have already observed
Proof: Let
to instance $(G, b, \dashv\infty, w)$ . We show that is a -approximate solution.
that is abe afor $(G, b, +\infty, w)$ . Let
We denote by OPT the minimum cost of) contains a minimum cost
vector computed in Step 1 of DOMINATE(/). Since EDS(G ,OPT. By Lemma 1 vector $2x$ ’ satisfies conditions (c) and (d), it holds. Since $b(e)\geq\beta$ for all $e\in E$ such that $b(e)\neq 0_{2}$ we see that $d_{iB}*(v)\geq\beta$for.
$d_{x}*(v)=0$
holds
for each $v\in V$ . Therefore, from Lemma 2, we have
or
over
all
vectorsinminimum
cost
outputsasolutionofthe
DOMINATE(/)
algorithm
Since, from which it follows, we have, as requlred.
$\overline{x}\in \mathbb{Z}_{+}^{E}$$\overline{x}$$(b, +\infty)- \mathrm{E}\mathrm{D}\mathrm{S}$$\overline{x}$$x^{*}\in \mathbb{R}_{+}^{E}$$\mathrm{a}(b, +\infty)- \mathrm{E}\mathrm{D}\mathrm{S}$$b,$ $+\infty$$w^{T}x^{*}\leq$$(b, +\infty)- \mathrm{E}\mathrm{D}\mathrm{S}$$\mathrm{E}\mathrm{C}(G, d_{x^{*}}, +\infty)$$\rho x\in \mathrm{E}\mathrm{C}(G, d_{x^{*}}, +\infty)$$\overline{x}$$\mathrm{E}\mathrm{C}(G, d_{x}*, +\infty)$$w^{T}\overline{x}\leq\rho w^{T}x^{*}$$\square$$w^{T}\overline{x}\leq \mathrm{p}\mathrm{O}\mathrm{P}\mathrm{T}$In addition, algorithm DOMINATE(f) achieves a better approximation factor in some special
cases. We introduce some results (but omit the proofs).
that $\beta=\min_{e\in E}b(e)\geq 1$ , algorithm DOMINATE(f)Theorem 2. For a demand vectora factor ofwithinsolutiona
costdelivers an approximateof$b\in \mathbb{Z}_{+}^{E}such$$\rho=2(1+\frac{1}{4\beta+1})(\leq\frac{12}{5})$to the $(b, +\infty)- EDS$ problem.

Theorem 3. DOMINATE(f) is a 2-approximation algorithm for the (b,$+\infty)- EDS$ problera inbipartite graphs.
Theorem 4. Suppose that $b(e)=\beta$ for all e $\in E$ . Then algorithm DOMINATE(/) ) delivers an.
approximate solution of a cost within a factor of 2.1 if $\beta=1$ or a factor of 2 if$\beta\geq 2$

Before closing this section, we mention the analysis shown in [15] for the case where takes
to be an appropriate value. Let
finite values for some edges. In this case, we need to set
and be the factor in Theorem 2 (resp., in Theorem 3) if thegraph is not bipartite (resp., the graph is bipartite). If $f\geq\rho$ , we can prove that
, where $x\in$ EDS(G, , ) and $\rho=2(1+1/\beta)$ (the proof is similar withthat of Lemmas 1 and 2). Then, algorithm DOMINATE(f) achieves the approximation factor of
because of the following reasons; The cost of output edges in $E’$ is bounded as
$c$

$f$

$\mathit{7}\mathit{3}=\min_{U\subseteq V,F\subseteq\delta(U)-E’}dx(U)-c\langle F\rangle$$\rho$$\rho x\langle E-E’\rangle\in$$b$$\mathrm{E}\mathrm{C}(\mathrm{G}, =(V, E-E’), d_{x}, c)$

$c$

$f$

$w\langle E’\rangle^{T}\overline{x}\langle E’\rangle\leq w\langle E’\rangle^{T}c(E’\rangle<fw\langle E’\rangle^{T}x^{*}\langle E’\rangle$.

With regard to edges in $E-E’$ , it holds$w\langle E-E’\rangle^{T}\overline{x}\langle E-E’\rangle\leq\rho w\langle E-E’\rangle^{T}x^{*}\langle E-E’\rangle$

from the above-mentioned relation. Hence, it holds$w^{T}\overline{x}=w\langle E’\rangle^{T}\overline{x}\langle E’\rangle+w\langle E-E’\rangle^{T}\overline{x}\langle E-E’\rangle<fw^{T}x^{*}\leq f\mathrm{O}\mathrm{P}\mathrm{T}$,where OPT denotes the cost of the optimal solution. Notice that depends on . As we, we can obtain better approximation factor. Especially,
make smaller with keeping
DOMINATE(8/3) is a 8/3-approximation algorithm.
Theorem 5. DOMINATE(8/3) is a 8/3-approximation algorithm for the (b,$c)- EDS$ problem.
$\rho$

$f$

$f$

$f$

$\geq\rho$

We also obtain the same results described in Theorems 3 and 4.
Theorem 6. DOMINATE(2) is a 2-approximation algorithm for the (b,$c)- EDS$ problem in bipartite graphs.

102

4

Hyperedge dominating set problem

We discuss the hypergraph version of the edge dominating set problem. The following result isalso shown in [15].
, the problem is formulated as
Given a hypergraph $=(V, E)$ and a cost vector$Jif$$w\in \mathbb{Q}_{+}^{E}$

minimizesubject to$w^{T}x$(4)

for each $e\in E$ ,$x\in \mathbb{Z}_{+}^{E}x(\delta(e)).\geq 1$such that $x(\delta(e))\geq 1$ for each $e\in E$ . In addition, we call
An HEDS is defined as a vector
the LP relaxation of the HEDS problem the fractional HEDS problem and its feasible solution afractional HEDS
To obtain an approximate solution to the HEDS problem, we transform a given instance ofthe HEDS problem to an instance of the set cover problem. The set cover problem is consideredis called a set coveras a hypergraph version of the edge cover problem. A hyperedge setof hypergraph $H=(V, E)$ if $\bigcup_{e\in F}e=V$ and the set cover problem asks to find a minimum cost
, the formulation of the set
set cover. Given a hypergraph $H=(V, E)$ and a cost vector
cover problem is given as follows.
$x\in \mathbb{Z}_{+}^{E}$$F\subseteq E$$w\in \mathbb{Q}_{+}^{E}$

minimizesubject to$w^{T}x$for each $v\in V$ ,(5)$x\in \mathbb{Z}_{+}^{E}x(\delta(v)).\geq 1$-hard [9]. Moreover, the LP relaxation of the set coverNote that this problem is proven to be
problem is called the fractional set cover problem and its feasible solution is called a fractional
set cover. It is known that a simple greedy algorithm finds an approximate solution for the set
cover problem, and that the cost of the solution is bounded in terms of the minimum cost of
fractional set cover, as described in the following theorem.
$\mathrm{N}\mathrm{P}$$\mathrm{a}$Theorem 7. $[5, 12]$ Let
be a given cost vector, be a minimum cost fractional set cover$H=(V,
E)$,andbe the maximum size of a hyperedge in H. Then a set cover
hypergraphaforwhose cost is at mostcan be obtained in polynomial time.
$x^{\mathrm{A}}$$w\in \mathbb{Q}_{+}^{E}$$k$$\theta_{k}w^{T}\hat{x}$Since the HEDS problem is a subclass of the set cover problem, the HEDS problem can be
be a given instance of the HEDS
reduced to the set cover problem directly Let $(H=(V, E),$
problem. Construct a hypergraph $H’=(V’, E’)$ such that its vertex set $V’$ consists of vertices
corresponding to its edges $e\in E$ and edge set $E’$ consists of $e_{e}’=\{v_{e}’,/|e’\in\delta(e)\}$ corresponding
is set to be $w(e)$ . Then, it is easy to see that a setto. A component of the cost vector
$(H,
w)$
$(H’,
w’)$
gives an HEDS forof same cost and vice versa. Let be the maximum
cover forfor all $e\in E$ , where $d=O(|V|^{k})$size of a hyperedge in $E’$ , i.e., the maximum size of$H$holds for the maximum size of a hyperedge in . By Theorem 7, this direct reduction gives a-approximation algorithm for the HEDS problem. Note that $\theta_{d}=O(k \log|V|)$ .
In algorithm HYPER described in Algorithm 2, an instance of the HEDS problem is transformed into an instance of the set cover problem. To prove that the approximation factor of
obtained in Step 1, vector
by using Theorem 7 we show that for a vector
HYPER isis a fractional set cover to $(H_{x}*, w’)$ .
$w\rangle$$v_{e}’$$w’(e_{e}’)$$\delta(e)$$d$$\delta(e)$$k$$\theta_{d}$$x^{*}$$k\theta_{k}$$k’x^{*}$

Lemma 3. Let x
be a fractional HEDS for a hypergraph H $=(V,E)$ , $H_{x}=(V’, E’)$ bea hypergraph obtained in Step 3 of HYPER from x and k be the maximum hyperedge size of H.
Then vector.
is a fractional set cover for$\in \mathbb{R}^{E}$$kx\langle E’\rangle\in \mathbb{R}^{E^{J}}$$H_{x}$

103

Algorithm 2

HYPER

Input: A hypergraph $H=(V, E)$ and a cost vector
Output: An HEDS for $H$ .

$w\in \mathbb{Q}_{+}^{E}$.

]
to the fractional HEDS problem for $H$ and .
Step 1: Find a minimum cost solution
Step 2: Let $V’:=$ { $v \in V|x^{*}(\delta(v))=\max_{u\in e}x^{*}(\delta(u))$ for some $e\in E$ }, $E’:=\{e\cap V’|e\in E\}$ ,$x^{*}\in$$w$$\mathrm{R}^{E}$.
andis at most
Step 3: Find a set cover for hypergraph $H_{x^{*}}=(V’, E’)$ such thatas an HEDS for $H$ .
minimum cost of a fractional set cover, and output$w’:=w\langle E’\rangle\in \mathbb{Q}_{+}^{E’}$$w^{\gamma T}\overline{x}$$\overline{x}$$\theta_{k}$times the$\overline{x}\langle E\rangle$

Proof: Suppose that $v\in V’$ is a vertex in a hyperedge $e\in E’$ such that $x(\delta(v))\geq x(\delta(u))$ for all,$u\in e$ . Since $\sum_{u\in e}x(\delta(u))\geq x(\delta(e))\geq 1$ , we have $x(\delta(v))\geq 1/k$ . Therefore.
is a fractional set cover forwhich means that$kx\langle E’\rangle(\delta(v))\geq 1$$kx\{E’\rangle$$\in \mathbb{R}^{E’}$$\square$$H_{x}$

Theorem 8. The algorithm HYPER achieves approximation factor ofwhere A is the maximum size of a hyperedge.
Proof: Let $w’(F)$ be the minimum weight of fractional set covers of. Moreover, Lemma 3indicatesalgorithm,

for the HEDS problem,$k\theta k$$H_{x^{*}}$. As described in the. Hence$w’(F)\leq kw^{\prime T}x^{*}\langle E’\rangle$$w^{\prime T}\overline{x}\leq\theta_{k}w’(F)$$w^{\prime T}\overline{x}\leq\theta_{k}w’(\Gamma\leq k\theta_{k}w^{rr}x^{*}\langle E’\rangle=k\theta_{k}w^{T}x^{*}$.

is a lower bound of the optimal
is the cost of solution algorithm outputs andSince
cost, it completes the proof.
Note that the approximation factor $k\theta k=O(k\log k)$ of algorithm HYPER is superior to that
, i.e., $H$ is a dense hypergraph suchof the algorithm obtained from the direct reduction ifthat $d=\Omega(|V|^{k})$ .
$w^{T}x^{*}$$w^{\gamma p}\overline{x}$$\square$$k\theta_{k}<\theta_{d}$5(d,$c)$ -edge cover with degree constraints over subsets

of subsets of ,, a family
Given an undirected graph $G=(V, E)$ , a cost vector
constralnts
degreewithcover, the $(d, c)$ -edge
and capacity vector
demand vector
over subsets is formulated by$V$$S\subseteq 2^{V}$$w\in \mathbb{Q}_{+}^{E}$$\mathrm{a}$$c\in \mathbb{Z}_{+}^{E}$$d\in \mathbb{Z}_{1}^{\mathrm{S}}$minimizesubject to$w^{T}x$$\sum_{v\in S}x(\delta(v))$$\geq d(S)$$\mathrm{x}(\mathrm{e})\leq c(e)$$x\in \mathbb{Z}_{+}^{E}$for eachfor each$S\in \mathrm{S}$

$e$

,

(6)

(; $E$ ,.

Note that if $S=\{\{v\}|v\in V\}$ , then problem (6) is equivalent to the $(d, c)$ -edge cover problem
problem, but(2). If $S=\{\{u, v\}|(u, v)\in E\}$ , then problem (6) seems similar to theconstraint
thefromdifferent$e=(u,v)\in
E$is
its first constraint $x(\delta(u))+x(\delta(v))\geq b(e)$ ori each
vectors
allofdenote the set$x(\delta(e))\geq b(e)$ for the. Letinequalities in (6), i.e., the relaxation of the covering problem. We show that problem (6)approximable by algorithm COVER(f) described Algorithm 3.
$(b, c)- \mathrm{E}\mathrm{D}\mathrm{S}$$x\in \mathbb{R}_{+}^{E}\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\mathrm{f}\gamma \mathrm{i}\mathrm{n}\mathrm{g}$$(b, c)- \mathrm{E}\mathrm{D}\mathrm{S}$$\mathrm{D}\mathrm{C}(G, \mathrm{S}, d, c)$$1\mathrm{s}$

$\ln$

104

$\overline{\frac{\mathrm{A}1\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}3\mathrm{C}\mathrm{O}\mathrm{V}\mathrm{E}\mathrm{R}(f)}{\mathrm{I}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}:\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{m}\mathrm{p}1\mathrm{e}\mathrm{u}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{e}\mathrm{d}}}$, afamily
graph $G=(V, E)$ , acost vector, and a real $f>0$ .
, a capacity vector
of $V$ , a demand vector
feasible to the covering problem (6).
Output: A vector$S\underline{\subseteq}2^{V}$$w\in \mathbb{Q}_{+}^{E}$of subsets$c\in \mathbb{Z}_{+}^{E}$$d\in \mathbb{Z}_{+}^{\mathrm{S}}$$x\in \mathbb{Z}_{+}^{E}$and let it .
over
Step 1: Let $E’:=\emptyset$ . Moreover, find a minimum cost vector, output Unfeasibl\"e.
If, $d(S):=$
Step 2: For each $e\in E$ , $fx^{*}(e)>c(e)$ , then let $\overline{x}(e):=c(e)$ , $E’:=E’\cup$$\in S$ with $e\in E[S]$ , and $d(S)$ $:= \max\{0, d(S)-c(e)\}$$\max\{0, d(S)-2c(e)\}$ for each$x^{*}$$\mathrm{D}\mathrm{C}(G, \mathrm{S}, d, c)$$x^{*}$$\mathrm{E}\mathrm{C}(\mathrm{G}, \mathrm{S}, d, c)=\emptyset$$\{e\}$$S$

for each $S\in S$ with $e\in\delta(S)$ .
Step 3: For each $\in S$ , $d_{x}’*(v, S)$ $:=d(S)$ if $x^{*}(\delta(v)-E’)\geq x^{*}(\delta(u)-E’)$ for all $u\in S$ and$d_{x^{*}}’(v, S):=0$ otherwise.
.
Step 4: For each v
for $G’=(V, E-E’)$ andcover
Step 4: Compute a minimum cost
, and output as a solution to (6).
$S$$\in V,\tilde{d}_{x}*(v):=\mathrm{m}\mathrm{a}\mathrm{x}s\in Sv\in s^{d_{x^{*}}’(v,S)}$$\overline{x}\langle E-E’\rangle$$(\tilde{d}_{x}*, c)\mathrm{c}\mathrm{a}\mathrm{s}\mathrm{e}$$w\langle E-E’\rangle$$\overline{x}$, the vector $v= \arg\max_{u\in S}x^{*}(\delta(u)-E’)$ satisfies. Since, we can see that is a feasible for problem (6). In
which follows, we discuss the approximation factor of COVER(f). It can be derived analogously
to that of algorithm DOMINATE(f). First, let us consider the case of $c(e)=+\infty$ . Notice thatfor any in this case.

For each$S$$\sum_{u\in S}\overline{x}(\delta(u)-E’)\geq$$\in S$$\overline{x}(\delta(v)-E’)\geq\tilde{d}_{x}*(v)\geq d(S)-2c(E[S]\cap E’)-c(\delta(S)\cap E’)$$\overline{x}$$E’)+2\mathrm{x}(\mathrm{E}[\mathrm{S}]\cap E’)+\overline{x}(\delta(S)\cap E’)\geq \mathrm{d}(\mathrm{S})$$E’=\emptyset$$\sum_{u\in S}\overline{x}(\delta(u))\geq\sum_{u\in \mathrm{S}}\overline{x}(\delta(u)-$$f$Lemma 4. Let xand (d) forS, d,, where$\in \mathrm{D}\mathrm{C}(G,$$\mathrm{E}\mathrm{C}(G,\tilde{d}_{x}, 1- 00)$$+\infty)$

and h$\tilde{d}_{x}\in \mathbb{Z}_{+}^{V}$. Then vector hx satisfies conditions (c)is a vector obtained from x in Step 4 of COVER(/).
$= \max_{S\in \mathrm{S}}|S|$. We show that $hx$ satisfies
then $hx(\delta(v))\geq$
for each $v\in V$ . Let be a vertex in $V$ . If(b), i.e.,$\tilde{d}_{x}(v)>0$ .
$S\in
S$
such
that $x(\delta(v))\geq$
existsasubsetThereholds. Then assume$\tilde{d}_{x}(v)=d_{x}’(v,S)$$=d(S)$ . From this inequality and the condition
holds for all $u\in S$ and, we have, for

Proof;

Since$x\in \mathbb{R}_{+}^{E-E’}$, vector $hx$ satisfies (a) for$hx(\delta(v))\geq\tilde{d}_{x}(v)$$\mathrm{E}\mathrm{C}(G,\tilde{d}_{x}, +\infty)$$\tilde{d}_{x}(v)=0_{\dot{J}}$$v$$0=\tilde{d}_{x}(v)$$x(\delta(u)\}$$\sum_{u\in S}x(\delta(u))\geq d(S\mathrm{I}$$\mathrm{E}\mathrm{C}(\mathrm{G}, S, d, +\infty)$$hx( \delta(v))\geq|S|x(\delta(v))\geq\sum_{u\in \mathit{3}}x(\delta(u))\geq d(S)$This implies that $hx$ satisfies (b) for$\mathrm{E}\mathrm{C}(G’,\tilde{d}_{x}, +\infty)$$=d_{x}’(v, S)$$=\tilde{d}_{x}(v)$.

.

$\square$Lemmas 2 and 4 indicate the following theorem.
Theorem 9. Algorithm COVER(/) achieves the approximation factor of$h$. $(1+ \frac{1}{2\lfloor 3\beta/2\rfloor+1})(\leq\frac{4}{3}h)$for problem (6) with $c(e)=+\infty$ , where $h= \max\{|S||S\in \mathrm{S}\}$ and$\beta=\mathrm{m}\mathrm{i}\mathrm{n}s\in \mathrm{S},b(s)\neq 0^{b(S)}$,105
Proof: Let $y=h$ . $(1+(2\lfloor 3\beta/2\rfloor+1)^{--1})x^{*}$ . By Lemmas 2 and 4, it holds. Since the algorithm
which implies that $w^{T}y$ is at least the minimum cost overandis a lower bound of the optim ai
outputs a vector of minimum cost overcost, the proof is completed.
For the case where $c(e)$ is finite, we can also derive an approximation factor as in the
problem. In the worst case, it achieves the factor of (4/3)h.

$y\in \mathrm{E}\mathrm{C}(G,\tilde{d}_{x}, +\infty)_{1}$$\mathrm{E}\mathrm{C}(G,\tilde{d}_{x}, +\infty)$$\mathrm{E}\mathrm{C}(G,\tilde{d}_{x}, +\infty)$$w^{T}x^{*}$$\square$$(b, c)- \mathrm{E}\mathrm{D}\mathrm{S}$6

The (b,$c)$ -edge packing problem

6.1(b,$c)$ -edge packing, (d,$c)$ -matching and polytopes

We now consider the edge packing problem, where $b(e)$ denotes an upper bound on the numberof edges dominating . The objective is to maximize the sum of costs of chosen edges. Formallythe problem is described as follows.
maximizesubject to $x(\delta(e))\leq b(e)$ for each $e\in E$ ,(7)$x(e)\leq c(e)$for each $e\in E$ ,$e$$w^{T}x$$x\in \mathbb{Z}_{+}^{B}$.

We call a feasible solution of this problem a $(b, c)$ -edge packing, and this problem the $(b, c)$ edge
packing problem.
satisfying
be the set of vectors
Let$x\in \mathbb{R}_{+}^{E}$$\mathrm{E}\mathrm{P}(G, b, c)$

(a)
(b)

$0\leq x(e)\leq c(e)$$x(\delta\{e))\leq b(e)$for each $e\in E$ ,for each $e\in E$ .

represents the feasible region of the linear programming problem obtained
Observe that
contains all feasible
relaxingby(7)
its integer constraints. Althoughproblemfrominclude any integermay
notregionoverthesolutionsalloptimal
the
set
of
(7),
of
solutionssolut ions .
To approximate the $(b, c)$ -edge packing problem, we consider the matching problem, which isone of the well-studied problems in the combinatorial optimization. This problem is generalized
into the following capacitated -matching problem.
maximizesubject to $x(\delta(v))\leq d(v)$ for each $v\in E$ ,(8)
for each $e\in E$ ,,$\mathrm{E}\mathrm{P}(G, b, \mathrm{c})$$\mathrm{E}\mathrm{P}(G, b, c)$$d$$w^{T}x$$\mathrm{x}(\mathrm{e})\leq c(e)$$x\in \mathbb{Z}_{+}^{E}$

are given capacities. In the following, we call the capacitated dand
matching problem with capacities and the $(d, c)$ matching problem and its feasible solution a$(d, c)$ -matching. Note that in the $(d, c)$ -matching problem, the second constraint $x(e)\leq c(e)$ is
not essential because all instances of the $(d, c)$ -matching problem can be reduced to a special caseof $(d, c)$ -matching problem where $c=+\infty[16]$ .
It is known that the $(d, c)$ -matching problem can be solved in strongly polynomial time $[1, 16]$ .
such that
Let MA(G, , ) be the set of vectors

where$c\in \mathbb{Z}_{+}^{E}$$d\in \mathbb{Z}_{+}^{V}$

$d$

$d$

$c$

$x\in \mathbb{R}_{+}^{E}$

$c$

(c)
(d)

(e)

$0\leq \mathrm{x}(\mathrm{e})\leq c(e)$$0\leq \mathrm{x}(6(\mathrm{v}))\leq d(v)$$x(E[U])+x(F) \leq\lfloor\frac{d\{U)+c(F]}{2}\rfloor$

for each $e\in E$ ,for each $v\in V$ ,$\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}d(U)+c(F)\mathrm{o}\mathrm{d}\mathrm{d}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{c}\mathrm{h}U\subseteq V,F^{\Gamma}\simeq\delta.(U)$108

MA(G, , ) is an integer polytope, whose all extreme points are represented by integer vectors [17].
Since every integer vector satisfying conditions (c) and (d) is a ( , -matching in , maximizing$w^{T}x$over the polytope MA(G, , ) is essentially equivalent to solving problem (8). Note that,in the $(b, c)$ -edge packing problem, is an $|E|$ -dimensional vector, while is defined as-matching problem.
dimensional vector in the
$d$

$c$

$d$

$d$

$G$

$c\rangle$

$c$

$d$

$b$

$\mathrm{a}|V|-$$(\mathrm{d}\mathrm{t}c)$6.2

Approximation algorithm

To construct an approximate solution to a given instance $(G, b, c, w)$ of the $(b, c)$ -edge packing
problem, we solve an instance $(G, d, c, w)$ of the $(d, c)$ -matching problem. The capacity vector
will be defined so that a $(d, c)$ -matching is also a $(b, c)$ -edge packing in . The algorithm is
described in Algorithm 4.
$G$

$d$

PACK

Algorithm 4

Input: An instance $(G, b, c, w)$ of the $(b, c)$ -edge packing problem.
Output: A $(b, c)$ -edge packing.

Step 1: For each $e=(u, v)\in E$ , $b’(u, e):=\lfloor b(e)/2\rfloor$ and $b’(v,e):=\lceil b(e)/2\rceil$ .
Step 2: For each $v\in V$ , $d(v):= \min_{e\in\delta(v)}b’(v, e)$ .
for the graph and the cost vector
Step 3: Compute a maximum cost ( , -matching, and output as a $(b, c)$ -edge packing.
$d$

$w$

$G$

$\overline{x}\in \mathbb{Z}_{+}^{E}$$c\rangle$$\overline{x}$) are $(b, c)$ -edge packings because
satisfying (c) and (d) of MA(G,$x(\delta(e))\leq x(\delta(u))\dashv- x(\delta(v))\leq d(u)+d(v)\leq b(e)$ hold. In the following, we analyze the approximation factor of algorithm PACK.

Integer vectors

Lemma 5. Let
Vector$x\in \mathbb{Z}^{E}$$d,$$x\in \mathrm{E}\mathrm{P}(G, b, c)$

, and

$c$

be a vector obtrmnea in Step 2 of algorithm PACK.

$d\in \mathbb{Z}_{+}^{V}$$\frac{1}{2}(1-\frac{1}{\beta_{1}})x$

if there is an edge with odd $b(e)$$\frac{1}{2}x$otherwise$x’=\{$

satisfies conditions (c) and (d) for MA(G, , ), where
$d$

$c$

$\beta_{1}=\min_{e\in E,b(e)xs}$

odd $b(e)$ .

Proof: Since
satisfies $0\leq x(e)\leq c(e)$ for each $e\in E$ , it is immediate to see thatsatisfies (c) for MA $(G, d, c)$ . Then, we show that $x’(\delta(v))\leq d(v)$ holds for each $v\in V$ .
Let $v\in V$ . There is an edge $e=(u, v)\in E$ such that $d(v)=b’(v, e)$ . Note that $x(\delta(v))\leq$$x(\delta(e))\leq b(e)$ hold by (b) for EDS(G, , ). If $b’(v, e)=\lceil b(e)/2\rceil$ , then it holds$x\in \mathrm{E}\mathrm{P}(G,b, c)$

$x’$

$b$

$c$

$x’( \delta(v))\leq\frac{1}{2}x(\delta(v))\leq\frac{x(\delta(e))}{2}\leq\frac{b(e)}{2}\leq \mathrm{r}\frac{b(e)}{2}\rceil=d(v)$,This implies thatsatisfies (d) in MA(G, , ),Consider the other case, $b’(v, e)<\lceil b(e)/2\rceil$ , i.e.,
is odd and $b’(v, e)=\lfloor b(e)/2\rfloor$ . Since$x(\delta(v))\leq b(e)$ and $d(v)=b’(v, e)=(b(e)-1)/2$ , we have$x’(\delta(v))$

$d$

$c$

$\mathrm{f}\mathrm{c}(\mathrm{e})$$\frac{d(v)}{x(\delta(v))}\geq\frac{b(e)-1}{2b(uv)}=\frac{1}{2}-\frac{1}{2b(e)}$

.

107

Prom the assumption,$b(e)\geq\beta_{1}$. Then,$\frac{1}{2}-\frac{1}{2b(e)}\geq\frac{1}{2}(1-\frac{1}{\beta_{1}})$

Therefore $x’(\delta(v))$ satisfies
Lemma 6. Let
vector$x\in \mathbb{R}_{+}^{E}$$\langle$$\mathrm{d})$.

for MA(G, , ).
$d$$\square$$c$satisfy (c) and (d) for MA $(G, d, c)$ and$\beta_{2}=\lfloor\min_{e\in E,b(e)\neq 0}b(e)/2\rfloor$. Then$(1- \frac{1}{2\lfloor 3\beta_{2}/2\rfloor+1})x$

satisfies (e) for$\mathrm{M}\mathrm{A}(G_{1}d,c)$,

be a nonempty subset of
Proof: Letsuffices to show that
$U$

$V$

, and $F$ be a subset of$x(E[U])+x(F) \leq\lfloor\frac{d(U)+c(F)}{2}\rfloor$$\delta(U)$which can be empty. It.

We can assume that contains no vertices such that $d(v)=0$ (i.e., $x(\delta(v))=0$ ) because theabove inequality for such and any is obtained from the one for $U-\{v\}$ and $F-\delta(v)$ .
), it holds
Since satisfies (d) for MA(G,
$U$

$v$

$F$

$U$

$d,$

$x$

$c$

$2x(E[U])+x( \delta(U))=\sum_{v\in U}x(\delta(v))\leq\sum_{v\in U}d(v)$$=d(U)$ ,from which we have$x(E[U]) \leq\frac{d(U)-x(\delta(U))}{2}$.

$\langle$

9)

From (c), $x(F)= \sum_{e\in F}x(e)\leq\sum_{e\epsilon F}\mathrm{b}(\mathrm{e})=c(F)$ holds. From this inequality and (9), we have$x(E[U])+x(F) \leq\frac{d(U)+c(F)-(x(\delta(U))-x(F))}{\underline{9}}$Since$x(\delta(U\})$-$\mathrm{x}(\mathrm{F})\geq 0$

holds by$F\subseteq\delta(U)$.

, it holds$x(E[U])+x(F) \leq\frac{d(U)+c(F)}{2}$

.

(10)

The gap between $(d(U)+c(F))/2$ and $\lfloor(d(U)+c(F))/2\rfloor$ depends on the parity of $d(U)+c(F)$ .
Therefore we only have to consider the case where $d(U)+c(F)$ takes a minimum odd value. We
consider the following three sub case

Case 1: $|U|=1$ . Let $U=\{v\}$ . Then $x(E[U])=0$ . Therefore the left hand side of (e) equals to. Since $d(U)+c(F)=d(v)+c(F)$ is assumed to be odd, it holds $d(v)\neq c(F)$ , which implies$d(u)+c(F) \geq 2\min\{d(u), c(F)\}+1$ . From (c), $x(F)$ $\leq c(F)$ holds. Moreover, $x(F)$$d(v)$ holds since. Therefore we have$\mathrm{x}(\mathrm{F})$$\leq x(\delta(v))\leq$$F\underline{\mathrm{C}}\delta(v)$$x(F) \leq\min\{c(F), d(v)\}\leq\frac{d(U)+c(F)-1}{2}=\lfloor\frac{d(U)+c(F)}{\underline{9}}\rfloor$.

108
Let $U=\{v_{1}, v_{2}\}$ , $F_{1}=\delta(v_{1})\cap F$ , and $F_{2}=\delta(v_{2})\cap F$ . Then $d(U)+c(F)=$$+c(F_{2})$ . Prom the facts that
that

Case 2: $|U|=2$ .

$d(v_{1})$ $+d(v_{2})+c(\Gamma_{1}^{\{})$$E[U]\cup F$$\delta(v_{1})$$\cup F_{2}\supseteq E[U]\cup\Gamma\prec \mathrm{a}\mathrm{n}\mathrm{d}$$\delta(v2)\cup F_{1}\supseteq$, we have.

(11)$x(E[U])+x(F) \leq\min\{x(\delta(v_{1}))+x(F_{2}),x(\delta(v_{2}))+x(F_{1})\}$

from (d). Moreover, we have $x(F_{1})\leq c(F_{1})$andIt holds thatand $x(F_{2})\leq c(F_{2})$ from (c). These relations and Inequality (11) lead to$x(\delta(v_{2}))\leq d(v_{2})$$x(\delta(v_{1}))\leq d(v_{1})$$x(E[U])+x(F) \leq\min\{d(\delta(v_{1}))+c(F_{2}), d(\delta(v_{2}))+c(F_{1})\}$

.

(12)

On the other hand; since $d(U)+c(F)$ is assumed to be odd, it holds $d(\delta(v_{1}))+c(F_{2})\neq d(\delta(v_{2}))+$, which implies that$c(F_{1})$$\min\{d(\delta(v_{1}))+c(F_{2}), d(\delta(v_{2}))+c(F_{1})\}\leq\lfloor\frac{d(U\}+c(F)}{2}\rfloor$

.

(13)

Prom (12) and (13), we have (e) for MA(G, , ).
$d$

$c$

Case 3: $|U|\geq 3$ . Since $b(e) \geq\min_{e\in E,b(e)\neq 0}b(e)$ for all $e\in E$ , it holds
Hence $d(U)\geq 3\beta_{2}$ . Considering that $d(U)+c(F)$ is odd, we have$d(U)+c(F) \geq 2\lfloor\frac{3\beta_{2}}{2}\rfloor+1$$d(v)\geq\beta_{2}$for all $v\in V$ .

.

Rrom (10) and the above inequality,$\frac{\lfloor(d(U)+c(F))/2\rfloor}{x(E[U])+x(F)}\geq 1-\frac{1}{d(U)+c(F)}\geq 1-\frac{1}{2\lfloor 3\beta_{2}/\underline{?}\rfloor+1}$.

This completes the proof of the lemma,$\square$

Theorem 10. Let be a vector constructed in Step 2 of algorithm PACK. Then MA(G, ,-approximate solutions of theis a polyhedron whose maimum cost extreme points are$(b, c)$ -edge packing problem
for a graph , where
$d$

$d$

$c\rangle$$\rho(\beta_{1}, \beta_{2})$$G$$1- \frac{1}{\beta_{1}})$.

$(1- \frac{1}{2\lfloor 3\beta_{2}/2\rfloor+1})$\’if there is an $ed9e$$e$with odd $b(e)$ ,$\rho(\beta_{1},\beta_{2})=\{_{\frac{}{2}}^{\frac{1}{21}}\xi$

otherwise,$1- \frac{1}{2\mathrm{L}3\beta_{2}/2\rfloor_{\mathrm{T}^{\mathrm{I}}}1})$$\beta_{1}=\min_{e\in E,b(e)is}$ $odd$ $b(e)$an$d \beta_{2}=\lfloor\min_{e\in E,b(e)\neq 0}b(e)/2\rfloor$.

in MA(G, $d,c$) is a $(b, c)$ -edge
Proof: We have already observed that an integer vector
packing. Since MA(G, , ) is an integer polytope, every extreme point is a $(b, c)$ -edge packing.
Denote by OPT the maximum cost of a solution to problem (7) with $(G, b, c, w)$ . In what
follows, we show that
holds, where is a maximum cost extreme point of.
MA(G, , ). Let
for the cost
be a vector of the maximum cost
Becausecontains an optimal solution to problem (7), it holds$x\in \mathbb{Z}_{+}^{E}$

$d$

$c$

$f(\beta_{1}, \beta_{2})\mathrm{O}\mathrm{P}\mathrm{T}\leq w^{T}\overline{x}$

$d$

$c$

$\overline{x}$$w^{T}x^{*}$$x^{*}\in \mathrm{E}\mathrm{P}(G,b, c)$$\mathrm{E}\mathrm{P}(G, b, c)$

OPT$\leq w^{T}x^{*}$.

$w\in \mathbb{Q}_{+}^{E}$

I09

By Lemmas 5 and 6, we can see that vectorofover MA(G, , ), it holds$d$$w^{T}\overline{x}$’$\rho(\beta_{1},\beta_{2})x$

belongs to MA(G, , ) . By the maximal ly
$d$

$c$

$c$

$\rho(\beta_{1},\beta_{2})w^{T}x^{*}\leq w^{T}\overline{x}$.

From the above two inequalities, we have$p(\beta_{1}, \beta_{2})\mathrm{O}\mathrm{P}\mathrm{T}\leq w^{T}\overline{x}$,as required,
The above theorem is equivalent to saying that the approximation factor of algorithm PACK is
because algorithm PACK outputs a maximum cost vector over the polyhedron MA(G, , ).
$\square$$d$$\rho(\beta_{1},\beta_{2})$Corollary 1. Let $\beta_{1}=\min_{e\in E,b(e)\mathrm{z}sodd}b(e)$ and.
mation factor of algorithm PACK is$\rho(\beta_{1},$$\beta_{2}=\lfloor\min_{e\in E,b(e)\neq 0}b(e)/2\rfloor$$c$. Then the approxi-$\beta_{2}\rangle$

if $E$ contains an edge such that $b(e)=1$ . We know that this problem
Note thatcannot be approximated within a constant factor in the case where $b(e)=1$ for all $e\in E[8]$ .
andHence it would be appropriate to assume that $b(e)=0$ or $b(e)\geq 2$ for all$\rho(\beta)=2/9$ holds.
$=1$
,
and
case,
where
worst
the
Particularlyin.
$\rho(\beta_{1}, \beta_{2})=0$$e$$e\in E(\mathrm{i}.\mathrm{e}.,$$\beta_{2}\geq 1)$$\beta_{1}=3$$\beta_{1}\geq 3$$\beta \mathrm{z}$Acknowledgment
This research was partially supported by the Scientific Grant-in-Aid from Ministry of Education,
Culture, Sports, Science and Technology of Japan.

References[1] R. P. Anstee, A polynomial algorithm for &machings: an alternative approach, Information
Processing Letters, vol. 24, pp. 153-157, 1987.
[2] E. M. Arkin, M, M. Halld6rsson, and R. Hassin, Approximating the tree and tour cover ofgraph, Information Processing Letters, vol. 47, pp. 275-282, 1987.

-approximation algorithm for a gen[3] R. Carr, T. Fujito, G. Konjevod, and 0. Parekh, Aeralization of the weighted edge-dominating set problem, In Proceedings of the Eighth ESA,
pp. 132-142, 2000,$2 \frac{1}{10}$[4] M. Chlebik and J. Chlebikova, Approximation hardness of minimum edge dominating set andminimum maximal matching, In Proceedings of the 14th Annual International Symposium on
Algorithms and Computation (ISAA C2003), pp. 41S-424, 2003.

[5] V. Chv\’atal, A greedy heuristics for the set covering problem, Mathematics of Operations
Research, vol. 4, PP. 233-235, 1979.
[6] T. Fujito and H. Nagamochi, A 2-approximation algorithm for the minimum weight
dominating set problem, Discrete Applied Mathmaiics, vol. 118, pP. 199-207, 2002.

$\mathrm{e}\mathrm{d}_{b}\sigma \mathrm{e}$[7] T. Fukunaga and H. Nagamochi, Approximation algorithms for the -edge dominating set
problem and its related problems, In Proceedings of the Eleventh International Computing
and Combinatorics Conference (COCOON 2005), LNCS 3595, pp. 747-756, Kunming, China,
August 16-192005

110[8] T. Fukunaga and H. Nagamochi, Edge packing problem with edge capacity constraints, In
Proceedings of the 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 69-75, Budapest, Hungary, June 3-62005.
[9] M. R. Garey and D. S. Johnson, Computers and Intractability; a Guide to the Theory of-cornpleteness, W. H. Freeman&Co., 1979.

$NP$[10] J. Horton and K. Kilakos, Minimum edge dominating sets, SIAM Journal on Discrete Mathematics, vol. 6, pp. 375-387, 1993.
[11] J. Konemann, G. Konjevod, O. Parekh, and A. Sinha; Improved approximations for tour andtree covers, Algorithm,ica, vol. 38, pp. 441-449, 2004.
[12] L. Lovasz, On the ratio of optim al integral and fractional covers, Discrete Mathematics,
vol. 13, Pp. 383-390, 1975.
[13] S. Mitchell and S. Hedetniemi, Edge domination in trees, In Proceedings of 8th Southeastern, pp. 489-509, 1979.
Conference on Combinatorics, Graph Theory, and$Comput\acute{\iota}ng$[14] K. G. Murty and C. Perin, A 1-matching blossom-type algorithm for edge covering problems,
Networks, vol. 12, pp. 379-391, 1982.
[15] O. Parekh, Polyhedral techniques for graphic covering problems, PhD thesis, Carnegie Mellon
University, 2002.
[16] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003.

[17] A. Srinivasan, K. Madhukar, P. Nagavamsi, C. P. Rangan, and M-S. Chang, Edge domination
on bipartite permutation graphs and contriangulated graphs, Information Processing Letters,
vol. 56, pp. 165-171, 1995.
[18] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM Journal on Applied
Mathematics, vol. 38, pp. 364-372, 1980