Approximation Algorithms for Steiner and Directed Multicuts

In this paper we consider theSteiner multicutproblem. This is a generalization of the minimum multicut problem where instead of separating nodepairs, the goal is to find a minimum weight set of edges that separates all givensetsof nodes. A set is considered separated if it is not contained in a single connected component. We show anO(log³(kt)) approximation algorithm for the Steiner multicut problem, wherekis the number of sets andtis the maximum cardinality of a set. This improves theO(t log k) bound that easily follows from the previously known multicut results. We also consider an extension of multicuts to directed case, namely the problem of finding a minimum-weight set of edges whose removal ensures that none of the strongly connected components includes one of the prespecifiedknode pairs. In this paper we describe anO(log² k) approximation algorithm for this directed multicut problem. Ifk ? n, this represents an improvement over theO(log n log log n) approximation algorithm that is implied by the technique of Seymour.     

On Four-Connecting a Triconnected Graph

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n · α(m, n) + m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and α(m, n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k − 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.     

The dominating set problem is fixed parameter tractable for graphs of bounded genus

We describe an algorithm for the dominating set problem with time complexity O((4g+40)^kn²) for graphs of bounded genus g1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8^kn²) result for planar graphs. Our method is a refinement of the earlier techniques.     

An Efficient Algorithm for a Sparse k-Edge-Connectivity Certificate

We present an efficient algorithm for finding a sparse k-edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)²(log n)²) time using O(k(n + m′)) processors on an ARBITRARY CRCW PRAM, where n and m′ stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.     

Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem

The dynamic programming algorithm of [12.] for the bandwidth minimization problem is improved. It is shown that, for all k > 1, BANDWIDTH(k) can be solved in O(n^k) steps and simultaneous O(n^k) space, where n is the number of vertices in the graph, and that each such problem is in NSPACE(log n). The same improved dynamic programming algorithm approach works to show that the MINCUT LINEAR ARRANGEMENT problem restricted to the fixed value k, denoted by MINCUT(k), is solvable in O(n^k) steps and simultaneous O(n^k) space and is in the class NSPACE(log n).     

A fast line-sweep algorithm for hidden line elimination

Fast hidden line elimination algorithms can be obtained by minor modifications to algorithms developed for reporting intersections of polygons. We show how the same modifications which have been applied to segment trees can be applied to the data structure of Swart and Ladner as well, leading to anO((n+k)logn) time hidden line elimination algorithm (n is the number of boundary edges of the input polygons andk is the number of intersections of the edges on the projection plane). The algorithm improves the fastest previous line-sweep algorithm for the problem by a factorO(logn).This work was supported by the grant Ot 64/4-2 from the Deutsche Forschungsgemeinschaft.On leave from the Department of Computer Science, University of Helsinki, Finland.     

Increasing the Weight of Minimum Spanning Trees

The problems of computing the maximum increase in the weight of the minimum spanning trees of a graph caused by the removal of a given number of edges, or by finite increases in the weights of the edges, are investigated. For the case of edge removals, the problem is shown to be NP-hard and an Ω(1/log k)-approximation algorithm is presented for it, where (input parameter) k > 1 is the number of edges to be removed. The second problem is studied, assuming that the increase in the weight of an edge has an associated cost proportional to the magnitude of the change. An O(n³m² log(n²/m)) time algorithm is presented to solve it.     

Parameterizing above Guaranteed Values: MaxSat and MaxCut

In this paper we investigate the parameterized complexity of the problems MaxSat and MaxCut using the framework developed by Downey and Fellows. LetGbe an arbitrary graph havingnvertices andmedges, and letfbe an arbitrary CNF formula withmclauses onnvariables. We improve Cai and Chen'sO(2^2ckcm) time algorithm for determining if at leastkclauses of ac-CNF formulafcan be satisfied; our algorithm runs inO(|f| + k²φ^k) time for arbitrary formulae and inO(cm + ckφ^k) time forc-CNF formulae, where φ is the golden ratio . We also give an algorithm for finding a cut of size at leastk; our algorithm runs inO(m + n + k4^k) time. We then argue that the standard parameterization of these problems is unsuitable, because nontrivial situations arise only for large parameter values (k ≥ m/2), in which range the fixed-parameter tractable algorithms are infeasible. A more meaningful question in the parameterized setting is to ask whether m/2 + kclauses can be satisfied, or m/2 + kedges can be placed in a cut. We show that these problems remain fixed-parameter tractable even under this parameterization. Furthermore, for up to logarithmic values of the parameter, our algorithms for these versions also run in polynomial time.     

Finding minimal spanning trees in a euclidean coordinate space

The minimal spanning tree problem of a point set in ak-dimensional Euclidean space is considered and a new version of the multifragmentMST-algorithm of Bentley and Friedman is given. The minimal spanning tree is found by repeatedly joining the minimal subtree with the closest subtree. Ak-d tree is used for choosing the connecting edges. Computation time of the algorithm depends on the configuration of the point set: for normally distributed random points the algorithm is very fast. Two extreme cases demandingO(n logn) andO(n ²) operations,n being the cardinality of the point set, are also given.     

A polynomial algorithm for the max-cut problem on graphs without long odd cycles

Given a graphG=[V, E] with positive edge weights, the max-cut problem is to find a cut inG such that the sum of the weights of the edges of this cut is as large as possible. Letg(K) be the class of graphs whose longest odd cycle is not longer than2K+1, whereK is a nonnegative integer independent of the numbern of nodes ofG. We present an O(n ^4K) algorithm for the max-cut problem for graphs ing(K). The algorithm is recursive and is based on some properties of longest and longest odd cycles of graphs. This research was supported by National Science Foundation Grant ECS-8005350 to Cornell University.     

Improved algorithms for path partition and related problems

We study the L_∞ path partition problem: given a path of n weighted vertices and an integer k, remove k−1 edges from the path so that the maximum absolute deviation of the weights of the resulting k sub-paths from their mean is minimized. Previously, the best algorithm solves this problem in O(nklogk) time. We present an O(nk) time algorithm. We also give improved solutions for two related problems: the L_d path partition problem and the web proxies placement problem.     

Almost all k-colorable graphs are easy to color

We describe a simple and efficient heuristic algorithm for the graph coloring problem and show that for all k ≥ 1, it finds an optimal coloring for almost all k-colorable graphs. We also show that an algorithm proposed by Brélaz and justified on experimental grounds optimally colors almost all k-colorable graphs. Efficient implementations of both algorithms are given. The first one runs in O(n + m log k) time where n is the number of vertices and m the number of edges. The new implementation of Brélaz's algorithm runs in O(m log n) time. We observe that the popular greedy heuristic works poorly on k-colorable graphs.     

Faster Subtree Isomorphism

We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O((k^1.5/log k)n)-time algorithm for this problem, where k and n are the number of vertices in H and G, respectively. This improves over the O(k^1.5n) algorithms of Chung and Matula. We also give a randomized (Las Vegas) O(k^1.376n)-time algorithm for the decision problem.     

A note on a conjecture about cycles with many incident chords

Given positive integers n and k, let g_k(n) denote the maximum number of edges of a graph on n vertices that does not contain a cycle with k chords incident to a vertex on the cycle. Bollobás conjectured as an exercise in [2, p. 398, Problem 13] that there exists a function n(k) such that g_k(n) = (k + 1)n ? (k + 1)² for all n ≥ n(k). Using an old result of Bondy [ 3 ], we prove the conjecture, showing that n(k) ≤ 3 k + 3. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 180–182, 2004     

The power of geometric duality

This paper uses a new formulation of the notion of duality that allows the unified treatment of a number of geometric problems. In particular, we are able to apply our approach to solve two long-standing problems of computational geometry: one is to obtain a quadratic algorithm for computing the minimum-area triangle with vertices chosen amongn points in the plane; the other is to produce an optimal algorithm for the half-plane range query problem. This problem is to preprocessn points in the plane, so that given a test half-plane, one can efficiently determine all points lying in the half-plane. We describe an optimalO(k + logn) time algorithm for answering such queries, wherek is the number of points to be reported. The algorithm requiresO(n) space andO(n logn) preprocessing time. Both of these results represent significant improvements over the best methods previously known. In addition, we give a number of new combinatorial results related to the computation of line arrangements.     

The book crossing number of a graph

Let G be a graph on n vertices and m edges. The book crossing number of G is defined as the minimum number of edge crossings when the vertices of G are placed on the spine of a k-page book and edges are drawn on pages, such that each edge is contained by one page. Our main results are two polynomial time algorithms to generate near optimal drawing of G on books. The first algorithm give an O(log² n) times optimal solution, on small number of pages, under some restrictions. This algorithm also gives rise to the first polynomial time algorithm for approximating the rectilinear crossing number so that the coordinates of vertices in the plane are small integers, thus resolving a recent open question concerning the rectilinear crossing number. Moreover, using this algorithm we improve the best known upper bounds on the rectilinear crossing number. The second algorithm generates a drawing of G with O(m²/k²) crossings on k pages. This is within a constant multiplicative factor from our general lower bound of Ω(m³/n²k²), provided that m = Ψ(n²). © 1996 John Wiley & Sons, Inc.     

Modelling gateway placement in wireless networks: Geometric k-centres of unit disc graphs

Motivated by the gateway placement problem in wireless networks, we consider the geometric k-centre problem on unit disc graphs: given a set of points P in the plane, find a set F of k points in the plane that minimizes the maximum graph distance from any vertex in P to the nearest vertex in F in the unit disc graph induced by P∪F. We show that the vertex 1-centre provides a 7-approximation of the geometric 1-centre and that a vertex k-centre provides a 13-approximation of the geometric k-centre, resulting in an O(kn)-time 26-approximation algorithm. We describe O(n²m)-time and O(n³)-time algorithms, respectively, for finding exact and approximate geometric 1-centres, and an O(mn2k)-time algorithm for finding a geometric k-centre for any fixed k. We show that the problem is NP-hard when k is an arbitrary input parameter. Finally, we describe an O(n)-time algorithm for finding a geometric k-centre in one dimension.     

Finding minimal nested polygons

An algorithm for finding a polygon with minimum number of edges nested in two simplen-sided polygons is presented. The algorithm solves the problem in at mostO(n logn) time, and improves the time complexity of two previousO(n ²) algorithms.The work was supported by NSERC grant OPG0041629.     

A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk

We propose a very simple ray-shooting algorithm, whose only data structure is a triangulation. The query algorithm, after locating the triangle containing the origin of the ray, walks along the ray, advancing from one triangle to a neighboring one until the polygon boundary is reached. The key result of the paper is a Steiner triangulation of a simple polygon with the property that a ray can intersect at most O(log n) triangles before reaching the polygon boundary. We are able to compute such a triangulation in linear sequential time, or in O(log n) parallel time using O(n/log n) processors. This gives a simple, yet optimal, ray-shooting algorithm for a simple polygon. Using a well-known technique, we can extend our triangulation procedure to a multiconnected polygon with k components and n vertices, so that a ray intersects at most O(√k log n) triangles.     

Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs

We give a direct combinatorial O(n³logn) algorithm for minimizing the number of late jobs on a single machine when jobs have release times and preemptions are allowed. Our algorithm improves the earlier O(n⁵) and O(n⁴) dynamic programming algorithms for this problem.