Parameterized complexity of three edge contraction problems with degree constraints

For any graph class \(\mathcal{H}\) , the \(\mathcal{H}\) -Contraction problem takes as input a graph \(G\) and an integer \(k\) , and asks whether there exists a graph \(H\in \mathcal{H}\) such that \(G\) can be modified into \(H\) using at most \(k\) edge contractions. We study the parameterized complexity of \(\mathcal{H}\) -Contraction for three different classes \(\mathcal{H}\) : the class \(\mathcal{H}_{\le d}\) of graphs with maximum degree at most  \(d\) , the class \(\mathcal{H}_{=d}\) of \(d\) -regular graphs, and the class of \(d\) -degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters \(k\) , \(d\) , and \(d+k\) . Moreover, we show that \(\mathcal{H}\) -Contraction admits an \(O(k)\) vertex kernel on connected graphs when \(\mathcal{H}\in \{\mathcal{H}_{\le 2},\mathcal{H}_{=2}\}\) , while the problem is \(\mathsf{W}[2]\) -hard when \(\mathcal{H}\) is the class of \(2\) -degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that \(\mathcal{H}\) -Contraction admits a linear vertex kernel when \(\mathcal{H}\) is the class of cycles.     

The categories L-\mathbf{Top}_{0} and L-\mathbf{Sob} as epireflective hulls

We show that the category \(L\) - \(\mathbf{Top}_{0}\) of \(T_{0}\) - \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}\) of \(L\) -topological spaces and the category \(L\) - \(\mathbf{Sob}\) of sober \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}_{0}\) .     

Fault tolerance of hypercubes and folded hypercubes

Let \(G = (V,E)\) be a connected graph. The conditional edge connectivity \(\lambda _\delta ^k(G)\) is the cardinality of the minimum edge cuts, if any, whose deletion disconnects \(G\) and each component of \(G - F\) has \(\delta \ge k\) . We assume that \(F \subseteq E\) is an edge set, \(F\) is called edge extra-cut, if \(G - F\) is not connected and each component of \(G - F\) has more than \(k\) vertices. The edge extraconnectivity \(\lambda _\mathrm{e}^k(G)\) is the cardinality of the minimum edge extra-cuts. In this paper, we study the conditional edge connectivity and edge extraconnectivity of hypercubes and folded hypercubes.     

Richardson Extrapolation on Some Recent Numerical Quadrature Formulas for Singular and Hypersingular Integrals and Its Study of Stability

Recently, we derived some new numerical quadrature formulas of trapezoidal rule type for the integrals \(I^{(1)}[g]=\int ^b_a \frac{g(x)}{x-t}\,dx\) and \(I^{(2)}[g]=\int ^b_a \frac{g(x)}{(x-t)^2}\,dx\) . These integrals are not defined in the regular sense; \(I^{(1)}[g]\) is defined in the sense of Cauchy Principal Value while \(I^{(2)}[g]\) is defined in the sense of Hadamard Finite Part. With \(h=(b-a)/n, \,n=1,2,\ldots \) , and \(t=a+kh\) for some \(k\in \{1,\ldots ,n-1\}, \,t\) being fixed, the numerical quadrature formulas \({Q}^{(1)}_n[g]\) for \(I^{(1)}[g]\) and \(Q^{(2)}_n[g]\) for \(I^{(2)}[g]\) are $$\begin{aligned} {Q}^{(1)}_n[g]=h\sum ^n_{j=1}f(a+jh-h/2),\quad f(x)=\frac{g(x)}{x-t}, \end{aligned}$$ and $$\begin{aligned} Q^{(2)}_n[g]=h\sum ^n_{j=1}f(a+jh-h/2)-\pi ^2g(t)h^{-1},\quad f(x)=\frac{g(x)}{(x-t)^2}. \end{aligned}$$ We provided a complete analysis of the errors in these formulas under the assumption that \(g\in C^\infty [a,b]\) . We actually show that $$\begin{aligned} I^{(k)}[g]-{Q}^{(k)}_n[g]\sim \sum ^\infty _{i=1} c^{(k)}_ih^{2i}\quad \text {as}\,n \rightarrow \infty , \end{aligned}$$ the constants \(c^{(k)}_i\) being independent of \(h\) . In this work, we apply the Richardson extrapolation to \({Q}^{(k)}_n[g]\) to obtain approximations of very high accuracy to \(I^{(k)}[g]\) . We also give a thorough analysis of convergence and numerical stability (in finite-precision arithmetic) for them. In our study of stability, we show that errors committed when computing the function \(g(x)\) , which form the main source of errors in the rest of the computation, propagate in a relatively mild fashion into the extrapolation table, and we quantify their rate of propagation. We confirm our conclusions via numerical examples.     

Universal regular control for generic semilinear systems

We consider discrete-time projective semilinear control systems \(\xi _{t+1} = A(u_t) \cdot \xi _t\) , where the states \(\xi _t\) are in projective space \(\mathbb {R}\hbox {P}^{d-1}\) , inputs \(u_t\) are in a manifold \(\mathcal {U}\) of arbitrary finite dimension, and \(A :\mathcal {U}\rightarrow \hbox {GL}(d,\mathbb {R})\) is a differentiable mapping. An input sequence \((u_0,\ldots ,u_{N-1})\) is called universally regular if for any initial state \(\xi _0 \in \mathbb {R}\hbox {P}^{d-1}\) , the derivative of the time- \(N\) state with respect to the inputs is onto. In this paper, we deal with the universal regularity of constant input sequences \((u_0, \ldots , u_0)\) . Our main result states that generically in the space of such systems, for sufficiently large \(N\) , all constant inputs of length \(N\) are universally regular, with the exception of a discrete set. More precisely, the conclusion holds for a \(C^2\) -open and \(C^\infty \) -dense set of maps \(A\) , and \(N\) only depends on \(d\) and on the dimension of \(\mathcal {U}\) . We also show that the inputs on that discrete set are nearly universally regular; indeed, there is a unique non-regular initial state, and its corank is 1. In order to establish the result, we study the spaces of bilinear control systems. We show that the codimension of the set of systems for which the zero input is not universally regular coincides with the dimension of the control space. The proof is based on careful matrix analysis and some elementary algebraic geometry. Then the main result follows by applying standard transversality theorems.     

Isomorphisms and functors of fuzzy sets and cut systems

Any fuzzy set \(X\) in a classical set \(A\) with values in a complete (residuated) lattice \( Q\) can be identified with a system of \(\alpha \) -cuts \(X_{\alpha }\) , \(\alpha \in Q\) . Analogical results were proved for sets with similarity relations with values in \( Q\) (e.g. \( Q\) -sets), which are objects of two special categories \({\mathbf K}={Set}( Q)\) or \({SetR}( Q)\) of \( Q\) -sets, and for fuzzy sets defined as morphisms from an \( Q\) -set into a special \(Q\) -set \(( Q,\leftrightarrow )\) . These fuzzy sets can be defined equivalently as special cut systems \((C_{\alpha })_{\alpha }\) , called f-cuts. This equivalence then represents a natural isomorphism between covariant functor of fuzzy sets \(\mathcal{F}_{\mathbf K}\) and covariant functor of f-cuts \(\mathcal{C}_{\mathbf K}\) . In this paper, we prove that analogical natural isomorphism exists also between contravariant versions of these functors. We are also interested in relationships between sets of fuzzy sets and sets of f-cuts in an \(Q\) -set \((A,\delta )\) in the corresponding categories \({Set}( Q)\) and \({SetR}( Q)\) , which are endowed with binary operations extended either from binary operations in the lattice \(Q\) , or from binary operations defined in a set \(A\) by the generalized Zadeh’s extension principle. We prove that the resulting binary structures are (under some conditions) isomorphic.     

Greedy routing in small-world networks with power-law degrees

In this paper we study decentralized routing in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we consider a variant of J. Kleinberg’s grid-based small-world model in which (1) the number of long-range edges of each node is not fixed, but is drawn from a power-law probability distribution with exponent parameter \(\alpha \ge 0\) and constant mean, and (2) the long-range edges are considered to be bidirectional for the purposes of routing. This model is motivated by empirical observations indicating that several real networks have degrees that follow a power-law distribution. The measured power-law exponent \(\alpha \) for these networks is often in the range between 2 and 3. For the small-world model we consider, we show that when \(2 < \alpha < 3\) the standard greedy routing algorithm, in which a node forwards the message to its neighbor that is closest to the target in the grid, finishes in an expected number of \(O(\log ^{\alpha -1} n\cdot \log \log n)\) steps, for any source–target pair. This is asymptotically smaller than the \(O(\log ^2 n)\) steps needed in Kleinberg’s original model with the same average degree, and approaches \(O(\log n)\) as \(\alpha \) approaches 2. Further, we show that when \(0\le \alpha < 2\) or \(\alpha \ge 3\) the expected number of steps is \(O(\log ^2 n)\) , while for \(\alpha = 2\) it is \(O(\log ^{4/3} n)\) . We complement these results with lower bounds that match the upper bounds within at most a \(\log \log n\) factor.     

Informational correlation between two parties of a quantum system: spin-1/2 chains

We introduce the informational correlation \(E^{AB}\) between two interacting quantum subsystems \(A\) and \(B\) of a quantum system as the number of arbitrary parameters \(\varphi _i\) of a unitary transformation \(U^A\) (locally performed on the subsystem \(A\) ) which may be detected in the subsystem \(B\) by the local measurements. This quantity indicates whether the state of the subsystem \(B\) may be effected by means of the unitary transformation applied to the subsystem \(A\) . Emphasize that \(E^{AB}\ne E^{BA}\) in general. The informational correlations in systems with tensor product initial states are studied in more details. In particular, it is shown that the informational correlation may be changed by the local unitary transformations of the subsystem \(B\) . However, there is some non-reducible part of \(E^{AB}(t)\) which may not be decreased by any unitary transformation of the subsystem \(B\) at a fixed time instant \(t\) . Two examples of the informational correlations between two parties of the four-node spin-1/2 chain with mixed initial states are studied. The long chains with a single initially excited spin (the pure initial state) are considered as well.     

Growth rates for persistently excited linear systems

We consider a family of linear control systems \(\dot{x}=Ax+\alpha Bu\) on \(\mathbb {R}^d\) , where \(\alpha \) belongs to a given class of persistently exciting signals. We seek maximal \(\alpha \) -uniform stabilization and destabilization by means of linear feedbacks \(u=Kx\) . We extend previous results obtained for bidimensional single-input linear control systems to the general case as follows: if there exists at least one \(K\) such that the Lie algebra generated by \(A\) and \(BK\) is equal to the set of all \(d\times d\) matrices, then the maximal rate of convergence of \((A,B)\) is equal to the maximal rate of divergence of \((-A,-B)\) . We also provide more precise results in the general single-input case, where the above result is obtained under the simpler assumption of controllability of the pair \((A,B)\) .     

Fault tolerance in distributed systems using fused state machines

Replication is a standard technique for fault tolerance in distributed systems modeled as deterministic finite state machines (DFSMs or machines). To correct \(f\) crash or \(\lfloor f/2 \rfloor \) Byzantine faults among \(n\) different machines, replication requires \(nf\) backup machines. We present a solution called fusion that requires just \(f\) backup machines. First, we build a framework for fault tolerance in DFSMs based on the notion of Hamming distances. We introduce the concept of an ( \(f\) , \(m\) )-fusion, which is a set of \(m\) backup machines that can correct \(f\) crash faults or \(\lfloor f/2 \rfloor \) Byzantine faults among a given set of machines. Second, we present an algorithm to generate an ( \(f\) , \(f\) )-fusion for a given set of machines. We ensure that our backups are efficient in terms of the size of their state and event sets. Third, we use locality sensitive hashing for the detection and correction of faults that incurs almost the same overhead as that for replication. We detect Byzantine faults with time complexity \(O(n f)\) on average while we correct crash and Byzantine faults with time complexity \(O(n \rho f)\) with high probability, where \(\rho \) is the average state reduction achieved by fusion. Finally, our evaluation of fusion on the widely used MCNC’91 benchmarks for DFSMs shows that the average state space savings in fusion (over replication) is 38 % (range 0–99 %). To demonstrate the practical use of fusion, we describe its potential application to two areas: sensor networks and the MapReduce framework. In the case of sensor networks a fusion-based solution can lead to significantly fewer sensor-nodes than a replication-based solution. For the MapReduce framework, fusion can reduce the number of map-tasks compared to replication. Hence, fusion results in considerable savings in state space and other resources such as the power needed to run the backups.     

Łukasiewicz logic and Riesz spaces

We initiate a deep study of Riesz MV-algebras which are MV-algebras endowed with a scalar multiplication with scalars from \([0,1]\) . Extending Mundici’s equivalence between MV-algebras and \(\ell \) -groups, we prove that Riesz MV-algebras are categorically equivalent to unit intervals in Riesz spaces with strong unit. Moreover, the subclass of norm-complete Riesz MV-algebras is equivalent to the class of commutative unital C \(^*\) -algebras. The propositional calculus \({\mathbb R}{\mathcal L}\) that has Riesz MV-algebras as models is a conservative extension of ?ukasiewicz \(\infty \) -valued propositional calculus and is complete with respect to evaluations in the standard model \([0,1]\) . We prove a normal form theorem for this logic, extending McNaughton theorem for ? ukasiewicz logic. We define the notions of quasi-linear combination and quasi-linear span for formulas in \({\mathbb R}{\mathcal L},\) and relate them with the analogue of de Finetti’s coherence criterion for \({\mathbb R}{\mathcal L}\) .     

Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs

The Induced Graph Matching problem asks to find \(k\) disjoint induced subgraphs isomorphic to a given graph  \(H\) in a given graph \(G\) such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, among several other problems. We show that Induced Graph Matching is fixed-parameter tractable in \(k\) on claw-free graphs when \(H\) is a fixed connected graph, and even admits a polynomial kernel when  \(H\) is a complete graph. Both results rely on a new, strong, and generic algorithmic structure theorem for claw-free graphs. Complementing the above positive results, we prove \(\mathsf {W}[1]\) -hardness of Induced Graph Matching on graphs excluding \(K_{1,4}\) as an induced subgraph, for any fixed complete graph \(H\) . In particular, we show that Independent Set is \(\mathsf {W}[1]\) -hard on \(K_{1,4}\) -free graphs. Finally, we consider the complexity of Induced Graph Matching on a large subclass of claw-free graphs, namely on proper circular-arc graphs. We show that the problem is either polynomial-time solvable or \(\mathsf {NP}\) -complete, depending on the connectivity of \(H\) and the structure of \(G\) .     

Some kinds of primitive and non-primitive words

If the length of a primitive word \(p\) is equal to the length of another primitive word \(q\) , then \(p^{n}q^{m}\) is a primitive word for any \(n,m\ge 1\) and \((n,m)\ne (1,1)\) . This was obtained separately by Tetsuo Moriya in 2008 and Shyr and Yu in 1994. In this paper, we prove that if the length of \(p\) is divisible by the length of \(q\) and the length of \(p\) is less than or equal to \(m\) times the length of \(q\) , then \(p^{n}q^{m}\) is a primitive word for any \(n,m\ge 1\) and \((n,m)\ne (1,1)\) . Then we show that if \(uv,u\) are non-primitive words and the length of \(u\) is divisible by the length \(v\) or one of the length of \(u\) and \(uv\) is odd for any two nonempty words \(u\) and \(v\) , then \(u\) is a power of \(v\) .     

Finding peculiar compositions of two frequent strings with background texts

We consider mining unusual patterns from a set  \(T\) of target texts. A typical method outputs unusual patterns if their observed frequencies are far from their expectation estimated under an assumed probabilistic model. However, it is difficult for the method to deal with the zero frequency and thus it suffers from data sparseness. We employ another set  \(B\) of background texts to define a composition  \(xy\) to be peculiar if both \(x\) and  \(y\) are more frequent in  \(B\) than in  \(T\) and conversely \(xy\) is more frequent in  \(T\) . \(xy\) is unusual because \(x\) and  \(y\) are infrequent in  \(T\) while \(xy\) is unexpectedly frequent compared to  \(xy\) in  \(B\) . To find frequent subpatterns and infrequent patterns simultaneously, we develop a fast algorithm using the suffix tree and show that it scales almost linearly under practical settings of parameters. Experiments using DNA sequences show that found peculiar compositions basically appear in rRNA while patterns found by an existing method seem not to relate to specific biological functions. We also show that discovered patterns have similar lengths at which the distribution of frequencies of fixed length substrings begins to skew. This fact explains why our method can find long peculiar compositions.     

Resource Buying Games

In resource buying games a set of players jointly buys a subset of a finite resource set \(E\) (e.g., machines, edges, or nodes in a digraph). The cost of a resource \(e\) depends on the number (or load) of players using \(e\) , and has to be paid completely by the players before it becomes available. Each player \(i\) needs at least one set of a predefined family \({\mathcal S}_i\subseteq 2^E\) to be available. Thus, resource buying games can be seen as a variant of congestion games in which the load-dependent costs of the resources can be shared arbitrarily among the players. A strategy of player \(i\) in resource buying games is a tuple consisting of one of \(i\) ’s desired configurations \(S_i\in {\mathcal S}_i\) together with a payment vector \(p_i\in {\mathbb R}^E_+\) indicating how much \(i\) is willing to contribute towards the purchase of the chosen resources. In this paper, we study the existence and computational complexity of pure Nash equilibria (PNE, for short) of resource buying games. In contrast to classical congestion games for which equilibria are guaranteed to exist, the existence of equilibria in resource buying games strongly depends on the underlying structure of the families \({\mathcal S}_i\) and the behavior of the cost functions. We show that for marginally non-increasing cost functions, matroids are exactly the right structure to consider, and that resource buying games with marginally non-decreasing cost functions always admit a PNE.     

The Local Discontinuous Galerkin Method for the Fourth-Order Euler–Bernoulli Partial Differential Equation in One Space Dimension. Part II: A Posteriori Error Estimation

In this paper new a posteriori error estimates for the local discontinuous Galerkin (LDG) method for one-dimensional fourth-order Euler–Bernoulli partial differential equation are presented and analyzed. These error estimates are computationally simple and are obtained by solving a local steady problem with no boundary condition on each element. We use the optimal error estimates and the superconvergence results proved in Part I to show that the significant parts of the discretization errors for the LDG solution and its spatial derivatives (up to third order) are proportional to \((k+1)\) -degree Radau polynomials, when polynomials of total degree not exceeding \(k\) are used. These results allow us to prove that the \(k\) -degree LDG solution and its derivatives are \(\mathcal O (h^{k+3/2})\) superconvergent at the roots of \((k+1)\) -degree Radau polynomials. We use these results to construct asymptotically exact a posteriori error estimates. We further apply the results proved in Part I to prove that, for smooth solutions, these a posteriori LDG error estimates for the solution and its spatial derivatives at a fixed time \(t\) converge to the true errors at \(\mathcal O (h^{k+5/4})\) rate. We also prove that the global effectivity indices, for the solution and its derivatives up to third order, in the \(L^2\) -norm converge to unity at \(\mathcal O (h^{1/2})\) rate. Our proofs are valid for arbitrary regular meshes and for \(P^k\) polynomials with \(k\ge 1\) , and for periodic and other classical mixed boundary conditions. Our computational results indicate that the observed numerical convergence rates are higher than the theoretical rates. Finally, we present a local adaptive procedure that makes use of our local a posteriori error estimate.     

Quantum entropy-typical subspace and universal data compression

The quantum entropy-typical subspace theory is specified. It is shown that any \(\rho ^{\otimes n}\) with von Neumann \(\hbox {entropy}\le h\) can be preserved approximately by the entropy-typical subspace with \(\hbox {entropy}=h\) . This result implies an universal compression scheme for the case that the von Neumann entropy of the source does not exceed \(h\) .     

Strong Conflict-Free Coloring for Intervals

We consider the \(k\) -strong conflict-free ( \(k\) -SCF) coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval \(I\) of the family there are at least \(k\) colors each appearing exactly once in \(I\) . We first present a polynomial-time approximation algorithm for the general problem; the algorithm has approximation ratio 2 when \(k=1\) and \(5-\frac{2}{k}\) when \(k\ge 2\) . In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any \(k \ge 1\) . We also provide, in case \(k=O({{\mathrm{polylog}}}(n))\) , a quasipolynomial time algorithm to decide the existence of a \(k\) -SCF coloring that uses at most \(q\) colors.     

Generation of atomic NOON states via adiabatic passage

We propose a scheme for generating atomic NOON states via adiabatic passage. In the scheme, a double \(\Lambda \) -type three-level atom is trapped in a bimodal cavity, and two sets of \(\Lambda \) -type three-level atoms are translated into and outside of two single-mode cavities, respectively. The three cavities connected by optical fibers are always in vacuum states. After a series of operations and suitable interaction time, we can obtain arbitrary large- \(n\) NOON states of two sets of \(\Lambda \) -type three-level atoms in distant cavities by performing a single projective measurement on the double \(\Lambda \) -type three-level atom. Our scheme is robust against the spontaneous emissions of atoms, the decays of fibers, and photon leakage of cavities, due to the adiabatic elimination of atomic excited states and the application of adiabatic passage.