The Power of Nondeterminism and Randomness for Oblivious Branching Programs

Abstract. This paper abstracts and generalizes the known approaches for proving lower bounds on the size of various variants of oblivious branching programs (oblivious BPs for short), providing an easy-to-use technique which works for all nondeterministic and randomized modes of acceptance. The technique is applied to obtain the following results concerning the power of nondeterminism and randomness for oblivious BPs: <p>— Oblivious read-once BPs, better known as OBDDs (ordered binary decision diagrams), are used in many applications and their structure is well understood in the deterministic case. It has been open so far to compare the power of nondeterministic OBDDs with so-called partitioned BDDs which are a variant of nondeterministic branching programs also used in practice. A k -partitioned BDD has a nondeterministic node at the top by which one out of k deterministic OBDDs with possibly different variable orders is chosen. It is proven here that the two models are incomparable as long as k is bounded by a logarithmic function in the input length. <p>— It is shown that deterministic oblivious read-k -times BPs for an explicitly defined function require superpolynomial size, for k logarithmic in the input length, while there are Las Vegas oblivious read-twice BPs of linear size for this function. This is in contrast to the situation for OBDDs, for which the respective size measures are polynomially related. <p>— Furthermore, an explicitly defined function is presented for which randomized oblivious read-k -times BPs with bounded error require exponential size, while the function as well as its complement can be represented in polynomial size by nondeterministic oblivious read-k -times BPs and deterministic oblivious read-(k+1) -times BPs, where k=o(log n) .     

The Power of Nondeterminism and Randomness for Oblivious Branching Programs

Abstract. This paper abstracts and generalizes the known approaches for proving lower bounds on the size of various variants of oblivious branching programs (oblivious BPs for short), providing an easy-to-use technique which works for all nondeterministic and randomized modes of acceptance. The technique is applied to obtain the following results concerning the power of nondeterminism and randomness for oblivious BPs: <p>— Oblivious read-once BPs, better known as OBDDs (ordered binary decision diagrams), are used in many applications and their structure is well understood in the deterministic case. It has been open so far to compare the power of nondeterministic OBDDs with so-called partitioned BDDs which are a variant of nondeterministic branching programs also used in practice. A k -partitioned BDD has a nondeterministic node at the top by which one out of k deterministic OBDDs with possibly different variable orders is chosen. It is proven here that the two models are incomparable as long as k is bounded by a logarithmic function in the input length. <p>— It is shown that deterministic oblivious read-k -times BPs for an explicitly defined function require superpolynomial size, for k logarithmic in the input length, while there are Las Vegas oblivious read-twice BPs of linear size for this function. This is in contrast to the situation for OBDDs, for which the respective size measures are polynomially related. <p>— Furthermore, an explicitly defined function is presented for which randomized oblivious read-k -times BPs with bounded error require exponential size, while the function as well as its complement can be represented in polynomial size by nondeterministic oblivious read-k -times BPs and deterministic oblivious read-(k+1) -times BPs, where k=o(log n) .     

Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs

Let Wn denote any bipartite graph obtained by adding some edges to the n-dimensional hypercube Qn, and let S and T be any two sets of k vertices in different partite sets of Wn. In this paper, we show that the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn if and only if k=²n−1 or the graph Wn−(S∪T) has a perfect matching. Moreover, if the graph Wn−(S∪T) has a perfect matching M, then the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn and all edges in M. And some corollaries are given.     

Decision algorithms for multiplayer noncooperative games of incomplete information

Extending the complexity results of Reif [1,2] for two player games of incomplete information, this paper (see also [3]) presents algorithms for deciding the outcome for various classes of multiplayer games of incomplete information, i.e., deciding whether or not a team has a winning strategy for a particular game. Our companion paper, [4] shows that these algorithms are indeed asymptotically optimal by providing matching lower bounds. The classes of games to which our algorithms are applicable include games which were not previously known to be decidable. We apply our algorithms to provide alternative upper bounds, and new time-space trade-offs on the complexity of multiperson alternating Turing machines [3]. We analyze the algorithms to characterize the space complexity of multiplayer games in terms of the complexity of deterministic computation on Turing machines.In hierarchical multiplayer games, each additional clique (subset of players with the same information) increases the complexity of the outcome problem by a further exponential. We show that an S(n) space bounded k-player game of incomplete information has a deterministic time upper bound of k + 1 repeated exponentials of S(n). Furthermore, S(n) space bounded k-player blindfold games have a deterministic space upper bound of k repeated exponentials of S(n). This paper proves that this exponential blow-up can occur.We also show that time bounded games do not exhibit such hierarchy. A T(n) time bounded blindfold multiplayer game, as well as a T(n) time bounded multiplayer game of incomplete information, has a deterministic space bound of T(n).     

Transforming spanning trees and pseudo-triangulations

Let TS be the set of all crossing-free straight line spanning trees of a planar n-point set S. Consider the graph TS where two members T and T^′ of TS are adjacent if T intersects T^′ only in points of S or in common edges. We prove that the diameter of TS is O(logk), where k denotes the number of convex layers of S. Based on this result, we show that the flip graph PS of pseudo-triangulations of S (where two pseudo-triangulations are adjacent if they differ in exactly one edge—either by replacement or by removal) has a diameter of O(nlogk). This sharpens a known O(nlogn) bound. Let be the induced subgraph of pointed pseudo-triangulations of PS. We present an example showing that the distance between two nodes in is strictly larger than the distance between the corresponding nodes in PS.     

Minimizing the makespan in a single machine scheduling problem with a time-based learning effect

Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning tree with minimum k-source routing cost among all spanning trees is called a k-source minimum routing cost spanning tree (k-MRCT). This paper proposes an algorithm to construct a spanning tree T for a metric graph G with a source vertex set S such that the building cost of T is at most 1+2/(α−1) times of that of an MST of G, and the k-source routing cost of T is at most α(1+2(k−1)(n−2)/k(n+k−2)) times of that of a k-MRCT of G with respect to S, where α>1, k=|S| and n is the number of vertices of G.     

k-Restricted rotation distance between binary trees

The restricted rotation distancedR(S,T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T, where rotations take place at the root of S, or at the right child of the root. A sharp upper bound dR(S,T)?4n−8 is known, based on group theory [S. Cleary, J. Taback, Bounding restricted rotation distance, Information Processing Letters 88 (5) (2003) 251-256]. We refine this bound to a sharp dR(S,T)?4n−8−ρS−ρT, where ρS and ρT are the numbers of vertices in the rightmost vertex chains of the two trees, using an elementary transformation algorithm. We then generalize the concept to k-restricted rotation, by allowing rotations to take place at all the vertices of the highest k levels of the tree, and study the new distance for k=2. The case k?3 is essentially open.     

Many-to-many disjoint paths in faulty hypercubes

This paper considers the problem of many-to-many disjoint paths in the hypercube Q_n with f_v faulty vertices and f_e faulty edges, and obtains the following result. For any integer k with 1?k?n-1, any two sets S and T of k fault-free vertices in different parts, if f_v+f_e?n-k-1, then there exist k disjoint fault-free (S,T)-paths in Q_n which contains at least 2ⁿ-2f_v vertices. This result is optimal in the worst case.     

Asymptotically Optimal Solutions for Small World Graphs

We consider the problem of determining constructions with an asymptotically optimal oblivious diameter in small world graphs under the Kleinberg’s model. In particular, we give the first general lower bound holding for any monotone distance distribution, that is induced by a monotone generating function. Namely, we prove that the expected oblivious diameter is Ω(log ² n) even on a path of n nodes. We then focus on deterministic constructions and after showing that the problem of minimizing the oblivious diameter is generally intractable, we give asymptotically optimal solutions, that is with a logarithmic oblivious diameter, for paths, trees and Cartesian products of graphs, including d-dimensional grids for any fixed value of d. The research was partially funded by the European project COST Action 293, “Graphs and Algorithms in Communication Networks” (GRAAL).     

On lower bounds for read-k-times branching programs

A syntactic read-k-times branching program has the restriction that no variable occurs more thank times on any path (whether or not consistent) of the branching program. We first extend the result in [31], to show that the “n/2 clique only function”, which is easily seen to be computable by deterministic polynomial size read-twice programs, cannot be computed by nondeterministic polynomial size read-once programs, although its complement can be so computed. We then exhibit an explicit Boolean functionf such that every nondeterministic syntactic read-k-times branching program for computingf has size exp $$\left( {\Omega \left( {\frac{n}{{4^k k^3 }}} \right)} \right).$$      

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

A linear-time algorithm to construct a rectilinear Steiner minimal tree fork-extremal point sets

Ak-extremal point set is a point set on the boundary of ak-sided rectilinear convex hull. Given ak-extremal point set of sizen, we present an algorithm that computes a rectilinear Steiner minimal tree in timeO(k ⁴ n). For constantk, this algorithm runs inO(n) time and is asymptotically optimal and, for arbitraryk, the algorithm is the fastest known for this problem.     

A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8^kn) and O(8^kk+n³), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.     

How many oblivious robots can explore a line

We consider the problem of exploring an anonymous line by a team of k identical, oblivious, asynchronous deterministic mobile robots that can view the environment but cannot communicate. We completely characterize sizes of teams of robots capable of exploring an n-node line. For k<n, exploration by k robots turns out to be possible, if and only if either k=3, or k?5, or k=4 and n is odd. For all values of k for which exploration is possible, we give an exploration algorithm. For all others, we prove an impossibility result.     

Higher-order Voronoi diagrams on triangulated surfaces

We study the complexity of higher-order Voronoi diagrams on triangulated surfaces under the geodesic distance, when the sites may be polygonal domains of constant complexity. More precisely, we show that on a surface defined by n triangles the sum of the combinatorial complexities of the order-j Voronoi diagrams of m sites, for j=1,…,k, is O(k²n²+k²m+knm), which is asymptotically tight in the worst case.     

An algorithm for computing the restriction scaffold assignment problem in computational biology

Let S and T be two finite sets of points on the real line with |S|+|T|=n and |S|>|T|. The restriction scaffold assignment problem in computational biology assigns each point of S to a point of T such that the sum of all the assignment costs is minimized, with the constraint that every element of T must be assigned at least one element of S. The cost of assigning an element si of S to an element tj of T is |si−tj|, i.e., the distance between si and tj. In 2003 Ben-Dor, Karp, Schwikowski and Shamir [J. Comput. Biol. 10 (2) (2003) 385] published an O(nlogn) time algorithm for this problem. Here we provide a counterexample to their algorithm and present a new algorithm that runs in O(n²) time, improving the best previous complexity of O(n³).     

Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

Simple and Improved Parameterized Algorithms for Multiterminal Cuts

Given a graph G=(V,E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 ^l kT(n,m)) time and Vertex Multiterminal Cut can be solved in O(k ^l T(n,m)) time, where T(n,m)=O(min?(n ^2/3,m ^1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 ^l T(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 ^l T(n,m)), O(2.772 ^l T(n,m)), O(3.349 ^l T(n,m)) and O(3.857 ^l T(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: $O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m))Given a graph G=(V,E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 ^l kT(n,m)) time and Vertex Multiterminal Cut can be solved in O(k ^l T(n,m)) time, where T(n,m)=O(min (n ^2/3,m ^1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 ^l T(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 ^l T(n,m)), O(2.772 ^l T(n,m)), O(3.349 ^l T(n,m)) and O(3.857 ^l T(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: O((min(?{2k},l)+1)^2k2^lT(n,m))O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m)) -time algorithm for Edge Multicut and O((2k) ^k+l/2 T(n,m))-time algorithm for Vertex Multicut.     

Evolution of simple sequence repeats

Simple Sequence Repeats (SSRs) are common and frequently polymorphic in eukaryote DNA. Many are subject to high rates of length mutation in which a gain or loss of one repeat unit is most often observed. Can the observed abundances and their length distributions be explained as the result of an unbiased random walk, starting from some initial repeat length? In order to address this question, we have considered two models for an unbiased random walk on the integers, n (n₀ ⩽ n). The first is a continuous time process (Birth and Death Model or BDM) in which the probability of a transition to n + 1 or n − 1 is λk, with k = n − n₀ + 1 per unit time. The second is a discrete time model (Random Walk Model or RWM), in which a transition is made at each time step, either to n − 1 or to n + 1. In each case the walks start at length n₀, with new walks being generated at a steady rate, S, the source rate, determined by a base substitution rate of mutation from neighboring sequences. Each walk terminates whenever n reaches n₀ − 1 or at some time, T, which reflects the contamination of pure repeat sequences by other mutations that remove them from consideration, either because they fail to satisfy the criteria for repeat selection from some database or because they can no longer undergo efficient length mutations. For infinite T, the results are particularly simple for N(k), the expected number of repeats of length n = k + n₀ − 1, being, for BDM, N(k) = S/kλ, and for RWM, N(k) = 2S. In each case, there is a cut-off value of k for finite T, namely k = Tλ ln2 for BDM and k = 0.57√T for RWM; for larger values of k, N(k) becomes rapidly smaller than the infinite time limit. We argue that these results may be compared with SSR length distributions averaged over many loci, but not for a particular locus, for which founder effects are important. For the data of Beckmann & Weber [(1992), Genomics 12, 627] on GT·AC repeats in the human, each model gives a reasonable fit to the data, with the source at two repeat units (n₀ = 2). Both the absolute number of loci and their length distribution are well represented.