Note on maximal bisection above tight lower bound

In a graph G=(V,E), a bisection (X,Y) is a partition of V into sets X and Y such that |X|?|Y|?|X|+1. The size of (X,Y) is the number of edges between X and Y. In the Max Bisection problem we are given a graph G=(V,E) and are required to find a bisection of maximum size. It is not hard to see that ⌈|E|/2⌉ is a tight lower bound on the maximum size of a bisection of G.We study parameterized complexity of the following parameterized problem called Max Bisection above Tight Lower Bound (Max-Bisec-ATLB): decide whether a graph G=(V,E) has a bisection of size at least ⌈|E|/2⌉+k, where k is the parameter. We show that this parameterized problem has a kernel with O(k²) vertices and O(k³) edges, i.e., every instance of Max-Bisec-ATLB is equivalent to an instance of Max-Bisec-ATLB on a graph with at most O(k²) vertices and O(k³) edges.     

Codes and Bernoulli partitions

We associate to a maximal codeX on an alphabetA a dynamical system Ω; our main result proves that the property of unique decipherability implies that the partition of Ω associated to the letters ofA is a Bernoulli partition. Surprisingly it is possible to give two very different proofs of this result: the first one uses probability measures on monoids together with methods from automata theory; the other is based on results of entropy theory.     

On the bi-enhancement of chordal-bipartite probe graphs

Given a class C of graphs, a graph G=(V,E) is said to be a C-probe graph if there exists a stable (i.e., independent) set of vertices X⊆V and a set F of pairs of vertices of X such that the graph G^′=(V,E∪F) is in the class C. Recently, there has been increasing interest and research on a variety of C-probe graph classes, such as interval probe graphs, chordal probe graphs and chain probe graphs.In this paper we focus on chordal-bipartite probe graphs. We prove a structural result that if B is a bipartite graph with no chordless cycle of length strictly greater than 6, then B is chordal-bipartite probe if and only if a certain “enhanced” graph B^∗ is a chordal-bipartite graph. This theorem is analogous to a result on interval probe graphs in Zhang (1994) [18] and to one on chordal probe graphs in Golumbic and Lipshteyn (2004) [11].     

Exact exponential-time algorithms for finding bicliques

Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G=(V,E) on n vertices, a pair (X,Y), with X,Y⊆V, X∩Y=∅, is a non-induced biclique if {x,y}∈E for any x∈X and y∈Y. The NP-complete problem of finding a non-induced (k₁,k₂)-biclique asks to decide whether G contains a non-induced biclique (X,Y) such that |X|=k₁ and |Y|=k₂. In this paper, we design a polynomial-space O(n^1.6914)-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(n^1.30052). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(n^1.30052).     

On fuzzifications of discrete dynamical systems

Let X denote a locally compact metric space and φ : X → X be a continuous map. In the 1970s Zadeh presented an extension principle helping us to fuzzify the dynamical system (X, φ), i.e., to obtain a map Φ for the space of fuzzy sets on X. We extend an idea mentioned in [P. Diamond, A. Pokrovskii, Chaos, entropy and a generalized extension principle, Fuzzy Sets Syst. 61 (1994) 277-283] to generalize Zadeh’s original extension principle.In this paper we study basic properties of so-called g-fuzzifications, such as their continuity properties. We also show that, for any g-fuzzification: (i) a uniformly convergent sequence of uniformly continuous maps on X induces a uniformly convergent sequence of fuzzifications on the space of fuzzy sets and (ii) a conjugacy (resp., a semi-conjugacy) between two discrete dynamical systems can be extended to a conjugacy (resp., a semi-conjugacy) between fuzzified dynamical systems.Throughout this paper we consider different topological structures in the space of fuzzy sets, namely, the sendograph, endograph and levelwise topologies.     

On the structure of generalized rough sets

In this paper we consider some fundamental properties of generalized rough sets induced by binary relations on algebras and show that

1.

Any reflexive binary relation determines a topology.

2.

If θ is a reflexive and symmetric relation on a set X, then O={A⊆X|θ_-(A)=A} is a topology such that A is open if and only if it is closed.

3.

Conversely, for every topological space (X,O) satisfying the condition that A is open if and only if it is closed, there exists a reflexive and symmetric relation R such that O={A⊆X|R_-(A)=A}.

4.

Let θ be an equivalence relation on X. For any pseudo ω-closed subset A of X, θ₋(A) is an ω-closed set if and only if ω(x, x, … , x) ∈ θ₋(A) for any x ∈ X.

Moreover we consider properties of generalized rough sets.     

Edge-pancyclicity and path-embeddability of bijective connection graphs

An n-dimensional Bijective Connection graph (in brief BC graph) is a regular graph with 2ⁿ nodes and n2ⁿ⁻¹ edges. The n-dimensional hypercube, crossed cube, Möbius cube, etc. are some examples of the n-dimensional BC graphs. In this paper, we propose a general method to study the edge-pancyclicity and path-embeddability of the BC graphs. First, we prove that a path of length l with dist(X_n, x, y) + 2 ? l ? 2ⁿ − 1 can be embedded between x and y with dilation 1 in X_n for x, y ∈ V(X_n) with x ≠ y in X_n, where X_n (n ? 4) is a n-dimensional BC graph satisfying the three specific conditions and V(X_n) is the node set of X_n. Furthermore, by this result, we can claim that X_n is edge-pancyclic. Lastly, we show that these results can be applied to not only crossed cubes and Möbius cubes, but also other BC graphs except crossed cubes and Möbius cubes. So far, the research on edge-pancyclicity and path-embeddability has been limited in some specific interconnection architectures such as crossed cubes, Möbius cubes.     

On some subclasses of the class of generable languages

A [k]-machine is a quadruple M = (W, V, k, δ), where W ≠ Ø is a finite set, V ? W, k∈ {1, 2,?}, δ: V^k → (2W?{Ø}). A [k]-machine is of the type α (β) if δ: V^k → V (δ: V^k → (2V?{Ø})). The language of M is the set of all words (sequences of elements of V) “generated” by M. In the paper the languages of [k]-machines of type α and β are studied and their relations to the sets of computations of machines as mentioned in references are discussed. For a fixed finite set A the number of languages E is given for which E ? A^∞ (of sequences of elements of A) generated by [k]-machines of type α and β.     

Undecidability of the first-order arithmetic A[P(x), 2x, x + 1]

It is shown that the first-order arithmetic A[P(x), 2x, x + 1] with two functions 2x, x + 1 and a monadic predicate symbol P(x) is undecidable, by using a kind of two-dimensional finite automata, called finite causal ω²-systems. From this immediately follows R.M. Robinson's result, which says that the monadic second-order theory with two functions 2x, x + 1 is undecidable. This is also considered as an improvement on H. Putnam's result about the undecidability of the first-order arithmetic with addition and a monadic predicate symbol.     

Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems

In the Hitting Set problem, we are given a collection F of subsets of a ground set V and an integer p, and asked whether V has a p-element subset that intersects each set in F. We consider two parameterizations of Hitting Set below tight upper bounds, p=m−k and p=n−k. In both cases k is the parameter. We prove that the first parameterization is fixed-parameter tractable, but has no polynomial kernel unless coNP ⊆ NP/poly. The second parameterization is W[1]-complete, but the introduction of an additional parameter, the degeneracy of the hypergraph H=(V,F), makes the problem not only fixed-parameter tractable, but also one with a linear kernel. Here the degeneracy of H=(V,F) is the minimum integer d such that for each X⊂V the hypergraph with vertex set V?X and edge set containing all edges of F without vertices in X, has a vertex of degree at most d.In Nonblocker (Directed Nonblocker), we are given an undirected graph (a directed graph) G on n vertices and an integer k, and asked whether G has a set X of n−k vertices such that for each vertex y∉X there is an edge (arc) from a vertex in X to y. Nonblocker can be viewed as a special case of Directed Nonblocker (replace an undirected graph by a symmetric digraph). Dehne et al. (Proc. SOFSEM 2006) proved that Nonblocker has a linear-order kernel. We obtain a linear-order kernel for Directed Nonblocker.     

Monotonicity of maximal solutions of algebraic Riccati equations

A monotonicity result for the maximal solution of the equation XBB^*X − A^*X − XA − Q = 0, Q = Q^*, (A, B) stabilizable, is proved.     

The twin domination number in generalized de Bruijn digraphs

Let G=(V,A) be a digraph. A set T of vertices of G is a twin dominating set of G if for every vertex v∈V?T, there exist u,w∈T (possibly u=w) such that arcs (u,v),(v,w)∈A. The twin domination numberγ^∗(G) of G is the cardinality of a minimum twin dominating set of G. In this paper we investigate the twin domination number in generalized de Bruijn digraphs GB(n,d). For the digraphs GB(n,d), we first establish sharp bounds on the twin domination number. Secondly, we give the exact values of the twin domination number for several types of GB(n,d) by constructing minimum twin dominating sets in the digraphs. Finally, we present sharp upper bounds for some special generalized de Bruijn digraphs.     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

Efficient evaluation of specific queries in constraint databases

Let F₁,…,Fs∈R[X₁,…,Xn] be polynomials of degree at most d, and suppose that F₁,…,Fs are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F₁,…,Fs.For any point x∈Rn, we consider the task of determining the signs of the values F₁(x),…,Fs(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F₁,…,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)^O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal.By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F₁,…,Fs belong to Z[X₁,…,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F₁,…,Fs.     

A verifiable multi-secret sharing scheme based on cellular automata

In this paper, we propose a verifiable (t, n)-threshold multi-secret sharing scheme, based on one-dimensional cellular automata where the number of secrets is not restricted by n or t. We show that our scheme can be used to solve an open problem proposed recently in Alvarez et al. (2008) [G. Alvarez, L. Hernández Encinas, A. Martín del Rey, A multisecret sharing scheme for color images based on cellular automata, Information Sciences 178 (2008) 4382-4395].     

Stability of linear infinite-dimensional systems revisited

The paper is devoted to a study of stability questions for linear infinite-dimensional discrete-time and continuous-time systems. The concepts of power stability and l ^p Instability for a linear discrete-time system x _k+1 = Ax _k (where x _k ε X, X is a Banach space, A is linear and bounded) are introduced and studied. Relationships between these concepts and the inequality r(A) < 1, where r(A) denotes the spectral radius of A, are also given. The discrete-time results are used for a simple derivation of some well-known properties of exponentially stable and L^p-stable linear continuous-time systems described by [xdot](t) = Ax(t) (A generates here a strongly continuous semigroup of linear and bounded operators on X). Some remarks on norms related to stable systems are also included.     

On generalized language equations

A system of generalized language equations over an alphabet A is a set of n equations in n variables: X_i = G_i(X₁,..., X_n), i = 1,...,n, where the G_i are functions from [P(A^*)]ⁿ into P(A^*), i=1,..., n, P(A^*) denoting the set of all languages over A. Furthermore the G_i are expressible in terms of set-operations, concatenations, and stars which involve the variable X_i as well as certain mixed languages. In this note we investigate existence and uniqueness of solutions of a certain subclass of generalized language equations. Furthermore we show that a solution is regular if all fixed languages are regular.     

On Nonnegative matrices generating a finite multiplicative monoid

Square nonnegative matrices with the property that the multiplicative monoid M(A) generated by the matrix A is finite are characterized in several ways. At first, the least general upper bound for the cardinality of M(A) is derived. Then it is shown that any square nonnegative matrix is cogredient to a lower triangular block form with the diagonal consisting of three blocks L, A ₀, and M where L and M are strictly lower triangular, A ₀ has no zero rows or columns, and M(A) is finite if and only if. M(A ₀) is so. Several criteria for, M(A ₀) to be finite are presented. One of the normal forms of A applies very well to the characterization of the nonnegative solutions of each of the matrix equations X ^k = 0, X ^k = 1, X ^k = X, and X ^k = X ^T where k > 1 is an integer. It also leads to a polynomial time algorithm for deciding whether or not M(A) is finite, if the entries of A are nonnegative rationals.     

Bounded DOL languages

For an alphabet A and a morphism h : A¹ → A¹, the set of words w such that the DOL language L(A, h, w) is a BOUNDED language is shown to be B¹, where B is an effectively computable subset of A. Consequently, BOUNDEDNESS is decidable for DOL languages. The result depends on the authors' recent results on periodic DOL languages. Interpretation of the result for polynomially bounded DOL languages is also considered.     

Variance based sensitivity analysis of model output. Design and estimator for the total sensitivity index

Variance based methods have assessed themselves as versatile and effective among the various available techniques for sensitivity analysis of model output. Practitioners can in principle describe the sensitivity pattern of a model Y=f(X₁,X₂,…,Xk) with k uncertain input factors via a full decomposition of the variance V of Y into terms depending on the factors and their interactions. More often practitioners are satisfied with computing just k first order effects and k total effects, the latter describing synthetically interactions among input factors. In sensitivity analysis a key concern is the computational cost of the analysis, defined in terms of number of evaluations of f(X₁,X₂,…,Xk) needed to complete the analysis, as f(X₁,X₂,…,Xk) is often in the form of a numerical model which may take long processing time. While the computational cost is relatively cheap and weakly dependent on k for estimating first order effects, it remains expensive and strictly k-dependent for total effect indices. In the present note we compare existing and new practices for this index and offer recommendations on which to use.