On Coloring Unit Disk Graphs

In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques. Received February 12, 1996; revised October 9, 1996.     

All Structured Programs Have Small Tree Width and Good Register Allocation

The register allocation problem for an imperative program is often modeled as the coloring problem of the interference graph of the control-flow graph of the program. The interference graph of a flow graphGis the intersection graph of some connected subgraphs ofG. These connected subgraphs represent the lives, or life times, of variables, so the coloring problem models that two variables with overlapping life times should be in different registers. For general programs with unrestricted gotos, the interference graph can be any graph, and hence we cannot in general color within a factorO(n) from optimality unless NP=P. It is shown that if a graph has tree widthk, we can efficiently color any intersection graph of connected subgraphs within a factor (k/2+1) from optimality. Moreover, it is shown that structured (≡goto-free) programs, including, for example, short circuit evaluations and multiple exits from loops, have tree width at most 6. Thus, for every structured program, we can do register allocation efficiently within a factor 4 from optimality, regardless of how many registers are needed. The bounded tree decomposition may be derived directly from the parsing of a structured program, and it implies that the many techniques for bounded tree width may now be applied in compiler optimization, solving problems in linear time that are NP-hard, or even P-space hard, for general graphs.     

Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs

The densest k-subgraph problem asks for a k-vertex subgraph with the maximum number of edges. This problem is NP-hard on bipartite graphs, chordal graphs, and planar graphs. A 3-approximation algorithm is known for chordal graphs. We present -approximation algorithms for proper interval graphs and bipartite permutation graphs. The latter result relies on a new characterisation of bipartite permutation graphs which may be of independent interest.     

Improved Approximation Algorithm for Convex Recoloring of Trees

A pair (T,C) of a tree T and a coloring C is called a colored tree. Given a colored tree (T,C) any coloring C′ of T is called a recoloring of T. Given a weight function on the vertices of the tree the recoloring distance of a recoloring is the total weight of recolored vertices. A coloring of a tree is convex if for any two vertices u and v that are colored by the same color c, every vertex on the path from u to v is also colored by c. In the minimum convex recoloring problem we are given a colored tree and a weight function and our goal is to find a convex recoloring of minimum recoloring distance. The minimum convex recoloring problem naturally arises in the context of phylogenetic trees. Given a set of related species the goal of phylogenetic reconstruction is to construct a tree that would best describe the evolution of this set of species. In this context a convex coloring corresponds to perfect phylogeny. Since perfect phylogeny is not always possible the next best thing is to find a tree which is as close to convex as possible, or, in other words, a tree with minimum recoloring distance. We present a (2+ε)-approximation algorithm for the minimum convex recoloring problem, whose running time is O(n ²+n(1/ε)²4^1/ε ). This result improves the previously known 3-approximation algorithm for this NP-hard problem. We also present an algorithm for computing an optimal convex recoloring whose running time is , where n ^* is the number of colors that violate convexity in the input tree, and Δ is the maximum degree of vertices in the tree. The parameterized complexity of this algorithm is O(n ²+n⋅k⋅2 ^k ).     

Spanning trees with minimum weighted degrees

Given a metric graph G, we are concerned with finding a spanning tree of G where the maximum weighted degree of its vertices is minimum. In a metric graph (or its spanning tree), the weighted degree of a vertex is defined as the sum of the weights of its incident edges. In this paper, we propose a 4.5-approximation algorithm for this problem. We also prove it is NP-hard to approximate this problem within a 2−ε factor.     

Two-dimensional packing with conflicts

We study the two-dimensional version of the bin packing problem with conflicts. We are given a set of (two-dimensional) squares V = {1, 2, . . . ,n} with sides and a conflict graph G = (V, E). We seek to find a partition of the items into independent sets of G, where each independent set can be packed into a unit square bin, such that no two squares packed together in one bin overlap. The goal is to minimize the number of independent sets in the partition. This problem generalizes the square packing problem (in which we have ) and the graph coloring problem (in which s _i = 0 for all i = 1,2, . . . , sn). It is well known that coloring problems on general graphs are hard to approximate. Following previous work on the one-dimensional problem, we study the problem on specific graph classes, namely, bipartite graphs and perfect graphs. We design a -approximation for bipartite graphs, which is almost best possible (unless P = NP). For perfect graphs, we design a 3.2744-approximation. An extended abstract version of this paper has appeared in Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT 2007), pp 288–299. Rob van Stee was supported by the Alexander von Humboldt Foundation.     

Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques

We give substantially improved exact exponential-time algorithms for a number of NP-hard problems. These algorithms are obtained using a variety of techniques. These techniques include: obtaining exact algorithms by enumerating maximal independent sets in a graph, obtaining exact algorithms from parameterized algorithms and a variant of the usual branch-and-bound technique which we call the "colored" branch-and-bound technique. These techniques are simple in that they avoid detailed case analyses and yield algorithms that can be easily implemented. We show the power of these techniques by applying them to several NP-hard problems and obtaining new improved upper bounds on the running time. The specific problems that we tackle are: (1) the Odd Cycle Transversal problem in general undirected graphs, (2) the Feedback Vertex Set problem in directed graphs of maximum degree 4, (3) Feedback Arc Set problem in tournaments, (4) the 4-Hitting Set problem and (5) the Minimum Maximal Matching and the Edge Dominating Set problems. The algorithms that we present for these problems are the best known and are a substantial improvement over previous best results. For example, for the Minimum Maximal Matching we give an O^*(1.4425ⁿ) algorithm improving the previous best result of O^*(1.4422^m) [35]. For the Odd Cycle Transversal problem, we give an O^*(1.62ⁿ) algorithm which improves the previous time bound of O^*(1.7724ⁿ) [3].     

The Longest Path Problem has a Polynomial Solution on Interval Graphs

The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno (Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC), LNCS, vol. 3341, pp. 871–883, 2004), where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm uses a dynamic programming approach and runs in O(n ⁴) time, where n is the number of vertices of the input graph.     

Improved Results for a Memory Allocation Problem

We consider a memory allocation problem. This problem can be modeled as a version of bin packing where items may be split, but each bin may contain at most two (parts of) items. This problem was recently introduced by Chung et al. (Theory Comput. Syst. 39(6):829–849, 2006). We give a simple \frac32\frac{3}{2} -approximation algorithm for this problem which is in fact an online algorithm. This algorithm also has good performance for the more general case where each bin may contain at most k parts of items. We show that this general case is strongly NP-hard for any k≥3. Additionally, we design an efficient approximation algorithm, for which the approximation ratio can be made arbitrarily close to \frac75\frac{7}{5} .     

Quadratic Kernelization for Convex Recoloring of Trees

The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k) ^k n ⁴). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k ²).     

On the complexity of finding balanced oneway cuts

A bisection of an n-vertex graph is a partition of its vertices into two sets S and T, each of size n/2. The bisection cost is the number of edges connecting the two sets. In directed graphs, the cost is the number of arcs going from S to T. Finding a minimum cost bisection is NP-hard for both undirected and directed graphs. For the undirected case, an approximation of ratio O(log²n) is known. We show that directed minimum bisection is not approximable at all. More specifically, we show that it is NP-hard to tell whether there exists a directed bisection of cost 0, which we call oneway bisection. In addition, we study the complexity of the problem when some slackness in the size of S is allowed, namely, (1/2−ε)n?|S|?(1/2+ε)n. We show that the problem is solvable in polynomial time when , and provide evidence that the problem is not solvable in polynomial time when ε=o(1/(logn)⁴).     

A constant approximation algorithm for the densest k-subgraph problem on chordal graphs

The densest k-subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.     

A series of approximation algorithms for the acyclic directed steiner tree problem

Given an acyclic directed network, a subsetS of nodes (terminals), and a rootr, theacyclic directed Steiner tree problem requires a minimum-cost subnetwork which contains paths fromr to each terminal. It is known that unlessNP⊆DTIME[n ^polylogn ] no polynomial-time algorithm can guarantee better than (lnk)/4-approximation, wherek is the number of terminals. In this paper we give anO(k ^ε)-approximation algorithm for any ε>0. This result improves the previously knownk-approximation. This research was supported in part by Volkswagen-Stiftung and Packard Foundation.     

任意处理时间的多处理机任务调度近似算法

研究多处理机任务调度模型P_mfixC_max,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法。在E.Bampis等人提出的Split-Round技术基础上,提出了该问题的一个改进的多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为2(2m)^-2,优于E.Bampis等人给出的3m^-2的结果。     

On the Largest Empty Axis-Parallel Box Amidst n Points

We give the first efficient (1?ε)-approximation algorithm for the following problem: Given an axis-parallel d-dimensional box R in ? ^d containing n points, compute a maximum-volume empty axis-parallel d-dimensional box contained in R. The minimum of this quantity over all such point sets is of the order $\Theta (\frac {1}{n} )$ . Our algorithm finds an empty axis-aligned box whose volume is at least (1?ε) of the maximum in O((8edε ^?2) ^d ?nlog ^d n) time. No previous efficient exact or approximation algorithms were known for this problem for d≥4. As the problem has been recently shown to be NP-hard in arbitrarily high dimensions (i.e., when d is part of the input), the existence of an efficient exact algorithm is unlikely. We also present a (1?ε)-approximation algorithm that, given an axis-parallel d-dimensional cube R in ? ^d containing n points, computes a maximum-volume empty axis-parallel hypercube contained in R. The minimum of this quantity over all such point sets is also shown to be of the order $\Theta (\frac{1}{n} )$ . A faster (1?ε)-approximation algorithm, with a milder dependence on d in the running time, is obtained in this case.     

An effective heuristic algorithm for sum coloring of graphs

Given an undirected graph G=(V,E), the minimum sum coloring problem (MSCP) is to find a legal vertex coloring of G, using colors represented by natural numbers (1,2,…) such that the total sum of the colors assigned to the vertices is minimized. In this paper, we present EXSCOL, a heuristic algorithm based on independent set extraction for this NP-hard problem. EXSCOL identifies iteratively collections of disjoint independent sets of equal size and assign to each independent set the smallest available color. For the purpose of computing large independent sets, EXSCOL employs a tabu search based heuristic. Experimental evaluations on a collection of 52 DIMACS and COLOR2 benchmark graphs show that the proposed approach achieves highly competitive results. For more than half of the graphs used in the literature, our approach improves the current best known upper bounds.     

On-line coloring and cliques covering for KK s,t -free graphs

The problem of on-line coloring of an arbitrary graphs is known to be hard. Here we consider the problem of on-line coloring in the simplified situation where the input graph is KK_s,t-free. We show that the on-line coloring algorithm with the First Fit strategy of proposed by Capponi and Pilotto in [1] is the best one for KK_1,t-free graphs (t≥3). A.Capponi and C.Pilotto have shown that this algorithm achieves a competitive ratio of t−1 while we show that it is the best possible. However for the family of KK_s,t-free graphs (s≥2, t≥2) there exists no on-line coloring algorithm with a competitive function. The problem of an on-line cliques covering for these families is hard. There exists no on-line cliques covering algorithm with a competitive function for the family of KK_s,t-free graphs (s≥ 1, t≥3). The additional assumption that the input graph is given in a connected way does not help a lot and does not change our results described above.     

Maximum matchings in planar graphs via gaussian elimination

We present a randomized algorithm for finding maximum matchings in planar graphs in timeO(n ^ω/2), whereω is the exponent of the best known matrix multiplication algorithm. Sinceω<2.38, this algorithm breaks through theO(n ^1.5) barrier for the matching problem. This is the first result of this kind for general planar graphs. We also present an algorithm for generating perfect matchings in planar graphs uniformly at random usingO(n ^ω/2) arithmetic operations. Our algorithms are based on the Gaussian elimination approach to maximum matchings introduced in [16]. This research was supported by KBN Grant 4T11C04425.     

Efficient Algorithms for k-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).     

Efficient Algorithms for <Emphasis Type="Italic">k</Emphasis>-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).