We consider the Vertex Cover problem in intersection graphs of axis-parallel rectangles on the plane. We present two algorithms: The first is an EPTAS for non-crossing rectangle families, rectangle families @math where @math is connected for every pair of rectangles @math . This algorithm extends to intersection graphs of pseudo-disks. The second algorithm achieves a factor of @math in general rectangle families, for any fixed @math , and works also for the weighted variant of the problem. Both algorithms exploit the plane properties of axis-parallel rectangles in a non-trivial way.
@cite_26: A unified and powerful approach is presented for devising polynomial approximation schemes for many strongly NP-complete problems. Such schemes consist of families of approximation algorithms for each desired performance bound on the relative error e > O, with running time that is polynomial when e is fixed. Though the polynomiality of these algorithms depends on the degree of approximation e being fixed, they cannot be improved, owing to a negative result stating that there are no fully polynomial approximation schemes for strongly NP-complete problems unless NP = P. The unified technique that is introduced here, referred to as the shifting strategy, is applicable to numerous geometric covering and packing problems. The method of using the technique and how it varies with problem parameters are illustrated. A similar technique, independently devised by B. S. Baker, was shown to be applicable for covering and packing problems on planar graphs.
@cite_4: We consider the problem of scheduling jobs that are given as groups of non-intersecting segments on the real line. Each job J j is associated with an interval, I j , which consists of up to t segments, for some t ≥ 1, a positive weight, w j , and two jobs are in conflict if any of their segments intersect. Such jobs show up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g. bandwidth in linear processor arrays), and in computational biology geometry. The objective is to schedule a subset of non-conflicting jobs of maximum total weight.In a single machine environment, our problem can be formulated as the problem of finding a maximum weight independent set in a t-interval graph (the special case of t = 1 is an ordinary interval graph). We show that, for t ≥ 2, this problem is APX-hard, even for highly restricted instances. Our main result is a 2t-approximation algorithm for general instances, based on a novel fractional version of the Local Ratio technique. Previously, the problem was considered only for proper union graphs, a restricted subclass of t-interval graphs, and the approximation factor achieved was (2t - 1 + 1 2t). A bi-criteria polynomial time approximation scheme (PTAS) is developed for the subclass of t-union graphs.In the online case, we consider uniform weight jobs that consist of at most two segments. We show that when the resulting 2-interval graph is proper, a simple greedy algorithm is 3-competitive, while any randomized algorithm has competitive ratio at least 2.5. For general instances, we give a randomized O(log2 R)-competitive (or O((log R)2+e)-competitive) algorithm, where R is the known (unknown) ratio between the longest and the shortest segment in the input sequence.
@cite_33: The MAXIMUM INDEPENDENT SET problem in d-box graphs, i.e., in the intersection graphs of axis-parallel rectangles in Rd, is a challenge open problem. For any fixed d ≥ 2 the problem is NP-hard and no approximation algorithm with ratio o(logd-1 n) is known. In some restricted cases, e.g., for d-boxes with bounded aspect ratio, a PTAS exists [17]. In this paper we prove APX-hardness (and hence non-existence of a PTAS, unless P = NP), of the MAXIMUM INDEPENDENT SET problem in d-box graphs for any fixed d ≥ 3. We state also first explicit lower bound 443 442 on efficient approximability in such case. Additionally, we provide a generic method how to prove APX-hardness for many NP-hard graph optimization problems in d-box graphs for any fixed d ≥ 3. In 2-dimensional case we give a generic approach to NP-hardness results for these problems in highly restricted intersection graphs of axis-parallel unit squares (alternatively, in unit disk graphs).
@cite_8: 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 equals the best known ratio for 2t--1 bounded degree graphs. Since these graphs are known to be included in multiple-interval graphs with t intervals associated to each vertex, this ratio is in some sense tight. 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-complete for the case of t = 3, and provide a (t2--t+1) 2-approximation algorithm for the problem, using recent bounds proven for the so-called transversal number of t-interval families.
@cite_28: We give polynomial time algorithms for the maximum independent set and maximum clique problems for classes of overlap graphs, assuming an overlap model is provided as input. The independent set algorithm applies to any class of overlap graphs for which the maximum weight independent set problem is polynomially solvable on the corresponding intersection graph class, where the vertex weights are nonnegative integers on which arithmetic operations can be performed in constant time. The maximum clique algorithm requires only that the overlap model satisfy the Helly property. In both cases, the size of the overlap model must be bounded by a polynomial in the size of the graph. The conditions for both algorithms are satisfied by the class of overlap graphs of subtrees in a tree, which contains chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs.
@cite_9: Circular-arc graphs are rich in combinatorial structures. Various characterization and optimization problems on circular-arc graphs have been studied. In this paper, we present an extremely simple O(n) algorithm which simultaneously solves the following three problems (the unweighted version) on circular-arc graphs: the maximum independent set, the minimum clique cover, and the minimum dominating set problems, whereas the best previous bounds for the latter two problems were O(n2) and O(n3), respectively. Our approach takes advantage of the underlying structure of circular-arc graphs that is amenable to greedy algorithms.
@cite_0: Abstract An algorithm is presented which finds a maximum stable set of a family of n arcs on a circle in O ( n log n ) time given the arcs as an unordered list of their endpoints or in O ( n ) time if they are already sorted. If we are given only the circular arc graph without a circular arc representation for it, then a maximum stable set can be found in O ( n + δe ) time where n , e , and δ are the number of vertices, edges, and minimum vertex degree, respectively. Our algorithms are based on a simple neighborhood reduction theorem which allows one to reduce any circular arc graph to a special canonical form.
@cite_5: A disk graph is the intersection graph of a set of disks with arbitrary diameters in the plane. For the case that the disk representation is given, we present polynomial-time approximation schemes (PTASs) for the maximum weight independent set problem (selecting disjoint disks of maximum total weight) and for the minimum weight vertex cover problem in disk graphs. These are the first known PTASs for @math -hard optimization problems on disk graphs. They are based on a novel recursive subdivision of the plane that allows applying a shifting strategy on different levels simultaneously, so that a dynamic programming approach becomes feasible. The PTASs for disk graphs represent a common generalization of previous results for planar graphs and unit disk graphs. They can be extended to intersection graphs of other "disk-like" geometric objects (such as squares or regular polygons), also in higher dimensions.
@cite_46: Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails. The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition. New edition of the "Classic" book on the topic Wonderful introduction to a rich research area Leading author in the field of algorithmic graph theory Beautifully written for the new mathematician or computer scientist Comprehensive treatment
@cite_16: A finite undirected graph is called chordal if every simple circuit has a chord. Given a chordal graph, we present, ways for constructing efficient algorithms for finding a minimum coloring, a minimum covering by cliques, a maximum clique, and a maximum independent set. The proofs are based on a theorem of D. Rose [3] that a finite graph is chordal if and only if it has some special orientation called an R-orientation. In the last part of this paper we prove that an infinite graph is chordal if and only if it has an R-orientation.
@cite_20: Abstract Given the interval model of an n -vertex, e -edge circle graph G , it is shown how to find a clique of G of maximum size l (respectively, maximum weight) in O (n log n + min [e,nl log ( 2n l )]) (respectively, O( n log n + min[ n 2 , e log log n ])) time. The best previous algorithms required, respectively, ⊝(n 2 ) and O( n 2 + e log log n ) time. An O( n log n + dn ) time and space algorithm that finds an independent set of maximum weight for the interval model of G is also presented. Here d is the maximum number of intervals crossing any position of the line in the interval model of G . The best previous solution for this problem took time O ( n 3 ).
@cite_17: 
, and its dual counterpart , have been previously studied in many geometric intersection graphs other than rectangle graphs. Gavril @cite_16 gave a polynomial-time algorithm for both of these problem in chordal graphs, intersection graphs of subgraphs of a tree. Apostolico @cite_20 gave a polynomial-time algorithm for these two problems in intersection graphs of chords on a circle, which were later improved by Cenek and Stuart @cite_28 , while Golumbic and Hammer @cite_0 gave a polynomial-time algorithm for intersection graphs of arcs on a circle which was later improved in @cite_9 . A good survey of many generalizations of these results can be found in @cite_46 @cite_17 . Hochbaum and Maass and later Chleb ' k and Chleb ' i kov ' a considered intersection graphs of @math -dimensional boxes in @math @cite_33 @cite_26 , while Erlebach @cite_5 considered intersection graphs of general fat objects in the plane. @cite_4 @cite_8 , approximation algorithms were suggested for and in the class of multiple-interval graphs.