スイッチンググラフ問題の独立集合問題への帰着

スイッチンググラフ問題の独立集合問題への帰着

05000653

東京工業大学

*

高澤 陽太朗

TAKAZAWA Yotaro

01603800

東京工業大学 水野 眞治

MIZUNO Shinji

1. ^はじめに

S = (I ∪ J , A)

を有向二部グラフとする．

J

内 の頂点にはスイッチがついており，頂点

j ∈ J

上のスイッチを押すと

j

に接続するすべての 有向辺の向きが反転する．本研究ではこのよ うな

S

をスイッチンググラフとよぶ．

J

^′

⊆ J

上 にあるスイッチを押したときに得られるグラ フ

S (J

^′

) = (I ∪ J , A(J

^′

))

とする（図１）．スイッ チンググラフ問題（Switching Graph Problem,

SGP

）とは，

S (J

^′

)

上の

I

の出次数または入次 数が

0

となる頂点の数が最大となる

J

^′

⊆ J

を 見つける問題である．

図

1:

スイッチンググラフ

SGP

は

Tang

ら

[3]

によって

VLSI

におけるビ ア最小化問題という問題のグラフ表現として 研究された．近年，

Karuno and Tanaka [1, 2]

に よって

SGP

の一般化に対するヒューリスティッ クアルゴリズムが与えられた．

SGP

へのヒュー リスティックアルゴリズムはいくつか与えれ ている一方で，これまでに近似・厳密アルゴ

リズムは与えられていない．

本研究では

SGP

が独立集合問題へ帰着でき ることを示した．そして，この帰着と独立集 合問題への既存研究を利用することによって，

SGP

に対する計算複雑性や近似・厳密アルゴ リズムを得た．

2. ^{問題の分析}

本研究では

SGP

の一般化である重み付き

SGP

を扱う．重み付き

SGP

では

i ∈ I

の入次 数または出次数が

0

のときそれぞれ非負の重 み

w

⁺_i，w⁻_i を得る．S

(J

^′

)

における入次数また は出次数が

0

の

I

上の頂点を以下のように表 記する．

I

⁺

(J

^′

) = { i ∈ I | d

_S⁻_(J′)

(i) = 0 }, I

⁻

(J

^′

) = { i ∈ I | d

_S⁺_(J′)

(i) = 0 }.

このとき，重み付き

SGP

は以下のように定式 化される．

max ∑

i∈I⁺(J^′)

w

⁺_i

+ ∑

i∈I⁻(J^′)

w

⁻_i

s.t. J

^′

⊆ J

(1)

ここで，

J

^′

⊆ J

を選ぶ代わりに，

I

の部分集 合のペア

(I

1

, I

2

)

に対して，

I

1内の頂点の入次 数が

0

かつ

I

₂内の頂点の出次数が

0

となるス イッチの押し方

J

^′が存在するかどうかという 視点に立って以下を定義する．

定義

1. J

^′

⊆ J

と

I

₁

, I

₂

⊆ I

に対して，

I

₁

⊆ I

⁺

(J

^′

)

かつ

I

2

⊆ I

⁻

(J

^′

)

であるとき，

J

^′は

(I

1

, I

2

)

を実 現するという．また，

I

₁

, I

₂

⊆ I

に対してに対 して，

(I

₁

, I

₂

)

を実現する

J

^′

⊆ J

が存在すると き，

(I

1

, I

2

)

は

S

に対して実行可能という．

以上の定義を使うと，問題

(1)

の代わりに 重み和が最大となる

S

に対して実行可能な

2-E-5

日本オペレーションズ・リサーチ学会

2019年 春季研究発表会

(I

₁

, I

₂

)

を見つける問題を解けばよいことがわ かる．

max ∑

i∈I1

w

⁺_i

+ ∑

i∈I2

w

⁻_i

s.t. (I

1

, I

2

)

が

S

に対して実行可能

(2)

本研究では

(I

₁

, I

₂

)

が

S

に対して実行可能で あるための必要十分条件（定理１）を導いた．

定理

1. S = (I ∪ J , A)

をスイッチンググラフと する

. I

1

, I

2

⊆ I

に対して，

(I

1

, I

2

)

が

S

に対し て実行可能であることの必要十分条件は

( { i

₁

, i

₂

}, ϕ )

は

S

に対して実行可能

( ∀ i

₁

, i

₂

∈ I

₁

) , ( ϕ, { i

1

, i

2

} )

は

S

に対して実行可能

( ∀ i

1

, i

2

∈ I

2

) , ( { i

₁

}, { i

₂

} )

は

S

に対して実行可能

( ∀ i

₁

∈ I

₁

, ∀ i

₂

∈ I

₂

) . (3)

3. ^{独立集合問題への帰着}

無向グラフ

G = (V , E)

と頂点集合

W ⊆ V

に 対して，

W

による誘導部分グラフを

G(W ) = (W , E(W))

と定める．ただし，

E(W) = {{ u , v } ∈ E | u , v ∈ W }

とする．頂点集合

W

が

E(W ) = ϕ

を満たす時，

W

をグラフ

G

の独立集合とよぶ．

非負の重み

w

_v

≥ 0(v ∈ V)

が与えられたとき，

重み付き独立集合問題とは重み和が最大とな る独立集合をみつける問題である．

重み付き

SGP

を重み付き独立集合問題へ帰 着する．定理

1

より

(I

₁

, I

₂

)

が

S

に対して実行 可能であることは，

I

1

, I

2内の

2

頂点ペアの関 係で決まることがわかる．さらに定理１内に ある

( { i

₁

, i

₂

}, ϕ )

といった

2

頂点の

S

に対する実 行可能性は簡単に確かめることができる．そ こで，

I

内の全

2

頂点ペアの関係を調べるこ とによって，

S

に対して実行可能な

(I

₁

, I

₂

)

と グラフの独立集合が対応するようなグラフ

G

S

（定義２，定理２）をつくる．

定義

2. S = (I ∪ J , A

⁺

∪ A

⁻

)

をスイッチング グラフ，

w

⁺_i

, w

⁻_i

(i ∈ I)

を重みとする．ただし，

I = { i

₁

, . . . , i

_n

}

．これらに対して，無向グラフ

G

_S

= (V

¹

∪ V

²

, E

¹

∪ E

²

∪ E

³

)

とその頂点重み

w

を以下のように定義する．

• V

¹

= { v

¹₁

, . . . , v

¹_n

}

• V

²

= { v

²₁

, . . . , v

²_n

}

• E

¹

= {{ v

¹_s

, v

¹_t

} ( ∀ s < t) |

( { i

_s

, i

_t

}, ϕ )

は

S

に対して実行可能

}

• E

²

= {{ v

²_s

, v

²_t

} ( ∀ s < t) |

( ϕ, { i

_s

, i

_t

} )

は

S

に対して実行可能

}

• E

³

= {{ v

¹_s

, v

²_t

} ( ∀ s ≤ t) |

( { i

_s

}, { i

_t

} )

は

S

に対して実行可能

}

• w

_v¹_s

= w

⁺_i

s

(s ∈ { 1 , . . . , n } )

• w

_v²

s

= w

⁻_i

s

(s ∈ { 1 , . . . , n } ).

定理

1

より，以下の定理を得る．

定理

2.

定義

1

によって得られる無向グラフと 頂点重みを

G

_S と

w

とおく．

W ⊆ V

¹

∪ V

²が

G

_S の独立集合であるとき

,

以下によって定ま る

(I

1

, I

2

)

は

S

に対して実行可能．

I

₁

= { i

_s

∈ I | v

¹_s

∈ W ∩ V

¹

} I

₂

= { i

_s

∈ I | v

²_s

∈ W ∩ V

²

}

逆に

, (I

1

, I

2

)

が

S

に対して実行可能であると き

,

以下によって定まる

W = W

₁

∪ W

₂は

G

_S の 独立集合となる

.

W

₁

= { v

¹_s

∈ V

₁

| i

_s

∈ I

₁

} W

₂

= { v

²_s

∈ V

₂

| i

_s

∈ I

₂

}

さらに

,

どちらの場合も

∑

i∈I1

w

⁺_i

+ ∑

i∈I2

w

⁻_i

=

∑

v∈W

w

_vが成立．

4. ^応用

定理

2

より，帰着によって得られたグラフ

G

S では頂点数が

2 | I |

で，最大次数は

I

と

J

の 最大次数の積で抑えられる．独立集合問題に 対しては，グラフの頂点数や最大次数に依存 した厳密・近似アルゴリズムが存在する．こ れらを帰着によって得られたグラフ

G

_S に利 用することによって，

SGP

に対する厳密・近 似アルゴリズムを得ることができた．これら の詳細は当日発表にて報告する．

参考文献

[1] Yoshiyuki Karuno and Seiya Tanaka. Cooperative item collecting problems in directed bipartite structures.Journal of Advanced Me- chanical Design, Systems, and Manufacturing, 11(2), 2017.

[2] Yoshiyuki Karuno and Seiya Tanaka. Iterative improvement ap- proaches for collecting weighted items in directed bipartite graphs.

Journal of Advanced Mechanical Design, Systems, and Manufactur- ing, 12(2), 2018.

[3] Maolin Tang, Kamran Eshraghian, and Hon Nin Cheung. An ef- ficient approach to constrained via minimization for two-layer vlsi routing. InProceedings of IEEE Asia and South Pacific Design Au- tomation Conference, pages 149–152, 1999.