On covering problems of codes

LetC be a binary code of lengthn (i.e., a subset of {0, 1} ⁿ ). TheCovering Radius of C is the smallest integerr such that each vector in {0, 1} ⁿ is at a distance at mostr from some code word. Our main result is that the decision problem associated with the Covering Radius of arbitrary binary codes is NP-complete. This result is established as follows. TheRadius of a binary codeC is the smallest integerr such thatC is contained in a radius-r ball of the Hamming metric space 〈{0, 1} ⁿ ,d〉. It is known [K] that the problems of computing the Radius and the Covering Radius are equivalent. We show that the 3SAT problem is polynomially reducible to the Radius decision problem. A central tool in our reduction is a metrical characterization of the set ofdoubled vectors of length 2n: {v=(v ₁ v ₂ …v _2n ) | ∀i:v _2i =v _2i−1}. We show that there is a setY ⊂ {0, 1}²ⁿ such that for everyv ε {0, 1}²ⁿ :v is doubled iffY is contained in the radius-n ball centered atv; moreover,Y can be constructed in time polynomial inn.     

Fast modular exponentiation of large numbers with large exponents

In many problems, modular exponentiation |x^b|_m is a basic computation, often responsible for the overall time performance, as in some cryptosystems, since its implementation requires a large number of multiplications.It is known that |x^b|_m=|x^|b|_(m)|_m for any x in [1,m−1] if m is prime; in this case the number of multiplications depends on (m) instead of depending on b. It was also stated that previous relation holds in the case m=pq, with p and q prime; this case occurs in the RSA method.In this paper it is proved that such a relation holds in general for any x in [1,m−1] when m is a product of any number n of distinct primes and that it does not hold in the other cases for the whole range [1,m−1].Moreover, a general method is given to compute |x^b|_m without any hypothesis on m, for any x in [1,m−1], with a number of modular multiplications not exceeding those required when m is a product of primes.Next, it is shown that representing x in a residue number system (RNS) with proper moduli m_i allows to compute |x^b|_m by n modular exponentiations |x_i^b|_mi in parallel and, in turn, to replace b by |b|_(mi) in the worst case, thus executing a very low number of multiplications, namely log₂m_i for each residue digit.A general architecture is also proposed and evaluated, as a possible implementation of the proposed method for the modular exponentiation.     

Exponential lower bounds for depth three Boolean circuits

We consider the class of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has gates (for k = O(n ^1/2)) for some , and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC ¹ that require size depth 3 circuits. The main tool is a theorem that shows that any circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form x _i = 0, x _i = 1, x _i = x _j or x _i = ) of dimension at least log(a/s)log n. Received: April 1, 1997.     

Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems

CLOSEST STRING is one of the core problems in the field of consensus word analysis with particular importance for computational biology. Given k strings of the same length and a nonnegative integer d , find a ``center string' s such that none of the given strings has the Hamming distance greater than d from s . CLOSEST STRING is NP-complete. In biological applications, however, d is usually very small. We show how to solve CLOSEST STRING in linear time for fixed d —the exponential growth in d is bounded by O(d ^d ) . We extend this result to the closely related problems d -MISMATCH and DISTINGUISHING STRING SELECTION. Moreover, we also show that CLOSEST STRING is solvable in linear time when k is fixed and d is arbitrary. In summary, this means that CLOSEST STRING is fixed-parameter tractable with respect to parameter d and with respect to parameter k . Finally, the practical usefulness of our findings is substantiated by some experimental results.     

On Rooted Node-Connectivity Problems

Let G be a graph which is k -outconnected from a specified root node r , that is, G has k openly disjoint paths between r and v for every node v . We give necessary and sufficient conditions for the existence of a pair rv,rw of edges for which replacing these edges by a new edge vw gives a graph that is k -outconnected from r . This generalizes a theorem of Bienstock et al. on splitting off edges while preserving k -node-connectivity. We also prove that if C is a cycle in G such that each edge in C is critical with respect to k -outconnectivity from r , then C has a node v , distinct from r , which has degree k . This result is the rooted counterpart of a theorem due to Mader. We apply the above results to design approximation algorithms for the following problem: given a graph with nonnegative edge weights and node requirements c _u for each node u , find a minimum-weight subgraph that contains max {c _u ,c _v } openly disjoint paths between every pair of nodes u,v . For metric weights, our approximation guarantee is 3 . For uniform weights, our approximation guarantee is \min{ 2, (k+2q-1)/k} . Here k is the maximum node requirement, and q is the number of positive node requirements. Received September 15, 1998; revised March 10, 2000, and April 17, 2000.     

Crown graphs and subdivision of ladders are odd graceful

A graph G of size q is odd graceful, if there is an injection φ from V(G) to {0, 1, 2, …, 2q?1} such that, when each edge xy is assigned the label or weight |f(x)?f(y)|, the resulting edge labels are {1, 3, 5, …, 2q?1}. This definition was introduced in 1991 by Gnanajothi [3], who proved that the graphs obtained by joining a single pendant edge to each vertex of C _n are odd graceful, if n is even. In this paper, we generalize Gnanajothi's result on cycles by showing that the graphs obtained by joining m pendant edges to each vertex of C _n are odd graceful if n is even. We also prove that the subdivision of ladders S(L _n ) (the graphs obtained by subdividing every edge of L _n exactly once) is odd graceful.     

VISOR: Vast Independence System Optimization Routine

An algorithm is sketched that generates all K maximal independent sets and all M minimal dependent sets of an arbitrary independence system, based on a set of cardinality n having at most 2 ⁿ subsets, with access to an oracle that decides if a set is independent or not. Because the algorithm generates all those sets, it solves the problems of finding all maximum independent and minimum dependent sets. Those problems are known to be impossible to solve in general in time polynomial in n , K , and M , and they are \cal N \cal P hard. The algorithm proposed and used is efficient in the sense that it requires only O(nK+M) or O(K+nM) visits to the oracle, the nonpolynomial part is only related to bitstring comparisons and the like, which can be performed rather quickly and, to some degree, in parallel on a sequential machine. This complexity compares favorably with another algorithm that is O(n ² K ² ) . The design of a computer routine that implements the algorithm in a highly optimized way is discussed. The routine behaves as expected, as is shown by numerical experiments on a range of randomly generated independence systems with n up to n=34 . Application on an engineering design problem with n=28 shows the routine requires almost 10 ⁶ times less visits to the oracle than an exhaustive search, while the time spent in visiting the oracle is still significantly larger than that spent for all other computations together. Received March 30, 1998; revised February 10, 1999 and April 27, 1999.     

d-正则(k,s)-SAT问题的NP完全性

研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是NP完全问题.研究具有更强正则约束的d-正则(k,s)-SAT问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(k,s)-SAT问题存在一个临界函数f(k,d),使得当s≤f(k,d)时,所有实例都可满足;当s≥f(k,d)+1时,d-正则(k,s)-SAT问题是NP完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数f(k,d)的研究有助于在更强正则约束条件下构造难解实例.     

On Word Equations in One Variable

For a word equation E of length n in one variable x occurring # _x times in E a resolution algorithm of O(n+# _x log n) time complexity is presented here. This is the best result known and for the equations that feature #_x < \fracnlogn\#_{x}<\frac{n}{\log n} it yields time complexity of O(n) which is optimal. Additionally it is proven here that the set of solutions of any one-variable word equation is either of the form F or of the form F∪(uv)⁺ u where F is a set of O(log n) words and u, v are some words such that uv is a primitive word.     

Algorithmic Aspects of Acyclic Edge Colorings

Abstract. A proper coloring of the edges of a graph G is called acyclic if there is no two-colored cycle in G . The acyclic edge chromatic number of G , denoted by a'(G) , is the least number of colors in an acyclic edge coloring of G . For certain graphs G , a'(G)\geq Δ(G)+2 where Δ(G) is the maximum degree in G . It is known that a'(G)≤ Δ + 2 for almost all Δ -regular graphs, including all Δ -regular graphs whose girth is at least cΔ log Δ . We prove that determining the acyclic edge chromatic number of an arbitrary graph is an NP-complete problem. For graphs G with sufficiently large girth in terms of Δ(G) , we present deterministic polynomial-time algorithms that color the edges of G acyclically using at most Δ(G)+2 colors.     

On meshy trees

A graph is termed d-meshy if it can be isomorphicaly embedded in the universal d-dimensional mesh (grid) M _d . We investigate the d-meshiness of tree graphs, especially for d = 2. Trees of minimum order that are nonmeshy are identified. It is shown that for any d and n≧2, there exists an h such that the full n-ary tree of height h is not d-meshy. Spreading mesh embeddings of trees that preserve distance from the root are discussed, qs well as the characterization of meshy trees by their degree sequences.     

Inapproximability of the Tutte polynomial

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). Jaeger et al. have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. We are interested in determining for which points (x,y) there is a fully polynomial randomised approximation scheme (FPRAS) for T(G;x,y). Under the assumption RP≠NP, we prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x<-1,y=1 (which is still open) and the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for (x,y) in the vicinity of the origin. A corollary of our results is that, under the assumption RP≠NP, there is no FPRAS at the point (x,y)=(0,1-λ) when λ>2 is a positive integer. Thus, there is no FPRAS for counting nowhere-zero λ flows for λ>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for λ=6. Although our main concern is to distinguish regions of the Tutte plane that admit an FPRAS from those that do not, we also note that the latter regions exhibit different levels of intractability. At certain points (x,y), for example the integer points on the x-axis, or any point in the positive quadrant, there is a randomised approximation scheme for T(G;x,y) that runs in polynomial time using an oracle for an NP predicate. On the other hand, we identify a region of points (x,y) at which even approximating T(G;x,y) is as hard as #P.     

Spectral properties of infinite-dimensional closed-loop systems

We consider feedback systems obtained from infinite-dimensional well-posed linear systems by output feedback. Thus, our framework allows for unbounded control and observation operators. Our aim is to investigate the relationship between the open-loop system, the feedback operator K and the spectrum (in particular, the eigenvalues and eigenvectors) of the closed-loop generator A^K. We give a useful characterization of that part of the spectrum σ(A^K) which lies in the resolvent set of A, the open-loop generator, via the “characteristic equation” involving the open-loop transfer function. We show that certain points of σ(A) cannot be eigenvalues of A^K if the input and output are scalar (so that K is a number) and K≠0. We devote special attention to the case when the output feedback operator K is compact. It is relatively easy to prove that in this case, σ_e(A), the essential spectrum of A, is invariant, that is, it is equal to σ_e(A^K). A related but much harder problem is to determine the largest subset of σ(A) which remains invariant under compact output feedback. This set, which we call the immovable spectrum of A, strictly contains σ_e(A). We give an explicit characterization of the immovable spectrum and we investigate the consequences of our results for a certain class of well-posed systems obtained by interconnecting an infinite chain of identical systems.     

On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs

It is known that if a Boolean function f in n variables has a DNF and a CNF of size then f also has a (deterministic) decision tree of size exp(O(log n log² N)). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp where N is the total number of monomials in minimal DNFs for f and ?f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs. One example results from the Bruen—Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably simple and combinatorially clear. Other examples have the additional property that f is in AC⁰. Received: June 5 1997.     

Inverting and noninverting H∞ controllers

It is well known that two-block S/KS/T H_∞ problems in which the plant is weighted at the output tend to invert the plant in the controller. This paper shows that even four-block S/KS/T problems in which the plant is weighted at the input result in controllers which invert the plant. However, if a GS/T weighting scheme is used where the weight for the sensitivity includes the plant, the inversion is avoided. This GS/T scheme therefore is especially suited for ill-conditioned plants. An example confirms these results.     

Reductions between disjoint NP-Pairs

Disjoint NP-pairs are pairs (A, B) of nonempty, disjoint sets in NP. We prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A, B, C, and D be nonempty sets belonging to NP. A smart reduction between the disjoint NP-pairs (A, B) and (C, D) is a Turing reduction with the additional property that if the input belongs to A B, then all queries belong to C D. We prove under the reasonable assumption that UP ∩ co-UP has a P-bi-immune set that there exist disjoint NP-pairs (A, B) and (C, D) such that (A, B) is truth-table reducible to (C, D), but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DistNP has a truth-table-complete disjoint NP-pair, but has no many-one-complete disjoint NP-pair.     

Steiner Minimal Trees with One Polygonal Obstacle

In this paper we study the Steiner minimal tree T problem for a point set Z with cardinality n and one polygonal obstacle ω in the Euclidean plane. We assume ω touches only one convex path in T that joins two terminals and that the number of extreme points of the obstacle is k . If all degree 2 vertices are omitted, then the topology of T is called the primitive topology of T . Given a full primitive topology along with ω convex, we prove that T can be determined in O(n ² +nlog ² k) time. Further, if ω is nonconvex, we then show that O(n ² +nklog k) time is required. Received April 16, 1996; revised August 18, 1997.     

A simple nc algorithm to recognize weakly triangulated graphs

Let S be a set of n closed intervals on the x-axis. A ranking assigns to each interval, s, a distinct rank, p(s)? [1, 2,…,n]. We say that s can see t if p(s)<p(t) and there is a point p?s∩t so that p?u for all u with p(s)<p(u)<p(t). It is shown that a ranking can be found in time O(n log n) such that each interval sees at most three other intervals. It is also shown that a ranking that minimizes the average number of endpoints visible from an interval can be computed in time O(n ^5/2). The results have applications to intersection problems for intervals, as well as to channel routing problems which arise in layouts of VLSI circuits.     

Sorting and Counting Networks of Arbitrary Width and Small Depth

We present the first construction for sorting and counting networks of arbitrary width that requires both small depth and small constant factors in the depth expression. Let w be the product w = p ₀ ⋅ p ₁ ⋅s p _n-1 , whose factors are not necessarily prime. We present a novel network construction of width w and depth O(n ² ) = O(log ² w) , using comparators (or balancers) of width less than or equal to max(p _i ) . This construction is practical in the sense that the asymptotic notation does not hide any large constants. An interesting aspect of this construction is that it establishes a family of sorting and counting networks of width w , one for each distinct factorization of w . A factorization in which max(p _i ) is large and n is small yields a network that trades small depth for large comparators (or balancers), and a factorization where max(p _i ) is small and n is large makes the opposite tradeoff. Received June 18, 2001. Online publication October 30, 2001.