Reconstructing Words from Subwords in Linear Time

Almost 30 years ago, M. Schützenberger and L. Simon established that two n-words with letters drawn from a finite alphabet having identical sets of subwords of length up to n/2 +1 are identical. In the context of coding theory, V.I. Levenshtein elaborated this result in a series of papers. And further elaborations dealing with alphabets and sequences with reverse complementation have been recently developed by P.L. Erds, P. Ligeti, P. Sziklai, and D.C. Torney. However, the algorithmic complexity of actually (re)constructing a word from its subwords has apparently not yet explicitly been studied. This paper augments the work of M. Schützenberger and L. Simon by showing that their approach can be reworked so as to provide a linear-time solution of this reconstruction problem in the original setting studied in their work.Received August 8, 2004     

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.     

Abelian repetitions in partial words

We study abelian repetitions in partial words, or sequences that may contain some unknown positions or holes. First, we look at the avoidance of abelian pth powers in infinite partial words, where p>2, extending recent results regarding the case where p=2. We investigate, for a given p, the smallest alphabet size needed to construct an infinite partial word with finitely or infinitely many holes that avoids abelian pth powers. We construct in particular an infinite binary partial word with infinitely many holes that avoids 6th powers. Then we show, in a number of cases, that the number of abelian p-free partial words of length n with h holes over a given alphabet grows exponentially as n increases. Finally, we prove that we cannot avoid abelian pth powers under arbitrary insertion of holes in an infinite word.     

Nonexistence of a Kruskal-Katona Type Theorem for Subword Orders

We consider the poset SO(n) of all words over an n-element alphabet ordered by the subword relation. It is known that SO(2) falls into the class of Macaulay posets, i. e. there is a theorem of Kruskal–Katona type for SO(2). As the corresponding linear ordering of the elements of SO(2) the vip-order can be chosen.Daykin introduced the V-order which generalizes the vip-order to the n2 case. He conjectured that the V-order gives a Kruskal–Katona type theorem for SO(n).We show that this conjecture fails for all n3 by explicitly giving a counterexample. Based on this, we prove that for no n3 the subword order SO(n) is a Macaulay poset.     

Spectral properties of threshold functions

We examine the spectra of boolean functions obtained as the sign of a real polynomial of degreed. A tight lower bound on various norms of the lowerd levels of the function's Fourier transform is established. The result is applied to derive best possible lower bounds on the influences of variables on linear threshold functions. Some conjectures are posed concerning upper and lower bounds on influences of variables in higher order threshold functions.Supported by an Eshkol fellowship, administered by the National Council for Research and Development—Israel Ministry of Science and Development.     

Bit strings withoutq-separation

LetB(n, q) denote the number of bit strings of lengthn withoutq-separation. In a bit string withoutq-separation no two 1's are separated by exactlyq – 1 bits.B(n, q) is known to be expressible in terms of a product of powers of Fibonacci numbers. Two new and independent proofs are given. The first proof is by combinatorial enumeration, while the second proof is inductive and expressesB(n, q) in terms of a recurrence relation.     

Toward a language theoretic proof of the four color theorem

This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.     

The local nature of Δ-coloring and its algorithmic applications

Given a connected graphG=(V, E) with |V|=n and maximum degree such thatG is neither a complete graph nor an odd cycle, Brooks' theorem states thatG can be colored with colors. We generalize this as follows: letG-v be -colored; then,v can be colored by considering the vertices in anO(log n) radius aroundv and by recoloring anO(log n) length augmenting path inside it. Using this, we show that -coloringG is reducible inO(log³ n/log) time to (+1)-vertex coloringG in a distributed model of computation. This leads to fast distributed algorithms and a linear-processorNC algorithm for -coloring.A preliminary version of this paper appeared as part of the paper Improved Distributed Algorithms for Coloring and Network Decomposition Problems, in theProceedings of the ACM Symposium on Theory of Computing pages 581–592, 1992. This research was done when the authors were at the Computer Science Department of Cornell University. The research was supported in part by NSF PYI award CCR-89-96272 with matching funds from UPS and Sun Microsystems.     

An integer based square root algorithm

We propose a fast integer based method for computing square roots of floating point numbers. This implies high accuracy and robustness, since no precision will be lost during the computation. Only integer addition and shifts are necessary to obtain the square root. Comparisons made with the modified Newton method indicate that the suggested method is twice as fast for computing floating point square roots.     

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.     

Hamiltonian paths with prescribed edges in hypercubes

Given a set P of at most 2n-4 prescribed edges (n?5) and vertices u and v whose mutual distance is odd, the n-dimensional hypercube Q_n contains a hamiltonian path between u and v passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as endvertices. This resolves a problem of Caha and Koubek who showed that for any n?3 there exist vertices u,v and 2n-3 edges of Q_n not contained in any hamiltonian path between u and v, but still satisfying the condition above. The proof of the main theorem is based on an inductive construction whose basis for n=5 was verified by a computer search. Classical results on hamiltonian edge-fault tolerance of hypercubes are obtained as a corollary.     

Growing perfect cubes

An (n,a,b)-perfect double cube is a b×b×b sized n-ary periodic array containing all possible a×a×a sized n-ary array exactly once as subarray. A growing cube is an array whose c_j×c_j×c_j sized prefix is an (n_j,a,c_j)-perfect double cube for , where and n₁<n₂<?. We construct the smallest possible perfect double cube (a 256×256×256 sized 8-ary array) and growing cubes for any a.     

Expected length of the longest common subsequence for large alphabets

We consider the length L of the longest common subsequence of two randomly uniformly and independently chosen n character words over a k-ary alphabet. Subadditivity arguments yield that E[L]/n converges to a constant γ_k. We prove a conjecture of Sankoff and Mainville from the early 1980s claiming that as k→∞.     

Davenport–Schinzel Trees*

In this paper we study labeled–tree analogues of (generalized) Davenport–Schinzel sequences.We say that two sequences a ₁ ... a _k , b ₁ ... b _k of equal length k are isomorphic, if a _i = a _j i b _i = b _j (for all i, j). For example, the sequences 11232, 33141 are isomorphic. We investigate the maximum size of a labeled (rooted) tree with each vertex labeled by one of n labels in such a way that, besides some technical conditions, the sequence of labels along any path (starting from the root) contains no subsequence isomorphic to a fixed forbidden sequence u.We study two models of such labeled trees. Each of the models is known to be essentially equivalent also to other models. The labeled paths in a special case of one of our models correspond to classical Davenport–Schinzel sequences.We investigate, in particular, for which sequences u the labeled tree has at most O(n) vertices. In both models, we answer this question for any forbidden sequence u over a two-element alphabet and also for a large class of other sequences u.* This research was partially supported by Charles University grants No. 99/158 and 99/159 and by Czech Republic Grant GAR 201/99/0242. Supported by project LN00A056 of The Ministry of Education of the Czech Republic.     

Digital Jordan curves

A digital Jordan curve theorem is proved for a new topology defined on Z². This topology is compared with the classical Khalimsky and Marcus topologies used in digital topology. We show that the Jordan curves with respect to the topology defined, unlike the Jordan curves with respect to any of the two classical topologies mentioned, may turn at the acute angle . We also discuss a quotient topology of the new topology.     

( d, m )-dominating numbers of hypercube

This paper shows that the (d, m)-dominating number of the m-dimensional hypercube Q _m (m≥4) is 2 for any integer d. . The project supported by NSFC and NSFJS.     

List Colouring When The Chromatic Number Is Close To the Order Of The Graph

Ohba has conjectured [7] that if G has 2 (G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this short note we prove the weaker version of the conjecture obtained by replacing 2 (G)+1 by * This research was partially supported by DIMACS and by CNRS/NSF collaboration grant. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey.     

The influence of large coalitions

This paper contains two results on influence in collective decision games. The first part deals with general perfect information coin-flipping games as defined in [3].Baton passing (see [8]), ann-player game from this class is shown to have the following property: IfS is a coalition of size at most \(\frac{n}{{3\log n}}\) , then the influence ofS on the game is only \(O\left( {\frac{{\left| S \right|}}{n}} \right)\) . This complements a result from [3] that for everyk there is a coalition of sizek with influence Ω(k/n). Thus the best possible bounds on influences of coalitions of size up to this threshold are known, and there need not be coalitions up to this size whose influence asymptotically exceeds their fraction of the population. This result may be expected to play a role in resolving the most outstanding problem in this area: Does everyn-player perfect information coin flipping game have a coalition ofo(n) players with influence 1?o(1)? (Recently Alon and Naor [1] gave a negative answer to this question.) In a recent paper Kahn, Kalai and Linial [7] showed that for everyn-variable boolean function of expectation bounded away from zero and one, there is a set of \(\frac{{n\omega (n)}}{{\log n}}\) variables whose influence is 1?o(1), wherew(n) is any function tending to infinity withn. They raised the analogous question where 1?o(1) is replaced by any positive constant and speculated that a constant influence may be always achievable by significantly smaller sets of variables. This problem is almost completely solved in the second part of this article where we establish the existence of boolean functions where only sets of at least \(\Omega \left( {\frac{n}{{\log ^2 n}}} \right)\) variables can have influence bounded away from zero.     

Sensitivity vs. block sensitivity of Boolean functions

Senstivity and block sensitivity are important measures of complexity of Boolean functions. In this note we exhibit a Boolean function ofn variables that has sensitivity and block sensitivity (n). This demonstrates a quadratic separation of the two measures.c/o László Babai