Optimization
Problems in Multiple-Interval Graphs
Авторы: Ayelet Butman,
Danny
Hermelin,
Moshe Lewenstein,
Dror
Rawitz
Источник:
Публикация [Перейти]
November
18, 2008
Abstract
Multiple-interval
graphs are a natural generalization
of interval graphs where each vertex may
have
more then one interval associated with it. We
initiate the study of optimization problems
in
multiple-interval graphs by considering three classical problems: Minimum
Vertex
Cover,
Minimum
Dominating Set,
and Maximum
Clique.
We describe applications
for each one of
these problems, and then proceed
to discuss
approximation algorithms for them.
Our results
can be summarized as follows: Let t
be
the
number of intervals associated
with each vertex
in a given multiple-interval graph. For
Minimum
Vertex Cover,
we give
a (2 −
1/t) – approximation
algorithm which also works when a t – interval
representation of our
given graph is absent.
Following this, we give a t2 – approximation
algorithm for Minimum
Dominating
Set which
adapts well to more general variants of
the
problem. We then proceed
to prove that Maximum
Clique is
NP-hard
already for 3 – interval
graphs, and provide a (t2−t+1)/2 –
approximation
algorithm for general values of t
≥
2,
using
bounds proven for
the so-called
transversal number of t-interval
families.
Keywords:
Approximation
Algorithms, Minimum
Vertex Cover,
Minimum Dominating Set, Maximum
Clique,
Multiple-Interval Graphs, t-interval
Graphs.
The
work on this paper was done at the
Caesarea Rothschild Institute.
Department
of
Computer Science, Holon Institute of Technology, Holon -
Israel.
Department
of
Computer Science, University of Haifa, Haifa 31905 -
Israel.
Department
of
Computer Science, Bar Ilan University, Ramat Gan 52900,
Israel.
This
work was supported by a German-Israel Foundation
(G.I.F.) young scientists program research grant.
School
of
Electrical Engineering, Tel Aviv University, Tel Aviv 69978,
Israel.
1
Introduction
Interval
graphs are one of the most popular and
well-understood graph classes in algorithmic
graph theory. They have numerous applications in
various areas, most of which can be modeled by
classical graph-theoretic problems. As an example,
basic scheduling and storage problems translate
to finding minimum colorings and clique covers in
appropriate interval graphs.
A
natural generalization of interval graphs are multiple-interval
graphs.
A multiple-interval
graph is an intersection
graph of a family of multiple
intervals,
where a multiple-interval is the
union of a
finite number of disjoint intervals over
the real line. Many problems that translate to
interval graph problems extend naturally to
multiple-interval graph problems. Scheduled tasks
become multi-tasks, storage items require non-linear
storage space, and so forth. However, in
contrast to interval graphs, most of these problems
turn out to be NP-hard.
In this paper, we consider three classical
optimization problems in multiple-interval graphs: Minimum
Vertex Cover,
Minimum
Dominating Set,
and Maximum
Clique.
Since all three
are NP-hard,
our
study focuses on designing approximation
algorithms for these problems.
1.1
Applications and motivation
Interval
graphs and closely related relatives have
been studied extensively due to their wide applicability
in modeling many real life problems. Below, we
consider three applications that correspond
to
the three problems we consider for
multiple-interval graphs in this paper.
Loss Minimization: Maximum
Independent Set is
probably
the most widely applicable
problem in
multiple-interval graphs [8, 9]. Usually,
the applications for this problem are in scheduling
or resource allocation scenarios. Since Minimum
Vertex Cover is
the complement problem
of Maximum
Independent Set,
onc can apply this
problem in most of these scenarios, where
one is
interested in minimizing loss occurring due to
unscheduled tasks or unfulfilled allocation
requests.
For
instance, describes an application for Maximum
Independent Set in
transmission of
continuous-media data such as
video by demand. Here,
each multiple-interval represents multiple
time
segments in which a client requests data,
allowing him to see a movie for instance, with
intermediate breaks. Two client requests are in
conflict if there is some time period in which they
overlap. An optimal schedule therefore corresponds to
the maximum (weight) independent set
in the
corresponding multiple-interval graph. In terms
of loss minimization, the minimum loss
is
obtained by not supplying the requests which
correspond to the minimum weight vertex cover
in
the corresponding multiple-interval graph. Another
application mentioned in is scheduling
RAM and processor time for multiple real-time programs
on multi-tasking systems. Here, loss
minimization corresponds to the minimum number of
programs to be removed from the schedule
so that
all remaining programs can run concurrently. We
mention also that loss minimization for
1-interval requests, where intervals have an
additional demand attribute associated with them, has
been considered by Bar-Noy et
al.
Employee
Monitoring: Consider
the
following scenario: The sales manager of
the ACME department
store chain wants to monitor
the salespersons at one
of his stores, since sales are not
looking too
good this year. For this, he would like to
assemble a group of monitor employees from
the
entire ACME chain, whose job is to inspect the
salespersons of the store during their work
shift. Now, at the beginning of each week he is handed
the working schedule of all the salespersons
in
the store, in addition to the working schedule of
the monitoring employees. Each schedule is
represented by a multiple-interval which corresponds
to multiple shifts in the week, i.e.
multiple
time segments
in which the salesperson or monitor can
be at the store. The manager seeks to find
the
minimum number of monitor employees needed to
inspect each one of salespersons at least once
during the week, so the remaining monitor employees
can be assigned monitor duties in other stores
of the ACME chain. If we assume that for a salesperson
to be inspected by a monitor, it is enough
that
they are both together in the store for some time
period during the week, the problem above
translates to Minimum
Directed Dominating Set.
Furthermore, if the monitor employees are
trusted salespersons that work at the store under
examination, the problem translates to Minimum
Dominating
Set.
Communication
Clique: Suppose
you
want to organize an international workshop
of computer
science specialists. In your
community, you have many
people fluent in many different languages.
You
wish to invite as many specialists as possible,
but you want all them to be able to communicate
together since you’re on a tight schedule and
anxious
to obtain the long anticipated breakthrough
in
your research. If we consider the real line as a
finite discrete set of points, where each point
represents a different langauge, we can assign a
multiple-interval
(where each interval is a single
point) to each
specialist in the community, according
to the multiple languages he is fluent in. The
problem above then translates to Maximum
Clique in
the corresponding multiple-interval graph.
One
can imagine that the scenario described above
appears in other real-life situations, e.g.
servers
and
communication protocols, transmitters and
frequency intervals, and so forth.
1.2
Our results
We
initiate the study of combinatorial optimization
problems on multiple-interval graphs. As mentioned
above, our study focuses on three classical problems: Minimum
Vertex Cover,
Minimum
Dominating
Set,
and Maximum
Clique.
Below, we briefly
describe our results for each of these
problems.
We use the term t-interval
to
refer to a multiple-interval which is the
union of t
disjoint
intervals.
For
Minimum
Vertex Cover,
we give an approximation
algorithm with ratio equalling (2 −
1/t).
This
algorithm consists of two phases. The first phase is a clean-up phase
that is based
on
the local
ratio technique.
At the end of this
phase, the remaining t-interval
graph is hereditarily
sparse,
i.e.
each
of its induced subgraphs has a bounded average degree. In the second
phase we
apply known techniques for computing
vertex covers in
hereditarily sparse graphs. We note that
our
algorithm works even when a t-interval
representation of the input graph is absent.
For
Minimum
Dominating Set,
we present a t2 –
approximation
algorithm which also applies
for the more
general case in which we are given two
subsets: a subset B
⊆
F
that
contains tintervals
that should be dominated, and a subset R
⊆
F that
contains t-intervals
that may be
used to dominate the t-intervals
in B.
This more general version of the problem is
equivalent to
Minimum
Directed Dominating Set,
since we
do not require R
and
B
to
be
disjoint. Our
algorithm can also be applied when
B
contains
tB – intervals
and R
contains
tR – intervals,
and in
this case it computes (tB, tR) – approximate
solutions. We note that this version of
the problem
contains problems such as Minimum
Rectangle Transversal (tB
=
2, tR
=
1, and the
intervals
in R
are
points), Minimum
t-Interval
Transversal (tB
=
t,
tR
=
1 and
the intervals in R
are
points), and Minimum
Set Cover with
at most t
blocks
of
consecutive ones in each column of
3
the constraint matrix (tB
=
1, tR
=
t,
and the
intervals in B
are
points)
as special cases. In fact,
our algorithm extends
the 2-approximation algorithm
for Minimum
Rectangle
Transversal
from , the t-approximation
algorithm for Minimum
t-Interval
Transversal that
is implied
by combining , and the t-approximation
algorithm for Minimum
Set Cover with
at most
blocks
of
consecutive ones from.
1.3
Related work
Multiple-interval
graphs have been studied extensively
from the graph-theoretic aspect. We briefly
list
some of the main results. The class of graphs
with maximum degree interval
graphs, while the complete bipartite
graph is
a ⌈(mn
+
1)/(m
+
n)⌉-interval
graph. Every graph with n
vertices
is
a ⌈(n
+1)/4⌉-interval
graph, and the complete bipartite
graph K⌊n/2⌋,⌈n/2⌉
is
an
extremal example of this. The class of
planar graphs is a subclass of
3-interval graphs
[10]. Finally, the problem of
determining whether a given graph is t-interval
is
NP-complete
for t
≥
2.
Many variants of
multiple-interval covering problems
have been studied by the combinatorial
optimization and discrete geometry communities. Hochbaum
and Levin [9] studied the problem
of covering
points by t-intervals.
The inverse problem of covering t-intervals
by points, also called
Minimum
t-Interval
Transversal,
has been studied along with many of its variants. Obtaining upper
bounds for the
transversal number of any t-interval
famil.
Computational biology is another field
where
multiple-interval
graph problems have been recently
considered.
For instance, Bafna et
alstudied
the problem of finding the maximum weight
subset
of non-overlapping local alignments between two
genomic sequences. This problem translates
to
finding a maximum weight independent set in a
restricted subclass of 2-interval graphs.
In
[3], the authors studied another restricted
subclass of t-interval
graphs in the context of high
throughput
genotyping. In [11, 16], 2-intervals
were used to model secondary structure of RNA
sequences, and secondary structure prediction
scenarios were modeled by variants of the Maximum
Independent
Set problem
in 2-interval graphs.
Classical optimization problems have been considered
on several ”geometric” intersection
graphs. The first results of these type are now part
of the classic literature [12]. Recently,
this line of research has been extended to consider
intersection graphs of various types of
geometric objects, e.g.
intersection
graphs of discs or ellipses in the plane [15, 16],
intersection
graphs of axis parallel rectangles [1], and
intersection graphs of general fat objects [14].
Finally, probably the most relevant work to ours is
that of Bar-Yehuda et
al. [8]
who
studied the
Maximum
Independent Set problem
in t-interval
graphs. They gave a 2t-approximation
algorithm
for this problem, in addition to a 2t-approximation
algorithm for the Minimum
Coloring
problem. We mention also [9], where a more general
variant of Maximum
Independent Set has
been studied.
2.1
The cleaning phase
The
cleaning phase is based on the Local-Ratio
technique [7] which in turn is based on the Local-
Ratio Theorem. In our terms, this theorem is stated as
follows.
Theorem 1 (Local
Ratio [7]).
Let
F
be
a family
of t-intervals
and let w,w1,
and w2
be
weight
functions for F
such
that w
=
w1
+w2.
Then,
if C
⊆ F
is
an α-approximate
cover for F,
both with
respect to w1
and
with
respect to w2,
then C
is
also an α-approximate
cover with respect to w.
A typical local ratio algorithm is recursive. In each
recursive step, the algorithm first collects all
zero elements to its solution. It then defines a
weight function w1
in
such a
way that w2
=
w
−
w1
still assigns non-negative weights to all elements,
and at least one element with non-zero weight
with respect to w
will
get
zero weight with respect to w2.
The
algorithm then recursively solves the
instance
of the problem.
References
[1]
P. Agarwal, M. van Kreveld, and S. Suri. Label
placement by maximum independent set in
rectangles. Computational
Geometry: Theory and Applications,
11,
1998.
[2]
N. Alon. Piercing d-intervals. Discrete
and Computational Geometry,
19:333–334, 1998.
[3]
Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter,
and Z. Yakhini. Dotted interval graphs
and high
throughput genotyping. In Proceedings
of the 16th annual Symposium on
Discrete
Algorithms (SODA),
pages
339–348, 2005.
[4]
V. Bafna, B. Narayanan, and R. Ravi. Nonoverlapping
local alignments (weighted independent
sets of
axis parallel rectangles). Discrete
Applied Mathematics,
71:41–53, 1996.
[5]
A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor, and
B. Shieber. A unified approach to
approximating
resource allocation and scheduling. Journal
of
the ACM,
48(5):1069–1090,
2001.
[6]
R. Bar-Yehuda and S. Even. A linear time
approximation algorithm for the weighted vertex
cover problem. Journal
of
Algorithms,
2:198–203, 1981.
[7]
R. Bar-Yehuda and S. Even. A local-ratio theorem
for approximating the weighted vertex
cover
problem. Annals
of
Discrete Mathematics,
25:27–46, 1985.
[8]
R. Bar-Yehuda, M. Halld´orsson, J. Naor, H.
Shachnai, and I. Shapira. Scheduling split intervals.
In Proceedings
of the 13th annual Symposium on Discrete Algorithms (SODA),
pages
732–741, 2002.
[9]
R. Bar-Yehuda and D. Rawitz. Using fractional
primal-dual to schedule split intervals with
demands. In 13th
annual European Symposium on Algorithms,
pages
714–725, 2005.
[10]
P. Berman, B. DasGupta, S. Muthukrishnan, and S.
Ramaswami. Efficient approximation
algorithms
for tiling and packing problems with
rectangles. Journal
of Algorithms,
41, 2001.
[11]
G. Blin, G. Fertin, and S. Vialette. New results
for the 2-interval pattern problem. In Proceedings
of the 15th annual symposium on
Combinatorial Pattern Matching (CPM),
pages
311–322, 2004.
[12]
A. Brandst¨adt, V. Le, and J. Spinrad. Graph
classes: A survey.
SIAM, 1999.
[13]
A. Butman, D. Hermelin, M. Lewenstein, and D.
Rawitz. Optimization problems in multipleinterval
graphs. In Proceedings
of the 18th annual Symposium On Discrete Algorithms (SODA),
pages 268–278, 2007.
[14]
T. Chan. Polynomial-time approximation schemes
for packing and piercing fat objects. Journal
of Algorithms,
46, 2003.
[15]
B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit
disk graphs. Discrete
Mathematics,
86:165–177, 1990.
[16]
M. Crochemore, D. Hermelin, G. Landau, and S.
Vialette. Approximating the 2-interval
pattern
problem. In Proceedings
of the 13th annual European Symposium on
Algorithms (ESA),
pages 426–437, 2005.
[17]
T. Erlebach, K. Jansen, and E. Seidel.
Polynomial-time
approximation schemes for geometric
intersection
graphs. SIAM
Journal on Computing,
34, 2005.