A fast algorithm for scalar Nevanlinna-Pick interpolation

Summary In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Givenn distinct pointsz _i in the unit disk |z|<1 andn complex numbersw _i satisfying the Pick condition for 1in, the new Nevanlinna-Pick interpolation algorithm requires onlyO(n) arithmetic operations to evaluate the interpolatory rational function at a particular value ofz, in contrast to the classical algorithm which requiresO(n ²) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring onlyO(logn) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine withn processors. We must remark that the rational functionf(z) computed by the new algorithm is one degree higher than the function computed by the classical algorithm.Supported in part by the US Army Research Office Grant No. DAAL03-91-G-0106     

A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

On the recognition complexity of some graph properties

By applying a topological approach due to Kahn, Saks and Sturtevant, we prove that all decreasing graph properties consisting of bipartite graphs only are elusive. This is an analogue to a well-known result of Yao.     

The complexity of detecting crossingfree configurations in the plane

The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.Klaus Jansen acknowledges support by the Deutsche Forschungsgemeinschaft. Gerhard J. Woeginger acknowledges support by the Christian Doppler Laboratorium für Diskrete Optimierung.     

Independence and port oracles for matroids,with an application to computational learning theory

Given a matroidM with distinguished elemente, aport oracie with respect toe reports whether or not a given subset contains a circuit that containse. The first main result of this paper is an algorithm for computing ane-based ear decomposition (that is, an ear decomposition every circuit of which contains elemente) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case thatM is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation forM. Thus, this algorithm solves a problem in computational learning theory; it learns the class ofbinary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroidM. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.Research partially funded by NSF PYI Grant No. DDM-91-96083.Research partially funded by NSF Grant No CCR-92-10957.     

The complexity of computing the tutte polynomial on transversal matroids

The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersx andy. It is shown that for fixedx andy the problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersx andy satisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.     

Improved Pseudorandom Generators for Combinatorial Rectangles

We construct a pseudorandom generator which uses bits and approximates the volume of any combinatorial rectangle in to within error. This improves on the previous construction using bits by Armoni, Saks, Wigderson, and Zhou [4]. For a subclass of rectangles with at most nontrivial dimensions and each dimension being an interval, we also give a pseudorandom generator using bits. This again improves the previous upper bound by Chari, Rohatgi, and Srinivasan [5]. Received July 29, 1998     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

Parallel computing in combinatorial optimization

This is a review of the literature on parallel computers and algorithms that is relevant for combinatorial optimization. We start by describing theoretical as well as realistic machine models for parallel computations. Next, we deal with the complexity theory for parallel computations and illustrate the resulting concepts by presenting a number of polylog parallel algorithms andP-completeness results. Finally, we discuss the use of parallelism in enumerative methods.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.     

An analysis of the greedy algorithm for the submodular set covering problem

We consider the problem: min \(\{ \mathop \Sigma \limits_{j \in s} f_j :z(S) = z(N),S \subseteqq N\} \) wherez is a nondecreasing submodular set function on a finite setN. Whenz is integer-valued andz(Ø)=0, it is shown that the value of a greedy heuristic solution never exceeds the optimal value by more than a factor \(H(\mathop {\max }\limits_j z(\{ j\} ))\) where \(H(d) = \sum\limits_{i = 1}^d {\frac{1}{i}} \) . This generalises earlier results of Dobson and others on the applications of the greedy algorithm to the integer covering problem: min {fy: Ay ≧b, y ε {0, 1}} wherea _ij ,b _i } ≧ 0 are integer, and also includes the problem of finding a minimum weight basis in a matroid.     

Fully-Dynamic Min-Cut*

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in worst-case time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^2/3), dating back to FOCS'92. Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in O(log n) time per edge. By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a near-minimal cut, but if we want to list the cut edges in O(log n) time per edge, the update time increases to . * A preliminary version of this work was presented at the The 33rd ACM Symposium on Theory of Computing( STOC) [22], Crete, Greece, July 2001.     

On the power of white pebbles

We construct a family (G _p |p) of directed acyclic graphs such that any black pebble strategy forG _p requiresp ² pebbles whereas 3p+1 pebbles are sufficient when white pebbles are allowed.Supported by the National Science Foundation under contract no. DCR-8407256 and by the office of Naval Research under contract no. N0014-80-0517.     

Improved bounds on the max-flow min-cut ratio for multicommodity flows

In this paper we consider the worst case ratio between the capacity of min-cuts and the value of max-flow for multicommodity flow problems. We improve the best known bounds for the min-cut max-flow ratio for multicommodity flows in undirected graphs, by replacing theO(logD) in the bound byO(logk), whereD denotes the sum of all demands, andk demotes the number of commodities. In essence we prove that up to constant factors the worst min-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities.Klein, Rao, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the min-cut max-flow ratio in general undirected graphs is bounded byO(logClogD), whereC denotes the sum of all the capacities. Tragoudas has improved this bound toO(lognlogD), wheren is the number of nodes in the network. Garg, Vazirani and Yannakakis further improved this toO(logklogD). Klein, Plotkin and Rao have proved that for planar networks, the ratio isO(logD).Our result improves the bound for general networks toO(log² k) and the bound for planar networks toO(logk). In both cases our result implies the first non-trivial bound that is independent of the magnitude of the numbers involved. The method presented in this paper can be used to give polynomial time approximation algorithms to the minimum cuts in the network up to the above factors.Preliminary version appeared in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, 691-697.Research supported by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by a grant from Mitsubishi Electric Laboratories.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

An algorithm for the difference between set covers

A set cover for a set S is a collection C of special subsets whose union is S. Given covers A and B for two sets, the set-cover difference problem is to construct a new cover for the elements covered by A but not B. Applications include testing equivalence of set covers and maintaining a set cover dynamically. In this paper, we solve the set-cover difference problem by defining a difference operation A-B, which turns out to be a pseudocomplement on a distributive lattice. We give an algorithm for constructing this difference, and show how to implement the algorithm for two examples with applications in computer science: face covers on a hypercube, and rectangle covers on a grid. We derive an upper bound on the time complexity of the algorithm, and give upper and lower bounds on complexity for face covers and rectangle covers.     

Recurrence relations for polynomial sequences via Riordan matrices

We give recurrence relations for any family of generalized Appell polynomials unifying so some known recurrences for many classical sequences of polynomials. Our main tool to get our goal is the Riordan group. We use the product of Riordan matrices to interpret some relationships between different polynomial families. Moreover using the Hadamard product of series we get a general recurrence relation for the polynomial sequences associated to the so called generalized umbral calculus.     

Paired domination on interval and circular-arc graphs

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time.     

Fast conversion algorithms for orthogonal polynomials

We discuss efficient conversion algorithms for orthogonal polynomials. We describe a known conversion algorithm from an arbitrary orthogonal basis to the monomial basis, and deduce a new algorithm of the same complexity for the converse operation.     

Bounded width problems and algebras

Let be finite relational structure of finite type, and let CSP denote the following decision problem: if is a given structure of the same type as , is there a homomorphism from to ? To each relational structure is associated naturally an algebra whose structure determines the complexity of the associated decision problem. We investigate those finite algebras arising from CSP’s of so-called bounded width, i.e., for which local consistency algorithms effectively decide the problem. We show that if a CSP has bounded width then the variety generated by the associated algebra omits the Hobby-McKenzie types 1 and 2. This provides a method to prove that certain CSP’s do not have bounded width. We give several applications, answering a question of Nešetřil and Zhu [26], by showing that various graph homomorphism problems do not have bounded width. Feder and Vardi [17] have shown that every CSP is polynomial-time equivalent to the retraction problem for a poset we call the Feder − Vardi poset of the structure. We show that, in the case where the structure has a single relation, if the retraction problem for the Feder-Vardi poset has bounded width then the CSP for the structure also has bounded width. This is used to exhibit a finite order-primal algebra whose variety admits type 2 but omits type 1 (provided P ≠ NP). Presented by M. Valeriote. Received January 8, 2005; accepted in final form April 3, 2006. The first author’s research is supported by a grant from NSERC and the Centre de Recherches Mathématiques. The second author’s research is supported by OTKA no. 034175 and 48809 and T 037877. Part of this research was conducted while the second author was visiting Concordia University in Montréal and also when the first author was visiting the Bolyai Institute in Szeged. The support of NSERC, OTKA and the Bolyai Institute is gratefully acknowledged.