1998年反日本オペレーションズ・リサーチ学会 秋季研究発表会 Ⅰ−2
文献賞受賞講演
一般化安定集合問題
＼ 01306430電気通倍大学・m村明久AkillisaTAMURA 撫向グラフは第1の型の辺のみからなる鱒何グラフ と 一般化安定集合閑適を考えましょう。第1型の不等式は 「2？の変数の串々1らが1である」を意味するわけで すが、グラフ的な表現をすれば「第1型の辺の両端点 の高々1つが選ばれる」となります。ここでは、頂点を 選ぶなら対応する変数を1とし、選ばないなら ます。制約条件を満たすように選ばれた頂点の集合は 互いに隣接すること！まなく、このような頂点の集合を 安東集合といいます（独立集合などともいいます）。す なわち、無向グラフが人力の場合の一般化安定集合問 題は、頂点に付加された蚤みの総和を最大にする安定 集合を求める問題になります。これ 集合間畏といわれる有名な組合せ最適化関越です。上 記のような理由で、一般化安定集合閑適と享ぶことに しました。 2 推移的単純双向グラフ 役人重み安定集合問題では、人力の撫向グラフが興な れば問題も異なります。しかし、・、−−・・般化安定集合問題で は、人力の双向グラフが異なっても問題が本質的に等価 な場合があります。例えば、．I・l＋．I・2≦1と−．r2−．丁・：｝≦ −1’という2つの制約不等式からなる問題と、これにさ らに．rl−ユ・3≦0という不等式を制約に加えた問題は 同じです。なぜなら、第3の不等式は第1不等式と第 2不等式の辺々の和を取ることで得られます。本質的 に等価な問題をまとめて扱うために、入力である双向 グラフとしてある種の療準形を考え」ますムここで扱う 標準形広2つの条件を満たすもので【2】で掟案されて いるものです。 まずは∴上の例めように存在する不等式から辺々の 和を取るという操作七得られる不等式は、もともと含 まれているとします。−上れを双向グラフで表現すると 次のようになります。 推移惟：・任意の2遡p−＝トバとp2 してこれらがノで異なる符号を持つとき、 f，んに接続しキ辺p3で両端の符号がpトP2 の符号と・一致するようなものが存在する。 与えられた双向グラフを推移件を満たすように変形す るのは頂点致に閲す鳥多項式時間でできますかち、以 下では推移的双向グラフだけを扱うことにします。 仮に、推移的双向グラフの頂点Jに、2横森の自己ル ープ、両端での符号が火に＋のものと両端での符号が共 1一般化安定集合間畏とは まず、−−・・埠化安定集合問題とはどのような問題かを 説明しましょう。次のような0−1整数計画問題 最大化 ∑長一・り・り 制釣条件 ∑完，〝り・り≦わ∫J＝1・…＝朋 ・り∈（0・1）ノ＝1・・：・・〃 において．、各制約不等式の左辺の非ゼロ係数が高々2 つとします。このとき、それぞれの制約不等式を次の 3つの型 l 1 0 ＜一＜一＜一 J ヽl ＋ ー・1−f￣tl’J ・I●f￣J−ノ のどれか置き換えても、本質的に等価な問題になりま す。第1の型は「・I・Jまたは．りの高々1つしか1になら ない」という2変数パッキング条件であり、第2の型は 「どちらか一方は1である」という2変数カバリング条 件で、第3の型は「・∼・‘が1ならこりも1である」という 条件です。このような3つの型の不等式制約条件から なる0−1整数計画問題を一般化安定集合問題とよび ます。すなわち、Ⅳ＝†1，…，〃）．P、C−J⊆〃×Ⅳお よび（叫．…．tl▼‖）Lに対して、 最大化 ∑ご＝1J“，JJ・J 制約灸件 ・l・汗・り ￣・I■f￣・l！j ・I一言￣・り ク人しー∴ル ∈ ∈ ∈ ∈ J 〃バ︰J．J ．′ ．′ ．I小 ︵ ︵ ︵ ︸ 1 1 1 ︵U O 一 ︷ ∈ ≦≦≦勺 という問題を一般化安定集合問題とよびます。 −一般化安定集合問題のそれぞれの制約不等式は左辺 にちょうど2つの変数を持つため、制約条件に対応し て次のような辺を定義することで、Ⅳを頂点集合上す る特殊なグラフを用いて表現することができます。 こrrト彗≦1占 ① ① −γ‘−・Ⅰリ≦−1⇔ ①く ＞① ・・・f−・り≦0 ⇔ 0 矢尻が符号−を意味し、もう−−・方が符号＋を意味すると 思えば、各辺の2つの符一号は対応する不等式の左辺の 係数の符号に一放します。このような3つの型の辺を 持つグラフを刃向グラフ（bidireぐtPdgrapll）といいま す。双向グラフの各頂点fに重み町と変数．l・fを付加さ せれば、÷般化安定集合問題は双向グラフを用いて表 現できるわけです。 −102− © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.に−のものが接続していたと仮定しましょう。；れらの 自己ループに対応する不等式はれ＋れ≦1、⊥．l・‘−ご「；≦
−1で、これを満たす整数値存在しません。すなわち、
一一般化安定集合問堪は実行不可能です。実はこの逆も 成り立つことが知られています【21。 また実行可能なときに、頂点ノに両端での符号が共 に＋である自己ループが接続すると．I−iの整数稚から．l・f は0に固定されます。同様に、両端の符号が捌こ−である自己ループや異なる型の多東辺が存在する場合は、
幾つかの変数の値が固定でき、問視を′トさくできるこ とが知られています【2】。そこで標準形では、単純性：自己ループや多重辺を持たない。
を仮定します。
8 多項式時間で解ける場合一般化安定集合問題は、最大額み安定集合問題を特
殊な場合として含みますからNP困難です。最大量み 安定集合問題に対しては、入力無向グラフがパーフェ クトである場合【1】やタローフリーである場合【3】（重 みつきの場合は修正が必要）に多項式時間で解けることが知られています。同様に−一般化安定集合問題に対
しても、及向グラフがパーフェクトあるいはタローフリーなら多項式時間解法が存在します【5、4】。
双向グラフがパーフェクトあるいはタローフリーと は以下のように定義します。与えられた双向グラフに対して、各辺を第1型にすべて置き換えて得られる無
向グラフを対応する無向グラフとよぶことにします。双向グラフが推移的かつ単純であり、対応する撫向グラ
フが性質Pをもつとき、その双向グラフが性質Pをも
つをいうことにします。例えば、対応する無向グラフ がパーフェクトならその双向グラフもパーフェクトといいます。
ここでは、上記の2つの解法を簡単に説明しましょう。パーフェクト及向グラフに対する解法は、次の2
つの事実に基づきます：「一一般化安定集合間遠は、最大
重み安定集合問題に多項式時間で変形でき、後者の最
適解から元の最適解が多項式時間で計算できる」、「こ
の変形はパーフェクト性を保存する」。重要なのは後者 の性質です。タローフリー双向グラフに対しては、この論法が通用しません。一般化安定集合問題から最大
量み安定集合問題への変形の仕方は幾つかありますが、
タローフリー性を保存するものは今のところありませ ん02つ目の解法は、Milltさ，の解法【3】を拡張したもの です。少し複雑なため詳しくは説明できませんが、線 形目的関数の最大化に分数計両の技法を使うところが面白いと思っています。
4 おわりに 双向グラフがパーフェクトあるいはクローフリーな らば、−【−・般化安定亀倉問題は多項式時間で解けること を紹介しました。この2つの事実から次のような予想 が考えられます。 予想 ある撫向グラフのクラスに対して、最大重み安 定集介問題が多項式時間で鰍ナるなら、対応する撫「句 グラフがこのクラスに含まれる双向グラフに対しては 一般化安定集合問題も多項式時間で解ける。 2つの事例から予想しているので、強い確信があるわ けではないのですが考えてみると面白いと思います。興 味があったら是非チャレンジして下さい。 一般化安定集合問題は、最大重み安定集合問題に比 べて幾つかの整数計画閃趨を容易に記述することがで きます。一般化安定集合問題は最大重み安定集合問題 に変形できるわけですから、これらの整数計画問題は 最大積み安定集合問題としても記述できます。しかし、 この変形は変数の数が増えるなどのことから、問題を 実際に解くという立場からはあまり歓迎できるもので はありません。最大重み安定集合問題に対しては、多 くの研究が成されています。解法にしても有用なもの を一−・般化安定集合問題向きに拡張し用いることで、幾 つかの応用問題がより効率的に解けるのではないかと 願っています。 Re鮎rences 【1】Gr6tsellel，M‥ Lov孟sz、L．all（lSぐhrijver．A．、 （1988），G紺mefγよcA如r五紙m．乍作れdC抑ゐ豆nαfor哀αJ Optimizalion．Sprillger．Berli11．【2】JollnSOn、E．L alld Padl）Prg，M．W．．（1982）．
“Degree−tWOineqllalitics．（・liqllPfaぐPtS．alldbiper一 缶ぐt grapllS．’■A冊乃几J．qβよβCrだわ肋妨emαまよcβ、16、 169−187． 【3】Minty，G．，．．（1980）、“Ol11naXi111ali11（lpl）ell（leIlt Set・SOfvert・iぐeSillぐIaw−freegral）hs∴J．Combin． meo叩∫er．且28．2朗・−304． 【4】Nakamllra．D．alld Tal1111l・a．A．．（1998），“Thc gelleralizedstablesetl）rOl）1pm払rclaw−frepl）idi− rpぐtCd graphs：’ill：Bixby．R．E‥Boyd．E．A．an（1 Rfios−Merca（lo、R・Z・（e（ls．）加e卵γPγ叩Ⅵmm如 αndC抑ゎれαわr盲α‖）クfよm壱zα山肌L打tllrぐNotesin ComputprSぐipnぐe1412．Sl）ringpr、69−一83． 【5】Tal1111ra．A．．（1997）．”ThぐgellPrali椚1stablespt prol）1emfbr pcrfcぐt hidirぐぐtfL（lgral）hs：−Journal イ伽Opだrα如耶月払叩Ⅳrん∫のC五戸fyのJ九p仇40． 40ト414． −103− © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
