Maximum <Emphasis Type="Italic">k</Emphasis>-Splittable <Emphasis Type="Italic">s</Emphasis>,<Emphasis Type="Italic">t</Emphasis>-Flows

Given a graph with a source and a sink node, the NP-hard maximum k-splittable s,t-flow (M k SF) problem is to find a flow of maximum value from s to t with a flow decomposition using at most k paths. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values for the paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Usually the routing is considered before the packing. Our main contributions are as follows: (i) We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal M k SF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we can guarantee that, for any fixed ε>0, the computed set of alternatives contains a packing used by a (1−ε)-approximate solution. The latter result is based on the observation that (1−ε)-approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. (ii) Based on (i), we prove that, for constant k, the M k SF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it.     

The complexity of mean flow time scheduling problems with release times

We study the problem of preemptive scheduling of n} jobs with given release times on m identical parallel machines. The objective is to minimize the average flow time. In this paper, show that when all jobs have equal processing times then the problem can be solved in polynomial time using linear programming. Our algorithm can also be applied to the open-shop problem with release times and unit processing times. For the general case (when processing times are arbitrary), we show that the problem is unary NP-hard. P. Baptiste and C. Dürr: Supported by the NSF/CNRS grant 17171 and ANR/Alpage. P. Brucker: Supported by INTAS Project 00-217 and by DAAD PROCOPE Project D/0427360. M. Chrobak: Supported by NSF grants CCR-0208856 and INT-0340752. S. A. Kravchenko: Supported by the Alexander von Humboldt Foundation.     

An efficient parallel algorithm for shortest paths in planar layered digraphs

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs.We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log² n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log² n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.Support for the first and third authors was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA, Order 8225. Support for the second author was provided in part by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052 and ARPA Order 8225.     

Maximizing the weighted number of just-in-time jobs in?several two-machine scheduling systems

The problem of maximizing the weighted number of just-in-time jobs in a two-machine flow shop scheduling system is known to be NP\mathcal {NP}-hard (Choi and Yoon in J. Shed. 10:237–243, 2007). However, the question of whether this problem is strongly or ordinarily NP\mathcal{NP}-hard remains an open question. We provide a pseudo-polynomial time algorithm to solve this problem, proving that it is NP\mathcal{NP}-hard in the ordinary sense. Moreover, we show how the pseudo-polynomial algorithm can be converted to a fully polynomial time approximation scheme (FPTAS). In addition, we prove that the same problem is strongly NP\mathcal{NP}-hard for both a two-machine job shop scheduling system and a two-machine open shop scheduling system.     

Practical Methods for Shape Fitting and Kinetic Data Structures using Coresets

The notion of ε-kernel was introduced by Agarwal et al. (J. ACM 51:606–635, 2004) to set up a unified framework for computing various extent measures of a point set P approximately. Roughly speaking, a subset Q⊆P is an ε-kernel of P if for every slab W containing Q, the expanded slab (1+ε)W contains P. They illustrated the significance of ε-kernel by showing that it yields approximation algorithms for a wide range of geometric optimization problems. We present a simpler and more practical algorithm for computing the ε-kernel of a set P of points in ℝ ^d . We demonstrate the practicality of our algorithm by showing its empirical performance on various inputs. We then describe an incremental algorithm for fitting various shapes and use the ideas of our algorithm for computing ε-kernels to analyze the performance of this algorithm. We illustrate the versatility and practicality of this technique by implementing approximation algorithms for minimum enclosing cylinder, minimum-volume bounding box, and minimum-width annulus. Finally, we show that ε-kernels can be effectively used to expedite the algorithms for maintaining extents of moving points. A preliminary version of the paper appeared in Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 2004, pp. 263–272. Research by the first two authors is supported by NSF under grants CCR-00-86013, EIA-98-70724, EIA-01-31905, and CCR-02-04118, and by a grant from the US–Israel Binational Science Foundation. Research by the fourth author is supported by NSF CAREER award CCR-0237431.     

On the power of parity polynomial time

This paper proves that the complexity class P, parity polynomial time [PZ], contains the class of languages accepted byNP machines with few accepting paths. Indeed, P contains a broad class of languages accepted by path-restricted nondeterministic machines. In particular, P contains the polynomial accepting path versions ofNP, of the counting hierarchy, and of Mod _m NP form>1. We further prove that the class of nondeterministic path-restricted languages is closed under bounded truth-table reductions.These results were announced at the 6th Symposium on Theoretical Aspects of Computer Science [CH3]. Jin-yi Cai was supported in part by NSF Grant CCR-8709818 and the work was done while he was at Yale University. Lane A. Hemachandra was supported in part by a Hewlett-Packard Corporation equipment grant and the National Science Foundation under Grant CCR-8809174/CCR-8996198 and a Presidential Young Investigator Award. His work was done in part while at Columbia University.     

Random Bichromatic Matchings

Given a graph with edges colored Red and Blue, we study the problem of sampling and approximately counting the number of matchings with exactly k Red edges. We solve the problem of estimating the number of perfect matchings with exactly k Red edges for dense graphs. We study a Markov chain on the space of all matchings of a graph that favors matchings with k Red edges. We show that it is rapidly mixing using non-traditional canonical paths that can backtrack. We show that this chain can be used to sample matchings in the 2-dimensional toroidal lattice of any fixed size ℓ with k Red edges, where the horizontal edges are Red and the vertical edges are Blue. An extended abstract appeared in J.R. Correa, A. Hevia and M.A. Kiwi (eds.) Proceedings of the 7th Latin American Theoretical Informatics Symposium, LNCS 3887, pp. 190–201, Springer, 2006. N. Bhatnagar’s and D. Randall’s research was supported in part by NSF grants CCR-0515105 and DMS-0505505. V.V. Vazirani’s research was supported in part by NSF grants 0311541, 0220343 and CCR-0515186. N. Bhatnagar’s and E. Vigoda’s research was supported in part by NSF grant CCR-0455666.     

An Explicit Lower Bound for TSP with Distances One and Two

Abstract. We show that, for any ɛ>0 , it is NP-hard to approximate the asymmetric traveling salesman problem with distances one and two within 2805/2804-ɛ . For the special case where the distance function is constrained to be symmetric, we show a lower bound of 5381/5380-ɛ , for any ɛ>0 . While it was previously known that there exists some constant, strictly greater than one, such that it is NP-hard to approximate the traveling salesman problem with distances one and two within that constant, this result is a first step towards the establishment of a good bound. In our proof we develop a new gadget construction to reduce from systems of linear equations mod 2 with two unknowns in each equation and at most three occurrences of each variable. Compared with earlier reductions to the traveling salesman problem with distances one and two, ours reduces the number of cities to less than a tenth of what was previously necessary.     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takesO(log² n) time withO(n) processors on a CRCW PRAM, wheren is the number of vertices of the graph.This research was supported by NSF Grants CCR-9011214 and CCR-9205982.     

A variation on the min cut linear arrangement problem

The Min Cut Linear Arrangement problem asks, for a given graphG and a positive integerk, if there exists a linear arrangement ofG's vertices so that any line separating consecutive vertices in the layout cuts at mostk of the edges. A variation of this problem insists that the arrangement be made on a (fixed-degree) tree instead of a line. We show that (1) this problem isNP-complete even whenG is planar; (2) it is easily solved whenG is a tree; and (3) there is a simple characterization for all graphs with cost 2 or less. Our main result is a linear-time algorithm to embed an outerplanar graphG into a spanning tree with cost at most maxdegree(G) + 1. This result is important because it extends to an approximation algorithm for the standard Min Cut Linear Arrangement Problem on outerplanar graphs.Supported in part by NSF Grant CCR-8710730.     

An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs

We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log² n) time withO(n ³) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.Research supported in part by NSF Grants CCR-9011214 and CCR-9205982.     

GSTE is partitioned model checking

Verifying whether an ω-regular property is satisfied by a finite-state system is a core problem in model checking. Standard techniques build an automaton with the complementary language, compute its product with the system, and then check for emptiness. Generalized symbolic trajectory evaluation (GSTE) has been recently proposed as an alternative approach, extending the computationally efficient symbolic trajectory evaluation (STE) to general ω-regular properties. In this paper, we show that the GSTE algorithms are essentially a partitioned version of standard symbolic model-checking (SMC) algorithms, where the partitioning is driven by the property under verification. We export this technique of property-driven partitioning to SMC and show that it typically does speed up SMC algorithms. A shorter version of this paper has been presented at CAV’04 (R. Sebastiani et al., Lecture Notes in Comput. Sci., vol. 3114, pp. 143–160, 2004). R. Sebastiani supported in part by the CALCULEMUS! IHP-RTN EC project, code HPRN-CT-2000-00102, by a MIUR COFIN02 project, code 2002097822_003, and by a grant from the Intel Corporation. M.Y. Vardi supported in part by NSF grants CCR-9988322, CCR-0124077, CCR-0311326, IIS-9908435, IIS-9978135, EIA-0086264, and ANI-0216467 by BSF grant 9800096, and by a grant from the Intel Corporation.     

The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs

We consider a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short, on interval graphs. Given a graph G and a subset T\mathcal{T} of k vertices of V(G), a k-fixed-endpoint path cover of G with respect to T\mathcal{T} is a set of vertex-disjoint paths ℘ that covers the vertices of G such that the k vertices of T\mathcal{T} are all endpoints of the paths in ℘. The kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality; note that, if T\mathcal{T} is empty the stated problem coincides with the classical path cover problem. In this paper, we study the 1-fixed-endpoint path cover problem on interval graphs, or 1PC for short, generalizing the 1HP problem which has been proved to be NP-complete even for small classes of graphs. Motivated by a work of Damaschke (Discrete Math. 112:49–64, 1993), where he left both 1HP and 2HP problems open for the class of interval graphs, we show that the 1PC problem can be solved in polynomial time on the class of interval graphs. We propose a polynomial-time algorithm for the problem, which also enables us to solve the 1HP problem on interval graphs within the same time and space complexity.     

Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles

We show that several problems that are hard for various parameterized complexity classes on general graphs, become fixed parameter tractable on graphs with no small cycles. More specifically, we give fixed parameter tractable algorithms for Dominating Set, t -Vertex Cover (where we need to cover at least t edges) and several of their variants on graphs with girth at least five. These problems are known to be W[i]-hard for some i≥1 in general graphs. We also show that the Dominating Set problem is W[2]-hard for bipartite graphs and hence for triangle free graphs. In the case of Independent Set and several of its variants, we show these problems to be fixed parameter tractable even in triangle free graphs. In contrast, we show that the Dense Subgraph problem where one is interested in finding an induced subgraph on k vertices having at least l edges, parameterized by k, is W[1]-hard even on graphs with girth at least six. Finally, we give an O(log p) ratio approximation algorithm for the Dominating Set problem for graphs with girth at least 5, where p is the size of an optimum dominating set of the graph. This improves the previous O(log n) factor approximation algorithm for the problem, where n is the number of vertices of the input graph. A preliminary version of this paper appeared in the Proceedings of 10th Scandinavian Workshop on Algorithm Theory (SWAT), Lecture Notes in Computer Science, vol. 4059, pp. 304–315, 2006.     

Primitives for asynchronous list compression

In this paper we study the problem of asynchronous processors traversing a list with path compression. We show that if an atomic splice operation is available, the worst-case work forp processors traversing a list of length h is (np ^1/2). The splice operation can be generalized to removek elements from the list. For thek-splice operation the worst-case work is (np ^1/ k+1).This research was supported by an NSF Presidential Young Investigator Award CCR-8657562, Digital Equipment Corporation, NSF CER Grant CCR-861966, and NSF/Darpa Grant CCR-8907960. A preliminary version of this paper was presented at the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures.     

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.     

The Complexity of Flood Filling Games

We study the complexity of the popular one player combinatorial game known as Flood-It. In this game the player is given an n×n board of tiles where each tile is allocated one of c colours. The goal is to make the colours of all tiles equal via the shortest possible sequence of flooding operations. In the standard version, a flooding operation consists of the player choosing a colour k, which then changes the colour of all the tiles in the monochromatic region connected to the top left tile to k. After this operation has been performed, neighbouring regions which are already of the chosen colour k will then also become connected, thereby extending the monochromatic region of the board. We show that finding the minimum number of flooding operations is NP-hard for c≥3 and that this even holds when the player can perform flooding operations from any position on the board. However, we show that this ‘free’ variant is in P for c=2. We also prove that for an unbounded number of colours, Flood-It remains NP-hard for boards of height at least 3, but is in P for boards of height 2. Next we show how a (c−1) approximation and a randomised 2c/3 approximation algorithm can be derived, and that no polynomial time constant factor, independent of c, approximation algorithm exists unless P=NP. We then investigate how many moves are required for the ‘most demanding’ n×n boards (those requiring the most moves) and show that the number grows as fast as Q(?c n)\Theta(\sqrt{c}\, n). Finally, we consider boards where the colours of the tiles are chosen at random and show that for c≥2, the number of moves required to flood the whole board is Ω(n) with high probability.     

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.     

AnO(logk)-approximation algorithm for thek minimum spanning tree problem in the plane

Givenn points in the Euclidean plane, we consider the problem of finding the minimum tree spanning anyk points. The problem isNP-hard and we give anO(logk)-approximation algorithm.