Spreading of Messages in Random Graphs

Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds, of the Erdős-Rényi random graph G(n,p). Whenever more than a ρ∈(0,1) fraction of a vertex v’s neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower bounds on the minimum number of initial seeds, min-seed(n,p,d,r)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho), needed to convince a δ∈{1/n,…,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that min-seed(n,p,d,r)=W(min{d,r}n)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)=\Omega(\min\{\delta,\rho\}n) with probability 1−n ^−Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρ n) and (2) min-seed(n,p,d,1/2)=W(dn/ln(e/d))\mathrm{min\hbox{-}seed}(n,p,\delta,1/2)=\Omega(\delta n/\ln(e/\delta)) with probability 1−exp (−Ω(δ n))−n ^−Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p.     

Estimating the number of good permutations by a modified fast simulation method

A permutation (s₀, s₁,…, s_{N − 1}) of symbols 0, 1,…, N − 1 s called good if the set (t₀, t₁,…, t_{N − 1}) formed according to the rule t_i = i + s_i (mod N), i = 0, 1,…, N − 1, is a permutation too. A modified fast simulation method is proposed to evaluate the number of good permutations for N = 205 with a 5% relative error. Empirical upper and lower bounds for the number of good permutations are also given. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 101–109, July–August 2008.     

Applying fast simulation to find the number of good permutations

A permutation (s₀, s₁,…, s_{N − 1}) of symbols 0, 1,…, N − 1, is called good if the set (t₀, t₁,…, t_{N − 1}) formed according to the rule t_i = i + s_i (mod N), i = 0, 1, … N − 1, is also a permutation. A fast simulation method is proposed. It allows the number of good permutations to be evaluated with high accuracy for large N (in particular, N > 100). Empirical upper and lower bounds for the number of good permutations are presented and verified against numerical data. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 80–89, November–December 2007.     

Tensor and border rank of certain classes of matrices and the fast evaluation of determinant inverse matrix and eigenvalues

The tensor rankA of the linear spaceA generated by the set of linearly independent matricesA ₁, A₂, …, A_p, is the least integert for wich there existt diadsu ^(r) v ^(r)τ, τ=1,2,...,t, such that . IfA=n+k,k≪n then some computational problems concerning matricesA∈A can be solyed fast. For example the parallel inversion of almost any nonsingular matrixA∈A costs 3 logn+0(log² k) steps with max(n ²+p (n+k), k² n+nk) processors, the evaluation of the determinant ofA can be performed by a parallel algorithm in logp+logn+0 (log² k) parallel steps and by a sequential algorithm inn(1+k ²)+p (n+k)+0 (k ³) multiplications. Analogous results hold to accomplish one step of bisection method, Newton's iterations method and shifted inverse power method applied toA−λB in order to compute the (generalized) eigenvalues provided thatA, B∈A. The same results hold if tensor rank is replaced by border rank. Applications to the case of banded Toeplitz matrices are shown. Dedicated to Professor S. Faedo on his 70th birthday Part of the results of this paper has been presented at the Oberwolfach Conference on Komplexitatstheorie, November 1983     

On the Cardinality Spectrum and the Number of Latin Bitrades of Order 3

By a (Latin) unitrade of order k, we call a subset of vertices of the Hamming graph H(n, k) that intersects any maximal clique at either 0 or 2 vertices. A bitrade is a bipartite unitrade, i.e., a unitrade that can be split into two independent subsets. We study the cardinality spectrum of bitrades in the Hamming graph H(n, k) with k = 3 (ternary hypercube) and the growth of the number of such bitrades as n grows. In particular, we determine all possible small (up to 2.5·2n) and large (from 14·3n−3) cardinalities of bitrades of dimension n and prove that the cardinality of a bitrade takes only values equivalent to 0 or 2n modulo 3 (this result can be treated in terms of a ternary Reed-Muller type code). A part of the results are valid for an arbitrary k. For k = 3 and n → ∞ we prove that the number of nonequivalent bitrades is not less than 2(2/3−o(1))n and not greater than $$2^{\alpha^n}$$, α < 2 (the growth order of the double logarithm of this number remains unknown). Alternatively, the studied set Bn of bitrades of order 3 can be defined as follows: B0 consists of three rationals - 1, 0, 1; Bn consists of ordered triples (a, b, c) of elements from Bn−1 such that a + b + c = 0.     

Testing Periodicity

We study the string-property of being periodic and having periodicity smaller than a given bound. Let Σ be a fixed alphabet and let p,n be integers such that p ￡ \fracn2p\leq \frac{n}{2} . A length-n string over Σ, α=(α ₁,…,α _n ), has the property Period(p) if for every i,j∈{1,…,n}, α _i =α _j whenever i≡j (mod p). For an integer parameter g ￡ \fracn2,g\leq \frac{n}{2}, the property Period(≤g) is the property of all strings that are in Period(p) for some p≤g. The property Period( ￡ \fracn2)\mathit{Period}(\leq \frac{n}{2}) is also called Periodicity.     

LP-oriented upper bounds for the weighted stability number of a graph

Upper bounds for the weighted stability number of a graph are considered that are based on the approximation of its stable set polytope by linear inequalities for odd cycles and p-wheels in the graph. Algorithms are developed for finding upper bounds on the basis of solution of LP problems with a finite number of inequalities produced by the shortest path algorithm for a special graph. The results of test experiments are given for graphs with several hundred or thousand vertices. This work was partially financially supported by the CRDF Cooperative Grants Program under grant UKM2-2812-KV-06. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 157–170, January–February 2009.     

Efficient coding of labeled directed acyclic graphs

 We use an adaptation of the Prüfer code for trees to encode labeled directed acyclic graphs, which are often abbreviated to DAGs (or ADGs). In this paper, each DAG is assigned a unique DAG code, which allows an easy handling for several purposes. The set of all possible DAG codes (and therefore the set of all DAGs) for a fixed number of n vertices can be generated efficiently. Furthermore, we are able to rank DAGs, i.e., we provide an algorithm that assigns every DAG a unique number in the set {0,…,a _n −1}, where a _n is the cardinality of the set of labeled DAGs with n≥1 vertices, and we are able to unrank DAGs, which is the inverse operation. We also gain recurrence relations, which can be used to calculate a _n and a _n,q , i.e., the number of DAGs with n vertices and q edges. Finally, it is possible to generate, enumerate, rank and unrank DAGs with given number of edges and also DAGs with bounded indegree. RID="*" ID="*" This research was supported by the Austrian Science Fund (FWF), P13261-INF. I want to thank the reviewers, specially the one who suggested to add the algorithm for unranking DAG codes, for reading the paper very carefully and for the helpful comments.     

On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms

We present a time algorithm finding a minimum feedback vertex set in an undirected graph on n vertices. We also prove that a graph on n vertices can contain at most 1.8638 ⁿ minimal feedback vertex sets and that there exist graphs having 105 ^n/10≈1.5926 ⁿ minimal feedback vertex sets. Preliminary extended abstracts of this paper appeared in the proceedings of SWAT’06 [29] and IWPEC’06 [18]. Additional support of F.V. Fomin, S. Gaspers and A.V. Pyatkin by the Research Council of Norway. The work of A.V. Pyatkin was partially supported by grants of the Russian Foundation for Basic Research (project code 05-01-00395), INTAS (project code 04–77–7173). I. Razgon is supported by Science Foundation Ireland (Grant Number 05/IN/I886).     

Approximate Pattern Matching with the <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> and <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ ⁿ and a pattern string P∈Σ ^m , for each i=1,2,…,n−m+1 define L _p (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L _p distance is to compute L _p (i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L ₁ matching (pattern matching with an L ₁ distance) we show a reduction of the string matching with mismatches problem to the L ₁ matching problem and we present an algorithm that approximates the L ₁ matching up to a factor of 1+ε, which has an O(\frac1e²nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|) run time. Then, the L ₂ matching problem (pattern matching with an L ₂ distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L _∞ matching up to a factor of 1+ε with a run time of O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|) . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog ⁴ m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.     

Fault-Tolerant Embedding of Pairwise Independent Hamiltonian Paths on a Faulty Hypercube with Edge Faults

A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P ₁=〈u ₁,u ₂,…,u _n 〉 and P ₂=〈v ₁,v ₂,…,v _n 〉 of G are said to be independent if u ₁=v ₁, u _n =v _n , and u _i ≠v _i for all 1<i<n; and both are full-independent if u _i ≠v _i for all 1≤i≤n. Moreover, P ₁ and P ₂ are independent starting at u ₁, if u ₁=v ₁ and u _i ≠v _i for all 1<i≤n. A set of Hamiltonian paths {P ₁,P ₂,…,P _k } of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting at u ₁) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting at u ₁). A bipartite graph G is Hamiltonian-laceable if there exists a Hamiltonian path between any two vertices from different partite sets. It is well known that an n-dimensional hypercube Q _n is bipartite with two partite sets of equal size. Let F be the set of faulty edges of Q _n . In this paper, we show the following results:

Finite Element Approximation of a Three Dimensional Phase Field Model for Void Electromigration

We consider a finite element approximation of a phase field model for the evolution of voids by surface diffusion in an electrically conducting solid. The phase field equations are given by the nonlinear degenerate parabolic system

A generalized distribution model for random recursive trees

 A random tree T _n of order n is constructed by choosing in a random tree T _n-1 of order n−1 a vertex at random and connecting it to a new vertex labeled n. In the usual constraint we assume that the n−1 vertices of T _n-1 are equally likely to be chosen. We introduce and research a more general case in which a distribution of choosing vertices is defined by a sequence α₁, α₂, …. Received: 14 February 1995/2 January 1996     

Efficient Prüfer-Like Coding and Counting Labelled Hypertrees

We consider labelled r-uniform hypertrees, 2≤r≤n, where n is the number of vertices in the hypertree. Any two hyperedges in a hypertree share at most one vertex and each hyperedge in an r-uniform hypertree contains exactly r vertices. We show that r-uniform hypertrees can be encoded in linear time using as little as n−2 integers in the range [1,n]. The decoding algorithm also runs in linear time. For general hypertrees, we require codes of length n+p−2 where p is the number of vertices belonging to more than one hyperedge in the given hypertree. Based on our coding technique, we show that there are at most distinct labelled r-uniform hypertrees, where f(n,r) is a lower bound on the number of labelled trees with maximum (vertex) degree exceeding . We suggest a counting scheme for determining such a lower bound f(n,r).     

Windows scheduling of arbitrary-length jobs on multiple machines

The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I=〈(w ₁,ℓ ₁),(w ₂,ℓ ₂),…,(w _n ,ℓ _n )〉 of n pairs of positive integers that are associated with the jobs 1,2,…,n, respectively. The processing length of job i is ℓ _i slots where a slot is the processing time of one unit of length. The goal is to repeatedly and non-preemptively schedule all the jobs on the fewest possible machines such that the gap (window) between two consecutive beginnings of executions of job i is at most w _i slots. This problem arises in push broadcast systems in which data are transmitted on multiple channels. The problem is NP-hard even for unit-length jobs and a (1+ε)-approximation algorithm is known for this case by approximating the natural lower bound W(I)=?_i=1ⁿ(1/w_i)W(I)=\sum_{i=1}^{n}(1/w_{i}). The techniques used for approximating unit-length jobs cannot be extended for arbitrary-length jobs mainly because the optimal number of machines might be arbitrarily larger than the generalized lower bound W(I)=?_i=1ⁿ(l_i/w_i)W(I)=\sum_{i=1}^{n}(\ell_{i}/w_{i}). The main result of this paper is an 8-approximation algorithm for the WS problem with arbitrary lengths using new methods, different from those used for the unit-length case. The paper also presents another algorithm that uses 2(1+ε)W(I)+logw _max machines and a greedy algorithm that is based on a new tree representation of schedules. The greedy algorithm is optimal for some special cases, and computational experiments show that it performs very well in practice.     

Panconnectivity of Cartesian product graphs

A graph G of order n (≥2) is said to be panconnected if for each pair (x,y) of vertices of G there exists an xy-path of length ℓ for each ℓ such that d _G (x,y)≤ℓ≤n−1, where d _G (x,y) denotes the length of a shortest xy-path in G. In this paper, we consider the panconnectivity of Cartesian product graphs. As a consequence of our results, we prove that the n-dimensional generalized hypercube Q _n (k ₁,k ₂,…,k _n ) is panconnected if and only if k _i ≥3 (i=1,…,n), which generalizes a result of Hsieh et al. that the 3-ary n-cube Q³_nQ^{3}_{n} is panconnected.     

Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem

To construct the asymptotically optimum plan of the p-index axial assignment problem of order n, p algorithms α₀, α₁, ..., α _p−1 with complexities equal to O(n^p+1), O(n^p), ..., O(n²) operations, respectively, are proposed and substantiated under some additional conditions imposed on the coefficients of the objective function. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 176–181, November–December 2005.     

Lower Bounds for Agnostic Learning via Approximate Rank

We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of arbitrary real-valued functions. That is, suppose that there exist functions f₁, ?, f_r\phi_{1}, \ldots , \phi_{r} : {− 1, 1}ⁿ → \mathbbR{\mathbb{R}} with the property that every disjunction f on n variables has $\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3 for some reals a₁, ?, a_r\alpha_{1}, \ldots , \alpha_{r}. We prove that then $r \geq exp \{\Omega(\sqrt{n})\}$r \geq exp \{\Omega(\sqrt{n})\}, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority functions, we obtain a lower bound of W(2ⁿ/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2ⁿ for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi (1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal.     

On a reduction of the interval coloring problem to a series of bandwidth coloring problems

Given a graph G=(V,E) with strictly positive integer weights ω _i on the vertices i∈V, an interval coloring of G is a function I that assigns an interval I(i) of ω _i consecutive integers (called colors) to each vertex i∈V so that I(i)∩I(j)=∅ for all edges {i,j}∈E. The interval coloring problem is to determine an interval coloring that uses as few colors as possible. Assuming that a strictly positive integer weight δ _ij is associated with each edge {i,j}∈E, a bandwidth coloring of G is a function c that assigns an integer (called a color) to each vertex i∈V so that |c(i)−c(j)|≥δ _ij for all edges {i,j}∈E. The bandwidth coloring problem is to determine a bandwidth coloring with minimum difference between the largest and the smallest colors used. We prove that an optimal solution of the interval coloring problem can be obtained by solving a series of bandwidth coloring problems. Computational experiments demonstrate that such a reduction can help to solve larger instances or to obtain better upper bounds on the optimal solution value of the interval coloring problem.