数理解析研究所講究録 1325 巻 2003 年 181-184181
平均次数の高い VC-PM の近似アルゴリズム
築地 立家竹内 元気
名古屋大学情報文化学部

名古屋大学人間情報学研究科

n9932@sis.nagoya-u.ac.jp

tsukiji@math.human.nagoya-u.ac.jp

1Introduction

ここで完全マッチングとは、 グラフ $G$ の全ての点を、2 点ずつ辺で向かい合わせる (マッチングさせる) 辺の部

最小頂点被覆問題とは、 与えられた無向グラフ $G=$$(V, E)$ に対して、頂点数が最小となる $G$ の頂点被覆を求める問題である。 -この問題は、取り得る解の集合から最もよい解を選び出す最適化問題のうち、 最小の解を探すことを日的とする最小化問題である。 また最小頂点被覆困難に属することが知られている。最適化問
問題はでない限り、 最良の解題が困難な場合は、$\mathrm{N}\mathrm{P}$$\mathrm{P}=\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{P}$をみつける多項式時間アルゴリズムは存在しない。 したがって、最小頂点被覆問題に対して最良の解を求める多項式時間アルゴリズムは存在しないという立場で、 この問題の近似アルゴリズムを考えることにする。 ただし、本稿では入力されるグラフを完全マッチングを持つグラフに限定している。入カグラフが完全マッチングを持つグラフに限定されている最小頂点被覆問題は、 VC-PMとよばれる。

Chen と Kanj [2] は VC-PM において近似度 が得ら$r$れるならば、一般のグラフに対しては近似度 $(r+2)/2$ が得られることを示している。また、 VC-PM の近似アルゴを求めた ( はリズムの近似度については、 1069+0平均次数) 。そして、今村と岩 ff [1] が Chen と Kanj のアルゴリズムを改良し、$0.0138\overline{d}+1.441$ (triangle-free の場合) の 3 つの近似度を示した。
本稿では、平均次数が高い場合を考える。そこで、 まず今村と岩間のアルゴリズムを解析して、平均次数が任$.069\overline{d}$分集合である。 ここで次の $G(V’)$ と $N_{G}(v)$ の定義もしておく。 $G=(V, E)$ の頂点部分集合 $V’$ に対して、 誘導
部分グラフ $G(V’)$ とは、 $E’=\{(u, v)\in E|u, v\in V’\}$ とした時の $G=(V’, E’)$ のことである。 また、 $G=(V, E)$において $v\in V$ の近傍 $N_{G}(v)$ とは、 に隣接する頂点集合 $\{u|(u, v)\in E\}$ のことをいう。以下ではグラフ $G$ の辺の本数を $m$ とする。
頂点数を
$v$

$n_{\text{、}}$

3

今村と岩間の近似アルゴリズム

この節では Chen と Kanj の近似アルゴリズムを応用した今村と岩間の近似アルゴリズム [1] の概要を紹介する。人力するグラフ $G=(V, E)$ は完全マツチング $M$ を持つものとする。人力されたグラフ $G$ から任意の頂点を、任意の辺 $(u, v)$ に対して節に対して変数を、 任意のマッチング辺 $(u, v)$ に対して節を定義する。
対応させ、 次のような論理式$x_{v}$$v$$(x_{u}\vee x_{v})$$(\overline{x}_{u}\vee\overline{x}_{v})$を$F_{G}$$\overline{d}$$F_{G}=\wedge(x_{u}\vee x_{v})\wedge\Lambda(\overline{x}_{u}\vee\overline{x}_{v})(u,v)\in E(u,v)\in M$$0.0230\overline{d}+1.378_{\text{、}}0.0115\overline{d}+1.534_{\text{、}}$

意に固定された時にも近似度を抑えられることを示した。
さらに Opt 解のサイズを評価することにより、平均次数が 20 から 30 程度 (正確には 20 . $16<\overline{d}<31.75$ ) の場合に、今村と岩間のアルゴリズを解析した場合の近似度を改良することができた。その近似度は、 16010+0$.0074\overline{d}$となった。の形の形の節は positiveのをした節は negative clause と呼ばれる。論理式
positive clause には各々 1 の、 negative clause には各々$(x_{u}\vee x_{v})$$\mathrm{c}1\mathrm{a}\mathrm{u}\mathrm{s}\mathrm{e}_{\text{、}}(\overline{x}_{u}\vee\overline{x}_{v})$$F_{G}$$w(w>1)$ の重みがつけられている。この論理式を MAX
2-SAT の近似アルゴリズムで解き (このアルゴリズムとする。 この割りとする) 、その解をの近似度を当て に対して、 以下のような修正を行う。 FALSE にを TRUE に割り当て直し
割り当てられている変数$\sigma$$r$$\sigma$$x_{v}$が増えるならば、変数て、 もし充足節の重みの和を TRUE に割り当て直す。 このような操作を、 FALSE$|\sigma|$$x_{v}$も TRUE に割り当に割り当てられているどの変数が減少してしまうという重みの和て直された時に、$x_{v}$$|\sigma|$2$\mathrm{V}\mathrm{C}$-PMに極大性を持たせる。 そして、の頂の誘導部 グラフとの和集合をと、点被覆は$G$ の頂点被覆とする。 ここでの極大性からところまで繰り返して$\sigma$$\text{分}$$F_{\sigma}=\{v|\sigma(x_{v})=\mathrm{T}\mathrm{R}\mathrm{U}\mathrm{E}\}$

無向グラフ $G=(V, E)$ が与えられたとき、「グラフ$G$ の任意の辺 $(u, v)\in E$ に対して $u\in C$ または $v\in C$をグラフ $G$ の頂点被覆というが成立」 をみたす
(ここで、 $V$ は頂点集合、 $E$ は辺集合を表わす) 頂点被覆の中で頂点数が最小である $C$ を探す問題を最小頂点被覆問題という。入カグラフ $G$ が完全マツチング $M$ を持つグラフに限定されている最小頂点被覆問題を VC-PM$C\subseteq V$$\text{。}$とよぶ。

$C_{\mathcal{F}}$$G(F_{\sigma})$$F_{\sigma}=\{v|\sigma(x_{v})=\dot{\mathrm{T}}\mathrm{R}\mathrm{U}\mathrm{E}\}$$G(F_{\sigma})$$\sigma$

次数が $w$ 未満のグラフとなっている。次に、今村と岩間の論文で示されている補題を紹介する。
補題 31
覆 $C$ を

$C_{f}$

を$G(F_{\sigma})$の任意の頂点被覆、 $G$ の頂点被$C=\mathcal{T}_{\sigma}\cup C_{f\text{、}}\sigma_{C}$を $\sigma_{C}(x_{v})=TRUE\Leftrightarrow v\in C_{\text{、}}$$\delta=(|\sigma|-|\sigma c|)/n_{\text{、}}\overline{d}=2m/n$と定義する。 このとき以182
4.1下の不等式が成り立つ。

$K_{k+1}$の頂点被覆についての頂点被覆としては $k+1$ 個の点のうち 1 点を残して他の 個の点を選ぶ。 そしてその 個の点をの変化は、 $K_{k+1}$ のTRUE に割り当て直したときの$k(k+1)/2$ 本の辺に対応する positive clause が充足され、また 個の negative clause が非充足になり $k(k+1)$ 減少する。差し引き $k(k+1)/2_{\text{、}}|\sigma|$ は減少する。従って$K_{k+1}$$\frac{|C|}{Opt(G)}\leq 1+\frac{2}{w}\delta+\frac{r-1}{wr}(\overline{d}+w)$

$k$

$k$

$|\sigma|$

ここで、 の値が大きくなるにつれて上の補題の近似度も大きくなってしまうので、 $w=2,3$ の場合に の値$\delta$$\delta$力吠きくても良い近似度が与えられるような別の評価式を与えている。
ここでは $w=3$ の場合の評価式の導き方を書くこと
は次数が 2 以下のグラフとにする。 $w=3$ の時、閉路、 パスからなる。
このグラフは独立頂点、なる。
この場合は最小頂点被覆が容易に求められる。
従って、

$k$

$($残りの頂点数)/(重みの和の減少数) の比は $2/k(k+1)$ となる。

$G(F_{\sigma})$というのも閉路、パスともに一つおきに頂点を選べば良いからである。 このように頂点を選べぽ、充足節の重みへと減少し、またいくつかの頂点からの和がが残る。 この減少数と残る頂点数の関係を調べる。完全を例にとってみると、最小頂点被覆として 3 個グラフの頂点のうち 2 個の頂点を選ぶことになる。 この時の充足節の重みの和の減少数は、 充足される positive clauseの個数が 3 個、非充足となる negative clause (重み 3 がかかっている) の個数が 2 個であることから、充足節の重みの和は 3 減少する。残る頂点数については 1 個である。従って、 残った頂点数と重みの和の減少数との比、(残りの頂点数)/(重みの和の減少数) は 1/3 となる。他$\delta n$$|\sigma c|$$|\sigma|$$K_{3}$の長さの閉路やパスの場合も同様にこのような比を考えのることができるが、 この比の値が最小になるのはから場合となる。従って、 充足節の重みの和個の頂点が残へと減少した場合、 少なくともる。つまり、 $|C|\leq n-\delta n/3$ が言える。 この不等式と$K_{3}$$\mathrm{B}^{*}\mathrm{a}|\sigma|$$|\sigma c|$$\delta n/3$$\delta n$

Opt(G)\geq n/2 から42$K_{k+1}$

以外のグラフの頂点被覆について以外のグラフにおいては次数が よりも小さい点が存在する。 そのような点の中でも最も次数が小さい点をとしその次数を $\mathrm{F}(l<k)$ とおく。 ここで以上と仮定してよい。の各々の点の次数}$k$$K_{k+1}$$v$$\mathrm{h}$$N_{G(\mathcal{F}_{\sigma})}(v)$$l$にの任意の点 に対して、割り当て、 このグラフの頂点被覆の一部とする。 同時にの変化を考える。充足される辺の本数は少な
この時のくとも $l(l+1)/2$ 本はあるので充足される positive clauseの個数は少なくとも $l(l+1)/2$ 個はある。 また非充足となる negative clause の個数は 個であるから、それにともなう重みの和の減少数は $l(k+1)$ であり、従ってこのの減少数を とすれぼ、 $\beta\leq l(2k-l+1)/2$ とな
時のる。 また、 { , N。
} のうち残る頂点の個数は の1 個なので、 (残りの頂点数)/(重みの和の減少数) は

また$x_{u}=\mathrm{T}\mathrm{R}\mathrm{U}\mathrm{E}$$u$$N_{G(\mathcal{F}_{\sigma})}(v)$$|\sigma|$$l$$\beta$$|\sigma|$

$v$

$v$

$(\mathcal{F}_{\sigma})(v)$$1/\beta$となる。 ここで、 $l(2k-l+1)/2<k(k+1)/2(l<k)$と $\beta\leq l(2k-l+1)/2$ から$\frac{1}{k(k+1)/2}<\frac{1}{l(2k-l-1)/2}\leq\frac{1}{\beta}$$\frac{|C|}{Opt(G)}\leq 2-\frac{2\delta}{3}$を出力すが言える。以上のような操作を繰り返してを出力するまでの流れは次のようになる。
る。

また補題 3.1 において $w=3$ とすれば

$C_{\mathcal{F}}$$C_{F}$$\frac{|C|}{Opt(G)}\leq 1+\frac{2}{3}\delta+\frac{r-1}{3r}(\overline{d}+3)$が得られ、$\min(2-\frac{2\delta}{3},$ $1+ \frac{2}{3}\delta+\frac{r-1}{3r}(\overline{d}+3))$$\leq 2-\frac{1}{6r}(3-(r-\mathfrak{y}d\gamma$が言えるから、 このアルゴリズムの近似度は、 2$(1/6r)(3-(r-1)\overline{d})$ とすればよい。 $r=1.0741$ $[3]$ とおくと、 近似度 $0.0115\overline{d}+1.534$ が得られる。

-4

今村と岩間の近似アルゴリズムの解析

4.3$w=k+1$ の場合の近似度の頂点被覆を求めてやると残りの頂点数)/(重みの和の減少数) の値の最小値は $K_{k+1}$の頂点被覆を考えた場合の $2/k(k+1)$ となる。従って、へとから減少すれば、充足節の重みの和が少なくとも $(2\delta n)/k(k+1)$ 個の頂点が の頂点被覆に選ぼれないで残る。従って $|C|\leq n-2\delta n/k(k+1)$ が或以上のようにして

この節では、今村と岩間の近似アルゴリズムにおいてnegative clause にかける重みを $w=k+1(k\geq 1)$ と一般の形でおき、 このアルゴリズムを解析する。重みがは次数が 以下のグラフと$w=k+1$ の場合、なる。
$G(F_{\sigma})$$k$$G(F_{\sigma})$$|\sigma|$$($$|\sigma c|$$\delta n$$G$183183
り立つ。 この不等式と Opt(G) $\geq n/2_{\text{、}}k=w-1$ から$\frac{|C|}{Opt(G)}\leq 2-\frac{4\delta}{(w-1)w}$

また補題 31[1] より$\frac{|C|}{Opt(G)}\leq 1+\frac{2}{w}\delta+\frac{r-1}{wr}(+w)-$

表 1:$P_{1},$ $P_{2},$$\cdots,$$P_{7}$の頂点数などが得られ、$\min(2-\frac{4\delta}{(w-1)w},$$1+ \frac{2}{w}\delta+\frac{r-1}{wr}(\overline{d}+w))$$P_{3}$

るもとのする。黒の頂点はこのアルゴリズムが TRUE に割り当てる頂点、 白の頂点は残す頂点を表す。そして分けられた部分ごとに、頂点の個数、 TRUE に割り当てら$\leq 2-2\frac{(1-r)\overline{d}+w}{r(1+w)w}$が言えるから、近似度は $2-2((1-r)\overline{d}+w)/(r(1+w)w)$とすることができる。 $r=1.0741$ $[3]_{\text{、}}-w=4,5$ とす 6と、 近似度はそれぞれ 1 $628+0.0069d,$ $1.690+0.0046\overline{d}$となる。

5においては、右側の点線が存在すとを示す。 ただしる時は、他の 2 本の点線のうち少なくとも一方は存在すれる頂点数、残る頂点の個数、頂点被覆に最低限必要な点の個数、重みの和の減少数を考える。頂点被覆に必要な頂点数については、 それぞれの部分の外側の部分のグラフの形はどのようになるかは分からないので出る辺を除いて考える。重みの和の減少数についてはそれぞれの部分で考えられる最も大きな減少数を表 1 に書く。

改良したアルゴリズム

ここでは $w=4$ とし、 Opt(G) のサイズの評価を行うことにより近似度を良くすることを考えた。その結果、が 20 から 30 のあたりで、 今村と岩間のアルゴリズムを解析した場合の近似度を改良することができた。
$(V, E)$ から論理式
構或し
以下でも $G$WEIGHTED MAX 2-SAT の近似アルゴリズムで近似ととにに極大性を持たせて $V$ を解 を求め、分けるところまでは同じである。これまでは Opt 解のサイズの評価として Opt(G) $\geq n/2$ という不等式をもちいをさらに $U,W$ とに分割して、た。 ここでは頂点集合に対してグラフ3 つの集合それぞれの場合において頂点被覆に最低限必要な点の個数を考えることによって Opt 解の評価をする。 このようにして評価された Opt 解のサイズの下界を $nv$ とする。 ここで、 $U$ は与えられた完全マッチングのマッチ$\overline{d}$$F_{G}$$=$$\mathcal{T}_{\sigma}$$|\sigma|$$\sigma$$F_{\sigma}$$\mathcal{T}_{\sigma}$$\mathrm{P}2$$G(U)_{\text{、}}G(W)_{\text{、}}$$U_{\text{、}}W_{\text{、}}F_{\sigma}$

P3P4

P6$\mathrm{P}5$$G(F_{\sigma})$の頂点とマッチしている頂点の集合、 つまり} とす{ $u|(u,v)\in M$ かつ$W$(とマッチしていない)
頂点集合、は残りのる。の極大性か
つまり $W=V-F_{\sigma}-U$ とする。 また、らの辺にマツチング辺は存在しない。
ング辺 $(u, v)$ に対して

図 1:

$G(F_{\sigma})$の分割$F_{\sigma}$$U=$$v\in F_{\sigma}$$F_{\sigma}$$|\sigma|$$G(F_{\sigma})$

5.2

得られる評価式を分割して頂点被覆 $Cr$ を出力し、このようにとの和をとることにより $G$ の頂点被覆 $C$ を求める。表とすれば、1 を参考にすると、残る頂点の個数の合計を$G(F_{\sigma})$

5.1$G(F_{\sigma})$$\mathcal{T}_{\sigma}$の分割$n_{\mathcal{F}}$は次数が 3 以下のグラフになる。
$w=4$ の場合
このグラフも閉路やパスや独立頂点に限らず様々な種類のグラフから構或されている。そこで我々のアルゴリズを分割する。
ムでは、 以下の 7 個の場合に即して$G(F_{\sigma})$$G(F_{\sigma})$

それぞれの部分を順に, P7 とし、 その個数をとする。 $P1$ は独立頂点、 P7 は完全グラフはそれぞれ図 2 で描く。 図 2とする.
$P_{1},$ $P_{2},$ $\cdots$$p_{1},p_{2},$ $\cdots,p_{7}$$K_{4}$$P_{2},$ $P_{3},$$\cdots,$$P_{6}$

において、頂点に接続している点線の辺はあってもなくてもよい。 また、辺と辺の間にある点線は、 2 本の実線の辺がつながっていても、 つながっていなくてもよいこnF=pl+7)2+Ps+p4+p5+p6+r。すると $|C|=n-n_{F}$と書ける。 また、 $G(W)$ は完全マツチングをもつので、$G(W)$ を被覆するには少なくとも $|W|/2$ 個の頂点を必要することと、 $G(U)$ を被覆するのに少なくとも OPt(G(U))
個の頂点を必要とすることから、 $G$ の頂点被覆には $nv=$p2+I\sim +2p4+p5+2 胸 $+3p_{7}+|W|/2+Opt(G(U))$
個以上の頂点を必要とする。従って OPt(G) に関してはのだが、 Opt(G(U)) が分か$\max(n/2, n_{V})$ とすればよ$\max(n/2,n\mathrm{v})$も分からない。 よって、 ここらないので、では次の 2 つの評価式を与えておく。 $|C|=n-n\tau$ と$\mathrm{A}\backslash$

184
Opt(G)\geq n/2 から$\text{、}$$\frac{|c|}{Opt(G)}\leq\frac{n-n_{F}}{n/2}$

また $|C|=n-n_{F}$ と Opt(G)$\geq n_{V}$

表 2: 近似度の比較

から、

6$\frac{|C|}{Opt(G)}\leq\frac{n-n_{\mathcal{F}}}{n_{V}}$が得られる。

については、表を次に、充足節の重みの和の減少数
参考にすれぼ、最も大きくなる場合で $3p2+4p\mathrm{a}+5p_{4}+$$\delta n$

3 几 $+5p_{6}+12p_{7}$ である。 これを とおけば、あることと補題 31[l](w $=4$ とする) から$\alpha$$\frac{|C|}{Opt(G)}$$\delta n\leq\alpha$$\leq$$1+ \frac{\delta}{2}+\frac{r-1}{4r}(+4)-$$\leq$$1+ \frac{\alpha}{2n}+\frac{r-1}{4r}(+4)-$

で

今村と岩間のアルゴリズムを重みの設定が 4 以上の場合を解析し、平均次数が任意に固定された時にも近似度を抑えられることを示した。 また、 Opt 解のサイズに依存した新しいアルゴリズムを提案することにより、平均次数が 20 から 30 程度の場合に、今村と岩間のアルゴリズムを解析した場合の近似度を改良することができた。
今回、我々のアルゴリズムの評価は、重みの設定が 4 の場合に絞って行われた。今後は、重みが 5 以上の場合も解析していきたい。
謝辞となる。

一方、我々は次のような $G$ の頂点被覆 $C$ もまた同時W、 に分割するところに考える。 $G$ の頂点をまでは同じである。 $G$ に対する新しい頂点被覆方法としを TRUE に割りの任意の頂点 に対し、て、を FALSE に割当て、 $U$ の任意の頂点 に対しては、と $G(U)$ の頂点被覆 C。とり当て直す。そしての和をとることにより $G$ の頂点被覆 $C$ を求める。 このを求める際には $G(U)$ に対して既存の (多項式時時間で終了する) 頂点被覆アルゴリズムを施す。 この時アルゴリズムが残した頂点の個数を $nu$ とする。 このアルゴリズムの近似度を $s\leq 2$ とすると、 このアルゴリズムの出力する頂点の個数は高々 sOpt(G(U)) である。 よって、少なくとも $|U|-sOpt(G(U))$ 個の頂点を残す。従って、 $n_{U}\geq|U|-sOpt(G(U))$ が言える。 $G$ においては、$|C|=n-n_{U}$ となる。 この等式と Opt(G) $\geq n/2$ から$F_{\sigma\text{、}}U_{\text{、}}$$F_{\sigma}\cup W$$v$$x_{u}$$F_{\sigma}\cup W$$C_{U}$$\frac{|C|}{Opt(G)}\leq$$\frac{n-n_{U}}{n/2}$.

$\frac{|C|}{Opt(G)}\leq\frac{n-n_{U}}{n_{V}}$となる。

これらの事実から、以上 5 つの近似度が得られる。実際は、 これらの近似度のなかで最も小さい比を採用すればよい。
$\min(1+\frac{\alpha}{2n}+\frac{(r-1)(\overline{d}+4)}{4r},$ $\frac{n-n_{F}}{n/2},$ $\frac{n-nr}{n_{V}},$$74\overline{d}$$\frac{n-n_{U}}{n/2},$$\frac{n-n_{U}}{n_{V}})$$(\overline{d}>20.16)$が言えるから、近似度 1 $6010+0.0074\overline{d}(\overline{d}>20.16)$ が得られる。
における近似度の比較を表 2 に示した。近似度 1 が、 今村と岩間のアルゴリズムの解析から求めたでは重みは近似度である。
では重みは 5 としている。近似度 2 は我々が求めた近似$21\leq\overline{d}\leq 31$$21\leq\overline{d}\leq 26$

参考文献[1] T. Imamura, K. Iwama, ” 完全マツチングを持つグ
ラフに対する最小頂点被覆問題の近似解法”, 2002 年
度夏の LA シンポジウム, 5-1-5-9,2 叩 2.

[2] Jianer Chen and Iyad Kanj, ”On approximating minimum vertex cover for graphs with Perfect matching”, International Symposium on AlgO
rithms and Computation, pp. 132-143, 2000.

$$[3] Uriel Feige and Michel X. Goemans, “Approximating the value of two prover proof systems, with aPplications to MAX
and MAX DICUT”,
Prvceedings of the Third Israel Syrnposium on Theory of Computing and Systems, 1995.
$2\mathrm{S}\mathrm{A}\mathrm{T}$また Opt(G) $\geq nv$ とすれぼ$<1.6010+0$

本稿を書くにあたり協力して頂いた築地立家先生には深く感謝しています。

$x_{v}$$u$$–\mathrm{L}-$まとめ$4_{\text{、}}27\leq\overline{d}\leq 31$