Compatibility of unrooted phylogenetic trees is FPT

A collection of _T1,_T2,…,_Tk$T_1,T_2,\dots ,T_k$ of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible   if there exists a tree T$T$ such that each tree _Ti$T_i$ can be obtained from T$T$ by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(n^k)$\mathrm{\Omega }(n^k)$ time, n$n$ being the number of leaves. Here, we present an O(nf(k))$\mathrm{O}(\mathit{nf}(k))$ algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable   (FPT) with respect to the number k$k$ of trees.     

Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

Computing phylogenetic roots with bounded degrees and errors is NP-complete

In this paper we study the computational complexity of the following optimization problem: given a graph G=(V,E)$G=(V,E)$, we wish to find a tree T such that (1) the degree of each internal node of T   is at least 3 and at most Δ$\Delta$, (2) the leaves of T are exactly the elements of V, and (3) the number of errors, that is, the symmetric difference between E   and {{u,v}:u,v$\{\{u,v\}:u,v$ are leaves of T   and _dT(u,v)≤k}$d_T(u,v)\le k\}$, is as small as possible, where _dT(u,v)$d_T(u,v)$ denotes the distance between u$u$ and v$v$ in tree T  . We show that this problem is NP-hard for all fixed constants Δ,k≥3$\Delta ,k\ge 3$.     

Topological additive numbering of directed acyclic graphs

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let D be a digraph and f   a labeling of its vertices with positive integers; denote by S(v)$S(v)$ the sum of labels over all neighbors of each vertex v. The labeling f is called topological additive numbering   if S(u)<S(v)$S(u)<S(v)$ for each arc (u,v)$(u,v)$ of the digraph. The problem asks to find the minimum number k for which D   has a topological additive numbering with labels belonging to {1,…,k}$\{1,\dots ,k\}$, denoted by _ηt(D)${\eta }_t(D)$.     

Choosing starting values for certain Newton–Raphson iterations

We aim at finding the best possible seed values when computing a^1/p$a^{1/p}$ using the Newton–Raphson iteration in a given interval. A natural choice of the seed value would be the one that best approximates the expected result. It turns out that in most cases, the best seed value can be quite far from this natural choice. When we evaluate a monotone function f(a)$f(a)$ in the interval [_amin,_amax]$[a_{\min },a_{\max }]$, by building the sequence _xn$x_n$ defined by the Newton–Raphson iteration, the natural choice consists in choosing _x0$x_0$ equal to the arithmetic mean of the endpoint values. This minimizes the maximum possible distance between _x0$x_0$ and f(a)$f(a)$. And yet, if we perform n$n$ iterations, what matters is to minimize the maximum possible distance between _xn$x_n$ and f(a)$f(a)$. In several examples, the value of the best starting point varies rather significantly with the number of iterations.     

Finding the nucleolus of any n-person cooperative game by a single linear program

In this paper we show a new method for calculating the nucleolus by solving a unique minimization linear program with O(4ⁿ)$O(4^n)$ constraints whose coefficients belong to {−1,0,1}$\{-1,0,1\}$. We discuss the need of having all these constraints and empirically prove that they can be reduced to O(_kmax2ⁿ)$O(k_{\mathit{max}}{2}^n)$, where k_max is a positive integer comparable with the number of players. A computational experience shows the applicability of our method over (pseudo)random transferable utility cooperative games with up to 18 players.     

On the partition dimension of a class of circulant graphs

For a vertex v   of a connected graph G(V,E)$G(V,E)$ and a subset S of V, the distance between a vertex v and S   is defined by d(v,S)=min{d(v,x):x∈S}$d(v,S)=\min \{d(v,x):x\in S\}$. For an ordered k  -partition π={_S1,_S2…_Sk}$\pi =\{S_1,S_2\dots S_k\}$ of V, the partition representation of v with respect to π is the k  -vector r(v|π)=(d(v,_S1),d(v,_S2)…d(v,_Sk))$r(v|\pi )=(d(v,S_1),d(v,S_2)\dots d(v,S_k))$. The k-partition π is a resolving partition if the k  -vectors r(v|π)$r(v|\pi )$, v∈V(G)$v\in V(G)$ are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. Salman et al. [1] in their paper which appeared in Acta Mathematica Sinica, English Series   proved that partition dimension of a class of circulant graph G(n,±{1,2})$G(n,\pm \{1,2\})$, for all even n?6$n?6$ is four. In this paper we prove that it is three.     

Fast algorithms for some dominating induced matching problems

We describe O(n)$O(n)$ time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n)$O(n)$ bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying these bounds, and employing existing O(n+m)$O(n+m)$ time algorithms we show that they can be reduced to O(n)$O(n)$ time. For claw-free graphs, we describe a variation of the existing algorithm for solving the unweighted version of the problem, which decreases its complexity from O(n²)$O(n^2)$ to O(n)$O(n)$, while additionally solving the weighted version. The same algorithm can be easily modified to count the number of DIM's of the given graph.     

Degree-constrained decompositions of graphs: Bounded treewidth and planarity

We study the problem of decomposing the vertex set V$V$ of a graph into two nonempty parts _V1,_V2$V_1,V_2$ which induce subgraphs where each vertex v∈_V1$v\in V_1$ has degree at least a(v)$a(v)$ inside _V1$V_1$ and each v∈_V2$v\in V_2$ has degree at least b(v)$b(v)$ inside _V2$V_2$. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible.     

The complexity of the zero-sum 3-flows

A zero-sum k-flow for a graph G   is a vector in the null-space of the 0,1$0,1$-incidence matrix of G   such that its entries belong to {±1,?,±(k−1)}$\{\pm 1,?,\pm (k-1)\}$. Akbari et al. (2009) [5] conjectured that if G is a graph with a zero-sum flow, then G   admits a zero-sum 6-flow. (2,3)$(2,3)$-semiregular graphs are an important family in studying zero-sum flows. Akbari et al. (2009) [5] proved that if Zero-Sum Conjecture is true for any (2,3)$(2,3)$-semiregular graph, then it is true for any graph. In this paper, we show that there is a polynomial time algorithm to determine whether a given (2,3)$(2,3)$-graph G   has a zero-sum 3-flow. In fact, we show that, there is a polynomial time algorithm to determine whether a given (2,4)$(2,4)$-graph G with n   vertices has a zero-sum 3-flow, where the number of vertices of degree four is O(log?n)$O(\log ?n)$. Furthermore, we show that it is NP-complete to determine whether a given (3,4)$(3,4)$-semiregular graph has a zero-sum 3-flow.     

On the privacy offered by (k, δ)-anonymity

The widespread deployment of technologies with tracking capabilities, like GPS, GSM, RFID and on-line social networks, allows mass collection of spatio-temporal data about their users. As a consequence, several methods aimed at anonymizing spatio-temporal data before their publication have been proposed in recent years. Such methods are based on a number of underlying privacy models. Among these models, (k,δ)-anonymity$(k,\delta )\mathrm{-}\mathrm{anonymity}$ claims to extend the widely used k  -anonymity concept by exploiting the spatial uncertainty δ≥0$\delta \ge 0$ in the trajectory recording process. In this paper, we prove that, for any δ>0$\delta >0$ (that is, whenever there is actual uncertainty), (k,δ)-anonymity$(k,\delta )\mathrm{-}\mathrm{anonymity}$ does not offer trajectory k-anonymity, that is, it does not hide an original trajectory in a set of k   indistinguishable anonymized trajectories. Hence, the methods based on (k,δ)-anonymity$(k,\delta )\mathrm{-}\mathrm{anonymity}$, like Never Walk Alone (NWA) and Wait For Me (W4M) can offer trajectory k  -anonymity only when δ=0$\delta =0$ (no uncertainty). Thus, the idea of exploiting the recording uncertainty δ$\delta$ to achieve trajectory k  -anonymity with information loss inversely proportional to δ$\delta$ turns out to be flawed.     

Optimal fault-tolerant embedding of paths in twisted cubes

The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let _TQn(V,E)${\mathit{TQ}}_n(V,E)$ denote the n-dimensional twisted cube. We prove that a path of length l   can be embedded between any two distinct nodes with dilation 1 for any faulty set F⊂V(_TQn)∪E(_TQn)$F\subset V({\mathit{TQ}}_n)\cup E({\mathit{TQ}}_n)$ with |F|?n-3$\left|F\right|?n-3$ and any integer l   with 2^n-1-1?l?|V(_TQn-F)|-1$2^{n-1}-1?l?|V({\mathit{TQ}}_n-F)|-1$ (n?3$n?3$). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l   and faulty set size |F|$\left|F\right|$ for a successful embedding are tight. That is, the result does not hold if l?2^n-1-2$l?2^{n-1}-2$ or |F|?n-2$\left|F\right|?n-2$. We also extend the result on (n-3)$(n-3)$-Hamiltonian connectivity of _TQn${\mathit{TQ}}_n$ in the literature.     

Fractional Adams–Moulton methods

In the simulation of dynamical systems exhibiting an ultraslow decay, differential equations of fractional order have been successfully proposed. In this paper we consider the problem of numerically solving fractional differential equations by means of a generalization of k  -step Adams–Moulton multistep methods. Our investigation is focused on stability properties and we determine intervals for the fractional order for which methods are at least A(π/2)$A(\pi /2)$-stable. Moreover we prove the A-stable character of k  -step methods for k=0$k=0$ and k=1$k=1$.     

On miniaturized problems in parameterized complexity theory

We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W[t]$\mathrm{W}[t]$ lies in W[t]$\mathrm{W}[t]$, too. In particular, the miniaturization of the dominating set problem is in W[2]$\mathrm{W}[2]$. Furthermore, we investigate the relation between f(k)·n^o(k)$f(k)·n^{\mathrm{o}(k)}$ time and subexponential time algorithms for the dominating set problem and for the clique problem.     

A note on scaling the Linpack benchmark

Dimensional analysis yields a new scaling formula for the Linpack benchmark. The computational power r(_p0,_q0)$r(p_0,q_0)$ on a set of processors decomposed into a (_p0,_q0)$(p_0,q_0)$ grid determines the computational power r(p,q)$r(p,q)$ on a set of processors decomposed into a (p,q)$(p,q)$ grid by the formula r(p,q)=(p/_p0)^α(q/_q0)^βr(_p0,_q0)$r(p,q)=(p/p_0{)}^{\alpha }(q/q_0{)}^{\beta }r(p_0,q_0)$. The two scaling parameters α$\alpha$ and β$\beta$ measure interprocessor communication overhead required by the algorithm. A machine that scales perfectly corresponds to α=β=1$\alpha =\beta =1$; a machine that scales not at all corresponds to α=β=0$\alpha =\beta =0$. We have determined the two scaling parameters by imposing a fixed-time constraint on the problem size such that the execution time remains constant as the number of processors changes. Results for a collection of machines confirm that the formula suggested by dimensional analysis is correct. Machines with the same values for these parameters are self-similar. They scale the same way even though the details of their specific hardware and software may be quite different.     

On mimicking networks representing minimum terminal cuts

Given a capacitated undirected graph G=(V,E)$G=(V,E)$ with a set of terminals K⊂V$K\subset V$, a mimicking network   is a smaller graph H=(_VH,_EH)$H=(V_H,E_H)$ which contains the set of terminals K   and for every bipartition [U,K−U]$[U,K-U]$ of the terminals, the cost of the minimum cut separating U   from K−U$K-U$ in G is exactly equal to the cost of the minimum cut separating U   from K−U$K-U$ in H.     

Chordless paths through three vertices

Consider the following problem, which we call “Chordless path through three vertices” or CP3V, for short: Given a simple undirected graph G=(V,E)$G=(V,E)$, a positive integer k, and three distinct vertices s, t  , and v∈V$v\in V$, is there a chordless path of length at most k from s   via v$v$ to t in G? In a chordless path, no two vertices are connected by an edge that is not in the path. Alternatively, one could say that the subgraph induced by the vertex set of the path in G is the path itself. The problem has arisen in the context of service deployment in communication networks. We resolve the parametric complexity of CP3V by proving it W[1]$W[1]$-complete with respect to its natural parameter k  . Our reduction extends to a number of related problems about chordless paths and cycles. In particular, deciding on the existence of a single directed chordless (s,t)$(s,t)$-path in a digraph is also W[1]$W[1]$-complete with respect to the length of the path.     

Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints

In this paper we consider the problem of scheduling n$n$ preemptive jobs on m$m$ machines with identical speed under machine availability and eligibility constraints when minimizing maximum lateness (_Lmax$(L_{\max }$). The lateness of a job is defined to be its completion time minus its due date, and _Lmax$L_{\max }$ is the maximum value of lateness among all jobs. We assume that each machine is not continuously available at all time throughout the planning horizon and each job is only allowed to be processed on specific machines. Network flow technique is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time two-phase binary search algorithm to verify the feasibility of the problem and to solve the scheduling problem optimally if a feasible schedule exists. Finally, we show that the time complexity of the algorithm is O((n+(2n+2x))³log(UB-LB))$O((n+(2n+2x){)}^3\log (\text{<italic>UB</italic>}-\text{<italic>LB</italic>}))$. Most literature in parallel machine scheduling assume that all machines are continuously available for processing and all jobs can be processed at any available machine throughout the planning horizon. But both assumptions might not be true in some practical environment, such as machine preventive maintenance and machines that have different capabilities to process jobs. This type of scheduling problem is seldom studied in the literature. The purpose of this paper is to examine the scheduling problem with machines with identical speed under machine availability and eligibility constraints. The objective is to minimize maximum lateness. We formulate this scheduling problem into a series of maximum flow problems with different values of _Lmax$L_{\max }$. A polynomial time two-phase binary search algorithm is proposed to verify the feasibility of the problem and to determine the optimal _Lmax$L_{\max }$.