On extending de Bruijn sequences

We give a complete proof of the following theorem:Every de Bruijn sequence of order n in at least three symbols can be extended to a de Bruijn sequence of order n+1. Every de Bruijn sequence of order n in two symbols can not be extended to order n+1, but it can be extended to order n+2.     

A notion of cross-perfect bipartite graphs

In this note, we consider four quantities defined on a bipartite graph B: the cross-chromatic index χ∗(B), the biclique number w∗(B), the cross-free matching number m∗(B) and the biclique edge covering number β∗(B). We mention several applications of these numbers and define a notion of cross-perfect bipartite graphs. A duality between these numbers for the class of cross-perfect graphs is examined.     

On the Positive-Negative Partial Set Cover problem

The Positive-Negative Partial Set Cover problem is introduced and its complexity, especially the hardness-of-approximation, is studied. The problem generalizes the Set Cover problem, and it naturally arises in certain data mining applications.     

Lucky labelings of graphs

Suppose the vertices of a graph G were labeled arbitrarily by positive integers, and let S(v) denote the sum of labels over all neighbors of vertex v. A labeling is lucky if the function S is a proper coloring of G, that is, if we have S(u)≠S(v) whenever u and v are adjacent. The least integer k for which a graph G has a lucky labeling from the set {1,2,…,k} is the lucky number of G, denoted by η(G).Using algebraic methods we prove that η(G)?k+1 for every bipartite graph G whose edges can be oriented so that the maximum out-degree of a vertex is at most k. In particular, we get that η(T)?2 for every tree T, and η(G)?3 for every bipartite planar graph G. By another technique we get a bound for the lucky number in terms of the acyclic chromatic number. This gives in particular that for every planar graph G. Nevertheless we offer a provocative conjecture that η(G)?χ(G) for every graph G.     

A lower bound for the hitting set size for combinatorial rectangles and an application

We prove a lower bound of where for the hitting set size for combinatorial rectangles of volume at least ε in [m]^d space, for and d>2.     

Improved upper bounds on synchronizing nondeterministic automata

We show that i-directable nondeterministic automata can be i-directed with a word of length O(2ⁿ) for i=1,2, where n stands for the number of states. Since for i=1,2 there exist i-directable automata having i-directing words of length Ω(2ⁿ), these upper bounds are asymptotically optimal. We also show that a 3-directable nondeterministic automaton with n states can be 3-directed with a word of length , improving the previously known upper bound O(2ⁿ). Here the best known lower bound is .     

On the longest increasing subsequence of a circular list

The longest increasing circular subsequence (LICS) of a list is considered. A Monte Carlo algorithm to compute it is given which has worst case execution time O(n3/2logn) and storage requirement O(n). It is proved that the expected length μ(n) of the LICS satisfies . Numerical experiments with the algorithm suggest that .     

Local branching-based algorithms for the disjunctively constrained knapsack problem

The disjunctively constrained knapsack problem (DCKP) is a variant of the well-known single constrained knapsack problem with special disjunctive constraints. This paper investigates the use of the local branching techniques for solving large-scale DCKP. Three versions of the algorithm are considered. The first version is based on the standard local branching which uses a starting solution provided by a specialized rounding solution procedure. The second version applies a two-phase solution procedure embedded in the local branching. For each subtree, the procedure serves to construct the set of objects containing the assigned variables and a second set including the free variables. The first set provides a partial local solution to the DCKP, whereas, for the second set, a truncated exact tree-search is applied for completing the partial local feasible solution. Finally, a diversification strategy is considered constituting the third version of the algorithm. All versions of the proposed algorithm are computationally analyzed on a set of benchmark instances of the literature and the obtained solutions are compared to those provided by existing algorithms. Encouraging results have been obtained.     

Optimal register allocation for SSA-form programs in polynomial time

This paper gives a constructive proof that the register allocation problem for a uniform register set is solvable in polynomial time for SSA-form programs.     

Infinite words and biprefix codes

Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set {v_ii0} of (finite) words on A such that ƒ=v₀v₁…v_i…, {v_ii1} is a biprefix code and v_i≠v_j for positive integers i≠j.     

Hashiwokakero is NP-complete

In a Hashiwokakero puzzle, one must build bridges to connect a set of islands. We show that deciding the solvability of such puzzles is NP-complete.     

Online hypergraph coloring

In this paper we investigate the online hypergraph coloring problem. In this online problem the algorithm receives the vertices of the hypergraph in some order v₁,…,vn and it must color vi by only looking at the subhypergraph Hi=(Vi,Ei) where Vi={v₁,…,vi} and Ei contains the edges of the hypergraph which are subsets of Vi. We show that there exists no online hypergraph coloring algorithm with sublinear competitive ratio. Furthermore we investigate some particular classes of hypergraphs (k-uniform hypergraphs, hypergraphs with bounded matching number, projective planes), we analyse the online algorithm FF and give matching lower bounds for these classes.     

Maximum subset intersection

Consider the following problem. Given u sets of sets A₁,…,Au with elements over a universe E={e₁,…,en}, the goal is to select exactly one set from each of A₁,…,Au in order to maximize the size of the intersection of the sets. In this paper we present a gap-preserving reduction from Max-Clique which enables us to show that our problem cannot be approximated within an n1−? multiplicative factor, for any ?>0, unless P=NP (Zuckerman, 2006 [12]).