On approximation algorithms
for
intersection
graphs of
rectangles
矩形によるインターセクショングラフに関する近似アルゴリズムについて
山崎浩– KoichiYAMAZAKI 群馬大学工学部情報工学科 〒 376-8515 群馬県桐生市天神町 1-5-1 koichi@comp.gunma-u.ac.jpAbstract: 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 maximumdegree ofvertex in $C_{\tau}$ by
$\Delta_{G}$
.
the neighborhoodsof$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 asetsof 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
ap-proximation algorithms for the problems.
2.1
Claw
$\mathrm{e}\mathrm{e}$property
. A graph is $k$
claw-free
if the graph does nothave $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$
.
suchthattheareaof 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
Themost
left objectstrategy
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 minimumcoloring 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}$ canbe approximated within ratio
of
$k$.Corollary 2.2 Let $R$ be a strongly non-proper
set
of
rectangles on the plane. Then mini,mumcolo$7\mathrm{v}ng$ problem and (unweighted) maximum
in-dependent set probl.$e7n$
for
intersectiongraphsrep-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
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 seethat 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 subgraphof
size $k$}.
3
Results
3.1
Graphthoretical
properties
ofrectangle graphs
Forbidden induced subgraphs
Lemma 3.1 Let $R$ be a set
of
rectangles on theplane. 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 themost 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 numberof
$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 anyin-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 approximationalgorithm
formininlum
coloring
problemTheorem 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 setsof
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 theproofiscom-plete. $\square$
4
Summary
Maximum
independent set
problemLet $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,
Minimum
coloring problem
[7] $\mathrm{D}.\mathrm{S}$.Hochbaum, Efficient bounds for thesta-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 andCul-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 coloringproblem. 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., ApproximationAlgo-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 discretecollections 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$
.
SecondAnnu-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
[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.