Àâòîðû:Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz
Èñòî÷íèê:Ïóáëèêàöèÿ ïåðåéòè
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.
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.
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.
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.
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.
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.
[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.