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.     

A low level component model easing performance portability of HPC applications

Scientific applications are getting increasingly complex, e.g., to improve their accuracy by taking into account more phenomena. Meanwhile, computing infrastructures are continuing their fast evolution. Thus, software engineering is becoming a major issue to offer ease of development, portability and maintainability while achieving high performance. Component based software engineering offers a promising approach that enables the manipulation of the software architecture of applications. However, existing models do not provide an adequate support for performance portability of HPC applications. This paper proposes a low level component model (L \(^2\) C) that supports inter-component interactions for typical scenarios of high performance computing, such as process-local shared memory and function invocation (C++ and Fortran), MPI, and Corba. To study the benefits of using L \(^2\) C, this paper walks through an example of stencil computation, i.e. a structured mesh Jacobi implementation of the 2D heat equation parallelized through domain decomposition. The experimental results obtained on the Grid’5000 testbed and on the Curie supercomputer show that L \(^2\) C can achieve performance similar to that of native implementations, while easing performance portability.     

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\) .     

Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs

The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in ${\mathcal {O}}^{*}(\alpha^{n})$ time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses ${\mathcal {O}}^{*}(1.657^{n})$ time and polynomial space. The Longest Cycle problem, in which the task is to find a cycle of maximum length, is a natural generalization of the Hamiltonian Cycle problem. For a claw-free graph G, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph H. Using this translation we obtain two deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses ${\mathcal {O}}^{*}(1.6818^{n})$ time and exponential space, and one algorithm that uses ${\mathcal {O}}^{*}(1.8878^{n})$ time and polynomial space.     

Fast Polynomial-Space Algorithms Using Inclusion-Exclusion

Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in $\mathcal{O}^{\star}(2^{k}c)$ time and $\mathcal{O}^{\star}(c)$ space, where the $\mathcal{O}^{\star}$ notation omits terms bounded by a polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give $\mathcal{O}^{\star}(2^{n})$ -time polynomial space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph.     

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.     

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.     

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.     

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}\) .     

Budget-bounded model-checking pushdown systems

We address the verification problem for concurrent programs modeled as multi-pushdown systems (MPDS). In general, MPDS are Turing powerful and hence come along with undecidability of all basic decision problems. Because of this, several subclasses of MPDS have been proposed and studied in the literature (Atig et al. in LNCS, Springer, Berlin, 2005; La Torre et al. in LICS, IEEE, 2007; Lange and Lei in Inf Didact 8, 2009; Qadeer and Rehof in TACAS, LNCS, Springer, Berlin, 2005). In this paper, we propose the class of bounded-budget MPDS, which are restricted in the sense that each stack can perform an unbounded number of context switches only if its depth is below a given bound, and a bounded number of context switches otherwise. We show that the reachability problem for this subclass is Pspace-complete and that LTL-model-checking is Exptime-complete. Furthermore, we propose a code-to-code translation that inputs a concurrent program \(P\) and produces a sequential program \(P'\) such that running \(P\) under the budget-bounded restriction yields the same set of reachable states as running \(P'\) . Moreover, detecting (fair) non-terminating executions in \(P\) can be reduced to LTL-Model-Checking of \(P'\) . By leveraging standard sequential analysis tools, we have implemented a prototype tool and applied it on a set of benchmarks, showing the feasibility of our translation.     

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\) .     

The PSurface library

We describe PSurface, a C $++$ library that allows to store and access piecewise linear maps between simplicial surfaces in $\mathbb{R }^2$ and $\mathbb{R }^3$ . Piecewise linear maps can be used, e.g., to construct boundary approximations for finite element grids, and grid intersections for domain decomposition methods. In computer graphics the maps allow to build level-of-detail representations as well as texture- and bump maps. The PSurface library can be used as the basis for the implementation of a wide range of algorithms that use piecewise linear maps between triangulated surfaces. A few simple examples are given in this work. We document the data structures and algorithms and show how PSurface is used in the numerical analysis framework Dune and the visualization software Amira.     

Ł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}\) .     

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.     

Frequency capping in online advertising

We study the following online problem. There are n advertisers. Each advertiser \(a_i\) has a total demand \(d_i\) and a value \(v_i\) for each supply unit. Supply units arrive one by one in an online fashion, and must be allocated to an agent immediately. Each unit is associated with a user, and each advertiser \(a_i\) is willing to accept no more than \(f_i\) units associated with any single user (the value \(f_i\) is called the frequency cap of advertiser \(a_i\) ). The goal is to design an online allocation algorithm maximizing the total value. We first show a deterministic \(3/4\) -competitiveness upper bound, which holds even when all frequency caps are \(1\) , and all advertisers share identical values and demands. A competitive ratio approaching \(1-1/e\) can be achieved via a reduction to a different model considered by Goel and Mehta (WINE ‘07: Workshop on Internet and Network, Economics: 335–340, 2007). Our main contribution is analyzing two \(3/4\) -competitive greedy algorithms for the cases of equal values, and arbitrary valuations with equal integral demand to frequency cap ratios. Finally, we give a primal-dual algorithm which may serve as a good starting point for improving upon the ratio of \(1-1/e\) .     

An integrated GA-DEA algorithm for determining the most effective maintenance policy for a k -out-of- n problem

This paper presents a novel hybrid GA-DEA algorithm in order to solve multi-objective \(k\) -out-of- \(n\) problem and determine preferred policy. The proposed algorithm maximizes overall system reliability and availability, while minimizing system cost and queue length, simultaneously. To meet these objectives, an adaptive hybrid GA-DEA algorithm is developed to identify the optimal solutions and improve computation efficiency. In order to improve computation efficiency genetic algorithm (GA) is used to simulate a series production line and find the Pareto-optimal solutions which are different values of \(k\) and \(n\) of \(k\) -out-of- \(n\) problem. Data envelopment analysis is used to find the best \(k\) and \(n\) from Genetic Algorithm’s Pareto solutions. An illustrative example is applied to show the flexibility and effectiveness of the proposed algorithm. The proposed algorithm of this study would help managers to identify the preferred policy considering and investigating various parameters and scenarios in logical time. Also considering different objectives result in Pareto-optimal solutions that would help decision makers to select the preferred solution based on their situation and preference.     

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.     

Query reverse engineering

In this paper, we introduce a new problem termed query reverse engineering (QRE). Given a database \(D\) and a result table \(T\) —the output of some known or unknown query \(Q\) on \(D\) —the goal of QRE is to reverse-engineer a query \(Q'\) such that the output of query \(Q'\) on database \(D\) (denoted by \(Q'(D)\) ) is equal to \(T\) (i.e., \(Q(D)\) ). The QRE problem has useful applications in database usability, data analysis, and data security. In this work, we propose a data-driven approach, TALOS for Tree-based classifier with At Least One Semantics, that is based on a novel dynamic data classification formulation and extend the approach to efficiently support the three key dimensions of the QRE problem: whether the input query is known/unknown, supporting different query fragments, and supporting multiple database versions.     

The Minimum Vulnerability Problem

We revisit the problem of finding \(k\) paths with a minimum number of shared edges between two vertices of a graph. An edge is called shared if it is used in more than one of the \(k\) paths. We provide a \({\lfloor {k/2}\rfloor }\) -approximation algorithm for this problem, improving the best previous approximation factor of \(k-1\) . We also provide the first approximation algorithm for the problem with a sublinear approximation factor of \(O(n^{3/4})\) , where \(n\) is the number of vertices in the input graph. For sparse graphs, such as bounded-degree and planar graphs, we show that the approximation factor of our algorithm can be improved to \(O(\sqrt{n})\) . While the problem is NP-hard, and even hard to approximate to within an \(O(\log n)\) factor, we show that the problem is polynomially solvable when \(k\) is a constant. This settles an open problem posed by Omran et al. regarding the complexity of the problem for small values of \(k\) . We present most of our results in a more general form where each edge of the graph has a sharing cost and a sharing capacity, and there is a vulnerability parameter \(r\) that determines the number of times an edge can be used among different paths before it is counted as a shared/vulnerable edge.     

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.