• 検索結果がありません。

矩形によるインターセクショングラフに関する近似アルゴリズムについて (新しいパラダイムとしてのアルゴリズム工学)

N/A
N/A
Protected

Academic year: 2021

シェア "矩形によるインターセクショングラフに関する近似アルゴリズムについて (新しいパラダイムとしてのアルゴリズム工学)"

Copied!
5
0
0

読み込み中.... (全文を見る)

全文

(1)

On approximation algorithms

for

intersection

graphs of

rectangles

矩形によるインターセクショングラフに関する近似アルゴリズムについて

山崎浩– KoichiYAMAZAKI 群馬大学工学部情報工学科 〒 376-8515 群馬県桐生市天神町 1-5-1 koichi@comp.gunma-u.ac.jp

Abstract: In this paper we show some graph theoretical properties of intersection graphs

on rectallgles and that the minimum coloring problem can be approximated within ratio

$O((\log|V(G)|)^{2})$ for the intersectiongraphs represented by set,$\mathrm{s}$of rectangles on the plane.

Keywords: Intersection graphs, rectangles. $\mathrm{a}\mathrm{p}\mathrm{p}\mathrm{r}\zeta)_{A}\mathrm{X}\overline{\mathrm{i}}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$ algorithms.

maximaum weight

independent setproblem. minimum coloring problem;

1

Definitions

and

notation

Let $G=(\mathrm{f}/^{r_{i}}E)$ be a graph. We denote the

subgraph of $G$ induced by $\mathfrak{s}\prime\prime\subseteq V$ by $G[V’]j$ the

degree ofvertex $u$ in $G$ by $d_{C7}(u)’$

.

the maximum

degree ofvertex in $C_{\tau}$ by

$\Delta_{G}$

.

the neighborhoods

of$v$ bv$\wedge’ \mathrm{V}_{G}(v)$

.

and $\{\iota’\}\cup\wedge j\backslash \tau_{G}(v)$ by $\wedge j\backslash ^{\tau}_{G}+(v)$

.

If $G$

is understood. then we often omit the inscription

$c_{\tau}$ in

$d_{G}.(?l)\mathit{1}^{\cdot}G_{i}\triangle\underline{i}\backslash _{G^{1(\iota)}\prime}^{r},$. and $\wedge \mathrm{i}\backslash _{G(v)}^{r+}’$

.

Let $\mathcal{F}=\{S_{1}\ldots..S_{k}\}$ be a family ofnonempty

subset of a set $S$

.

We will call the pair (F.$S$)

$repreSentat_{?on}$. We will refer to the set $S$ as the

hostandthe subsets$S_{i}$ as objects. A graph $G$isan

intersectiongraphrepresentedbya representation

$(\mathcal{F}_{j}S)$ if $G=(\mathcal{F}^{\cdot}, E)$ such that $\forall S_{i}.S_{j}\in F(i\neq$

$j)_{i}$

{Si.

$S_{j}$

}

$\in E$ iff $Si\cap S_{j}\neq\emptyset$

.

Let $\mathcal{R}=(\mathcal{F}=$

$\{S_{1_{\mathit{1}\text{ノ}}}\ldots..s_{k}\}.S)$ be a representation. We will say

that $\mathcal{R}$ is $un\dot{i}t$ if the objects of $F$ have the same

shape. $R$ is injective if $S_{i}=S_{j}$ implies $\dot{i}=j$ (i.e.

the subsets are distinct). Objects we consider in

the paper are open.

A closed (open) rectangleon the plane is a set

$R_{i}$ of points such that $\exists(x_{1\cdot y1})\text{ノ}.(x_{2}., y_{2})(x_{1}\leq$

$x_{2}.y_{1}\leq y_{2})$ for which $R_{i}=\{(x_{l}.y)|x_{1}\leq x\leq$

$x_{2}$. $y_{1}\leq y\leq y_{2}$

}

$(\{(x, y)|x_{1}<x<x_{2,}.y_{\mathrm{J}}<$

$y<y_{2}\}$ respectively). $\mathrm{Y}\backslash ^{7}\mathrm{e}$

denote the projection

of a rectangle

a

on the $\mathrm{x}$-axis (

$\mathrm{y}$-axis) $I_{x}(R_{i})$

$(I_{\mathrm{t}},(Ri)\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{V}\mathrm{e}1_{3}r)$

.

Let$R$be a

setsof rectangles

on the plane. $R$ is $x$-axis ($y$-axis) non-proper if

$\forall R_{i}.R_{j}\in RI_{x}(R_{i})\subset I_{x}(R_{j}\neq)$ and $I_{x}(R_{j})\subset I_{x}(R_{j}\neq)$

$((I_{y}(R_{i})\subset I_{\tau},(R_{j}\neq)$ and $I_{\iota},(JR_{j})\subset I_{\mathrm{t}}\neq/(Ri))$

respec-tively). $R$ is strongly non-proper if $R$ is $\mathrm{x}$ and $\mathrm{y}$-axis non-proper.

Let $I$ be a sets of intervals on the real line. A

graph $G$ is an interval graph represented by $I$

if

$G$ is an intersection graph represented by

$I$ (so

the host is the real line in this case). Let $MI=$

$\{A_{1_{}}\ldots. .A_{k}\}$ be a set such that $A_{i}(\forall 1\leq i\leq k)$

is a $\mathrm{u}\mathrm{l}\dot{\mathrm{u}}\mathrm{o}\mathrm{n}$of intervals on the

realline. A graph $G$

is a multiple interval graph represented by $MI$ if

$G$ is an intersection graphrepresented by $MI$ (so

the host is the real line in this case).

2

Known techniques

In the section. we willreviewseveral techniques

(2)

ap-proximation algorithms for the problems.

2.1

Claw

$\mathrm{e}\mathrm{e}$

property

. A graph is $k$

claw-free

if the graph does not

have $I_{11,k}^{\nearrow}$ as induced subgraph (See [18]). A set

ofgraphs is

claw-free

if there is a positive integer

$k$ such that all graphs in the set are $k$ claw-free.

For example. the following types of intersection

graphs have claw-free property.

Unit intersectiongraphs

Most of intersection graphs with unit

repre-sentations have the claw-free property. For

example. a graph represented by unit

iso-oriented rectangles on the plane is a 5

claw-free graph. A graph representedbyunit disks

onthe plane is $\mathrm{a}\overline{(}$claw-free graph (inour

def-inition all objectswe consider areopen) (See

[15]$)$.

Representations with objects ofbounded area

Let $C_{\tau}$be agraph representedbyaset$\mathrm{o}\mathrm{b}.|\mathrm{e}\mathrm{C}\mathrm{t}\mathrm{s}$ $\mathcal{F}$onthe plane with followingtwoproperties;

there isa positive integer$\lambda$

.

suchthatthearea

of each$\mathrm{o}\mathrm{b}.|\mathrm{e}\mathrm{C}\mathrm{t}$ in $F$is at most$k$. andanytwo

intersecting objects in $F$ share a region with

an area ofat least one. Then it is easy tosee

that all grapll representedbv$F$on the plane

are $k+1$ claw-free graphs.

The claw-free property plays an $\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{r}\mathrm{t}|\mathrm{a}\mathrm{n}\mathrm{t}$ role

in the two (or more) dimensional packing

prob-lem (See [2. 15]). because packing problem canbe

thought as a maximum independent set problem$i$

and it is known that the independent number of

a 3 claw-free weighted graph can be computed in

polynomial time [16] and also tllat the

indepen-dent number of a$k$claw-free graphcanbe

approx-$\mathrm{i}_{11}1\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{d}$ within ratio of $(k+1)/2$ for unweighted

graphs [10] and $k$ for weighted graphs [11].

2.2

The

most

left object

strategy

be the vertex corresponding to themostleft

objec-$\mathrm{t}$ in a representation of $G$

.

Then since

$G[^{}arrow\backslash ^{r_{C}}’(+v7)]$

is a 3 claw-free graph, wehave $\alpha(G[_{\wedge}\nwarrow_{G}^{+}r(v)])\leq 2$.

$\mathrm{S}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{r}13_{i}^{r}$ for an intersectiongraph$G$of unit disks

on the plane. we have $\alpha(G[_{\wedge^{/}}\mathrm{V}^{+}G(v)]\mathrm{I}\leq 3$ (note

that in our definition all objects we consider are

open) [15]. Clearly if$G$is an intersection graph of

strongly non-proper rectangles ($\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r}$unit desk)

on the plane then so is an induced subgraph of

$G$. Hence theintersectiongraphs of strongly

non-proper rectangles on the plane ($\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r}$ of unit

disks on the plane [15]$)$ have the following

prop-erties: Let $\mathcal{I}$ be a set ofintersection graphs.

.

$\exists$ a small integer $k$ sudu that $\forall G\in \mathcal{I}$. $\exists v\in$ $V(G)$ for whidi$\alpha(G[\wedge \mathrm{v}_{G}+(v)])\leq k$.

.

$\forall C_{7}\in \mathcal{I}$ and $\forall V’\subseteq V(G)$

.

$G[V’]\in \mathcal{I}$.

Using this properties. Maratheet al. showed

bet-terapproxinlation algoritlrms for minimum

color-ing problem and maximum independent set

prob-lemfor unit disk graphs [15]. The method in [15]

leads the the following proposition (See

conclud-ing remarks in [15]$)$

.

The proofs (for minimum

coloring problem) is quite similar to theunit disk

case presented in [15]. hence are omitted.

Proposition 2.1 Let $\mathcal{I}$ be a set

of

graphs with

$propert_{i}es$ that (1) $\exists$ a small inteqer $k$ such that

$\forall G\in \mathcal{I}$. $\exists v\in l^{arrow}(C_{\mathrm{T}})$

for

which $\mathfrak{a}(C7[-\backslash ^{\mathcal{T}+}((’\mathrm{T}L|)])\leq k$,

and (2) $\forall G\in \mathcal{I}$ and $\forall V’\subseteq l^{\Gamma}(c7)$. $G[l^{\gamma\prime}|\in \mathcal{I}$

.

Then. minimum, $col_{or}\dot{i}n.q$problem and $(unwe\dot{i}ght-$

$ed)$ maximum independent set problem

for

$\mathcal{I}$ can

be approximated within ratio

of

$k$.

Corollary 2.2 Let $R$ be a strongly non-proper

set

of

rectangles on the plane. Then mini,mum

colo$7\mathrm{v}ng$ problem and (unweighted) maximum

in-dependent set probl.$e7n$

for

intersectiongraphs

rep-resented by $R$ can be $approxi_{J}mated$ within ratio

of

2.

2.3

Shifting strategy

Hochbaum and Maass illtroduced a method.

Let $C_{\tau}$ bean intersectiongraph of strongly

non-proper rectangles on the plane. and let $v\in V(G)$

called shifting strategy. which applies to

(3)

to yield a polynomialtime approximation scheme

$[8_{J}.9]$

.

2.4

Decomposition strategy

In [14], S.Khanna et al. introduced the

fol-lowingsimple and useful technique to partition a

graph$G$representedby rectangles on the plane

in-to $O((\mathrm{i}\mathrm{o}\mathrm{g}|V(G)|)^{2})9$ claw-freeinduced

subgraph-$\mathrm{s}$ of $G$: Partition the set of given rectangles into

$\lceil\log|V(G)|1^{2}$ classes $(\dot{i}_{\mathrm{L}}\backslash j)’.1\leq\dot{i}\leq\lceil\log|V(G)|1$

and $1\leq j\leq\lceil\log|V(G)|1$

.

The class $(\dot{i}_{\mathit{1}}.j)$

com-prises all rectangles with width $\in[2^{i-1}+1_{i}2^{i}]$

.

and $\mathrm{h}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}\in[\underline{9}^{j-1}+1,2^{j}]$

.

Then it is easy to see

that each intersection graph represented by

rect-angles in class $(\uparrow,\cdot j)$ (on$\mathrm{t}1_{1}\mathrm{e}$plane) is a 9 claw-free

graph. We wvill refer to the technique as

decom-$pos?,t_{8}on$ strategy.

Decomposition strategy is very simple but

use-ful. For example. $\backslash \backslash ^{\tau}\mathrm{e}$ can give much more simple

proofthan one in chapter 6 in[4] for the following

theorem byusing decompositionstrategy.

Theorem 2.3 $\tau(n)\geq 7?/\lceil\log_{2}n\rceil$

for

all $n\geq 3$,

where $\tau(n)=\mathrm{m}\mathrm{a}\supset\overline{\mathrm{L}}\{k|$ every $i,nterval$graph

of

size

$n$ has a 3

claw-free

induced subgraph

of

size $k$

}.

3

Results

3.1

Graph

thoretical

properties

of

rectangle graphs

Forbidden induced subgraphs

Lemma 3.1 Let $R$ be a set

of

rectangles on the

plane. And let $G$ be the $\dot{i}ntersection$graph

repre-sentedbyR. Then, $G$ does not have an octahedron

as an induced subgraph.

Chromatic number and clique number

$\lceil\triangle(G)/4\rceil$ and $\Delta(G)+1\geq \text{ノ}\backslash ’(c)$

.

By using the

most left objectstrategy, we can show the

follow-ing slightly better upper bound.

Proposition 3.2 Let $C_{7}$ be an intersection

graph

represented by a strongly non-proper set

of

rect-angles on theplane. Then the chromatic number

of

$G$ is at most two $t\dot{i}meS$ the clique number

of

$G$

plus one.

Proof. Let $\mathcal{G}$ be the set of

intersection graphs

represented by a strongly non-proper set of

rect-angles on the plane. Any $G\in \mathcal{G}$ has a vertex

$v$ such that $d_{G}(v)$ is at most $2\omega$

.

For any

in-duced subgraph $G’$ of $C_{\tau}$

.

$C_{\tau}’$ is also in $\mathcal{G}$, and

$\omega(G^{f})\leq\omega(C_{\tau})$

.

$\mathrm{T}\mathrm{h}\mathrm{u}\mathrm{s}$

.

$,\chi(c)\leq 2\omega(G)+1$

.

$\square$

3.2

An approximation

algorithm

for

mininlum

coloring

problem

Theorem 3.3 The $\min,$imum coloring problem

canbe approximated$w\dot{i}th?.n$ ratio$O((\log|V(G)|)^{2})$

for

the $intersect?,’ on$ graphs represented by sets

of

rectangles on the plane.

Proof. By using decompositon strategy. we

have at most $O((\log|V(C7)|)^{2})9\mathrm{c}\mathrm{l}\mathrm{a}\backslash \mathrm{v}$-free

sub-graphs $C_{\tau_{ij}}$ of $C_{\tau}(1\leq i.j\leq 1o\mathrm{g}|V(c_{\tau})|)$

.

Ob-viously for each subgraph $G_{ij,}$

.

X$(c_{\tau_{ij}})\leq\backslash (G)$

.

From propositon 2.2. the problem for each

sub-graph $G_{ij}$ can be approximated within ratio 7.

This means that $\sum_{ij}(7\cross\chi(C_{7}ij))\leq\sum_{ij}(7\cross\chi(C_{\tau}))$

is $O((\log|V(G)|)^{2})\cross\lambda(G)$

.

thus theproofis

com-plete. $\square$

4

Summary

Maximum

independent set

problem

Let $R$ be a set of rectangles on the plane. And

let $C_{\mathrm{T}}$ be the intersection

graph represented by

$R$

.

In [1]. Asplund and Gr\"unbaum showed that

$4\omega(c_{\tau})^{2}>\chi(G)$. If $R$ is strongly non-proper,

(4)

Minimum

coloring problem

[7] $\mathrm{D}.\mathrm{S}$.Hochbaum, Efficient bounds for the

sta-bleset. vertex cover and set packing

problem-$\mathrm{s}_{i}$ Discrete Appl. Math. 6 (1983) 243-254.

*1: From corollary 2.2.

*2: Fron proposition 2.1 and decomposition

s-trategy.

5

Acknowledgment

Tlleresearch is partly supported by the

Grant-in-Aid for$\mathrm{S}\mathrm{C},\mathrm{i}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{C}$Research onPriority Areas of

Mimistry of

Educationi

Science. Sports and

Cul-tureof Japan$\mathrm{u}\mathrm{n}\mathrm{r}_{-}1\mathrm{e}\mathrm{r}$Grant No. ltI205202. andthe

Scientific Grant-in-Aid for Encouragement of

Y-oung Scientists ofMinistryofEducation. Science.

Sports and Culture ofJapan.

$*,\doteqdot\vee’\mathrm{X}\Re$

[1] E.Asplund and B.$\mathrm{C}_{7}\mathrm{r}\ddot{\mathrm{u}}\mathrm{n}\mathrm{b}\mathrm{a}\mathrm{u}\mathrm{m}$

.

On a coloring

problem. Math. Scand. 8 (1960) 181-188.

[2] V.Bafna. B.Naravanan. and R.Ravi.

Nonoverlapping local alignments (Weighted

independent sets of axis parallel rectallgles).

Discrete Apllied Math. 71 (1996) 41-53.

[3] $\mathrm{B}.\mathrm{N}.\mathrm{C}\mathrm{l}\mathrm{a}\mathrm{r}\mathrm{k}\text{ノ}.\mathrm{C}.\mathrm{J}$.Colbourn. and

$\mathrm{D}.\mathrm{S}$.Johnson.

Unit disk graphs. $Dis$crete Math. 86 (1990)

165-177.

[4] $\mathrm{P}.\mathrm{C}$.Fishbum, Interval orders and interval

graphs - A Study of Partially Ordered

Set-$\mathrm{s}- \text{ノ}$

.

A Wiley-Interscience Publication. 1985.

[5] $\mathrm{M}.\mathrm{C}$.Golumbic., Interval graphs and related

topics, Discrete Math. 55 (1985) 113-121.

[6] A.Gv\’arf\’as., On the chromatic number of

mul-tipleintervalgraphs and overlap graphs.

Dis-crete Math. 55 (1985) $16\dot{1}- 166$

.

[8] $\mathrm{D}.\mathrm{S}$.Hochbaum and $\mathrm{t}^{f}1’.\mathrm{M}\mathrm{a}\mathrm{a}\mathrm{s}\mathrm{s}.$

,

Approxima-tion schemes for covering and packing

prob-lems in image processing and VLSI. $JA$CM

32 (1985) 130-136.

[9] $\mathrm{D}.\mathrm{S}$.Hochbaum. Various notions of

approxi-mations: good. better., best., and more, in:

D.S.Hochbauml.

ed., Approximation

Algo-rithms for NP-HARD PROBLEMS (PWS

Publishing Company. 1997) 339-446.

[10] $\mathrm{b}\mathrm{I}.f\vee 1.\mathrm{H}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{d}\text{\’{o}} \mathrm{r}\mathrm{s}\mathrm{o}\mathrm{n}$

.

Approximating discrete

collections via local improvements.

Proceed-ings of the Sixth Annual ACM-SIAM

Sym-posium on Discrete Algorithms. (1995)

160-169.

[11] $\mathrm{D}.\mathrm{S}$.Hochbaum. Efficient bounds for the

sta-bleset.vertexcoverandsetpacking

problem-$\mathrm{s}$

.

Discrete Applied Math.. 6 (1983) 243-254.

[12] H. B. Hunt. M. V. Marathe. $\backslash "$

.

Rad-hakrishnan. and S. S. Ravi. A unified

ap-proach to approximation scllemes for

NP-and PSPACE-hard problems for geometric

graplls. Algoritluns–ESA $j94$

.

Second

Annu-al European Symposium. LNCS 855 (1994) 424-435.

[13] H.Imai and T.Asano. Finding the connected

components and a maximum clique ofan

in-tersection graphs of rectangles in the plane.

J. Algorithms, 4 (1983) 310-323.

[14] S.Khanna. S.Muthukrishnan

and M.Paterson$i$ On approximating

rectan-gle tiling and packing. Proceedings of the

Ninth Annual ACM-SIAM Symposium on

Discrete Algorithms. (1998) 384-393.

[15] $\mathrm{M}.\mathrm{V}.\mathrm{M}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{e}_{1}$

.

H.Breu.

$\mathrm{H}.\mathrm{B}$.Hunt

III, $\mathrm{S}.\mathrm{S}$.Ravi. and $\mathrm{D}.\mathrm{J}$.Rosenkrantz, Simple

heuristics for unit disl $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{h}\mathrm{S}_{i}$ Networks 25

(5)

[16] $\mathrm{G}.\mathrm{J}$.Minty, On maximal

independent sets of

vertices in claw-free graphs, J. Combin.

The-ory Ser. $B28$ (1980) 284-304.

[17] $\mathrm{D}.\mathrm{T}$.Lee., and J.Y-T.Leung,

On the 2-dimensional channel assignment $\mathrm{P}^{\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}}i$

IEEE Trans. Compute., c-33 (1984) 2-6.

[18] R.Faudaree, E.Flandrin. and Z.Ryj\’a\v{c}ek, Claw-free graphs–A$\mathrm{s}\mathrm{u}\mathrm{r}\mathrm{v}\mathrm{e}\mathrm{y}_{i}DisCrete$ Math.

参照

関連したドキュメント

Eckstein: Dual coordinate step methods for linear network flow problems, Mathematical Programming 42 (1988)

東京工業大学

Intervals graphs (denoted by INT ) are intersection graphs of intervals on a line, circular-arc graphs (CA ) are intersection graphs of intervals (arcs) on a circle, circle graphs (CI

The number of isomorphism classes of Latin squares that contain a reduced Latin square is the number of isomorphism classes of loops (since every quasigroup isomorphic to a loop is

Perhaps the most significant result describing planar graphs as intersection graphs of curves is the recent proof of Scheinerman’s conjecture that all planar graphs are segment

It is well known that in the cases covered by Theorem 1, the maximum permanent is achieved by a circulant.. Note also, by Theorem 4, that the conjecture holds for (m, 2) whenever m

セットで新規ご加入いただくと「USEN音楽放送」+「USEN Register」+「USEN光」の 月額利用料を 最大30%割引 します。

ƒ 、または Arduinoのリセットボタン”oƒ、2 }~x してか らコマンド @2 しま Q*した Arduino す。 プログラムを Arduino に…き:む Äsについては「