Graph burning is a discrete-time process that models the spread of social contagion. Initially, all vertices are unburned. In each round, one unburned vertex is selected and burned, while any unburned vertex that has a burned neighbour from the previous round also becomes burned. The burning number of a graph is the minimum number of rounds needed to burn the entire graph. In this paper, we study the burning number of graph powers. First, we show that for a connected graph~$G$, its graph power~$G^k$ contains a~$(k+1)^+$-branching tree as a spanning tree. A~$(k+1)^+$-branching tree is one in which all internal vertices have degree at least~$k+1$. We then show that $(k+1)^+$-branching trees on~$n$ vertices have burning number at most $\left\lceil{\sqrt{\frac{4(k-1)n}{k^2}}}~\right\rceil$. As the burning number of a graph is at most the burning number of any of its spanning trees, this gives an upper bound on the burning number of graph powers. We also derive an alternative upper bound on the burning number of~$k^+$-branching trees using the strongest currently known general burning number bound [Bastide et al.]. We then identify the ranges of~$k$ and~$n$ for which our bound outperforms or matches this alternative bound. Finally, we show that~$b(G^k) \le (1+o(1))\sqrt{n/k}$ based on the asymptotic burning number bound of Norin and Turcotte.

We introduce the concept of cyclic covers, which generalizes the classical notion of covers in strings. Given any string X , a factor W of X is called a cyclic cover if each position of X belongs to an occurrence of a cyclic shift of W in X . Two cyclic covers are distinct if one is not a cyclic shift of the other. The cyclic covers problem asks for all distinct cyclic covers of an input string X . We present an algorithm that solves the cyclic covers problem in O ( n log ⁡ n ) time, where n is the length of X . It is based on finding a well-structured set of standard occurrences of a constant number of factors of a cyclic cover candidate W , computing the regions of X covered by cyclic shifts of W , extending those factors, and taking the union of the results. • We introduce the cyclic cover problem. • Two cyclic covers are distinct if one is not a cyclic shift of the other. • The cyclic cover problem requires finding all distinct cyclic covers of X . • We show that for a string of length n, the cyclic cover problem can be solved in O ( n log ⁡ n ) time.

A consensus tree is a phylogenetic tree that summarizes the evolutionary relationships inferred from a collection of phylogenetic trees with the same set of leaf labels. Among the many types of consensus trees that have been proposed in the last fifty years, the frequency difference consensus tree is one of the more finely resolved types that retains a large amount of information. This article presents a new deterministic algorithm for constructing the frequency difference consensus tree. Given k phylogenetic trees with identical sets of n leaf labels, it runs in O ( k n log ⁡ n ) time, improving the best previously known solution. Furthermore, we demonstrate that the implementation of our algorithm is faster in practice than the prior implementations for the same problem.

Abstract We study applications of clustering (in particular, the Hamming k -center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices with clustered rows or columns, respectively. Our results in part can be regarded as an extension of the clustering-based approach to Boolean square matrix multiplication due to Arslan and Chidri (CSC 2011). We provide a simple and efficient deterministic algorithm for approximate matrix product of 0-1 matrices, where the additive error is proportional to the minimum maximum radius in an $${\ell }$$ ℓ -center clustering of the rows of the first matrix or an k -center clustering of the columns of the second matrix. We use the approximation algorithm as a preprocessing after which a query asking for the exact value of an arbitrary entry in the product matrix can be answered in time proportional to the additive error. As a consequence, we obtain a simple deterministic algorithm for the exact matrix product of 0-1 matrices. We also present an alternative simple deterministic algorithm for the exact product and in addition, faster analogous randomized algorithms for an approximate and the exact matrix products of 0-1 matrices based on randomized $${\ell }$$ ℓ - and k -center clustering.

We consider the fundamental problem of assigning distinct labels to agents in theprobabilistic model of population protocols. Our protocols operate under the assumptionthat the size n of the population is embedded in the transition function. W.h.p. (withhigh probability), they are silent, i.e., eventually each agent reaches its nal state andremains in it forever, and they are safe, i.e., never change a label that has already beenassigned to an agent. We provide efficient protocols for this problem complemented withtight lower bounds. Our fast labeling protocol uses only O((n logn)/ε) interactions w.h.p.,(2 + ε)n + O(na) states, and the label range [1,(1 + ε)n], where 1 ≥ ε > 0 and 0 < a < 1,while our nearly state-optimal protocol uses only n + 5√n + O(log logn) states, the labelrange [1,n], and w.h.p., O(n3) interactions.

We study the problems of computing the Voronoi diagram and a triangulation of a set of n 2 points with O ( log ⁡ n ) -bit coordinates in the Euclidean plane in a substantially sublinear in n number of rounds in the congested clique model with n nodes. First, we observe that if the points are uniformly at random distributed in a unit square then their Voronoi diagram within the square can be computed in O ( 1 ) rounds with high probability (w.h.p.). Next, we show that if a very weak smoothness condition is satisfied by an input set of n 2 points with O ( log ⁡ n ) -bit coordinates in the unit square then the Voronoi diagram of the point set within the unit square can be deterministically computed in O ( log ⁡ n ) rounds in this model. Finally, we present a deterministic O ( log ⁡ n ) -round protocol for a triangulation of n 2 points with O ( log ⁡ n ) -bit coordinates in the Euclidean plane. It relies on our novel method for extending triangulations of two planar point sets separated by a straight line to a complete triangulation of the union of the sets in O ( 1 ) rounds.

The problem of computing the longest common subsequence of two sequences ( LCS for short) is a classical and fundamental problem in computer science. In this article, we study four variants of LCS : the Repetition-Bounded Longest Common Subsequence problem ( RBLCS ), the Multiset-Restricted Common Subsequence problem ( MRCS ), the Two-Side-Filled Longest Common Subsequence problem ( 2FLCS ), and the One-Side-Filled Longest Common Subsequence problem ( 1FLCS ). Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O ( 1 . 4422 5 n ) -time, dynamic programming (DP) based algorithm for RBLCS was proposed, where the two input sequences have lengths n and p o l y ( n ) . Here, we first establish that each of MRCS , 1FLCS , and 2FLCS is polynomially equivalent to RBLCS . Then, we design a refined DP-based algorithm for RBLCS that runs in O ( 1 . 4142 2 n ) time, which implies that MRCS , 1FLCS , and 2FLCS can also be solved in O ( 1 . 4142 2 n ) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS .

Abstract We consider a graph orientation problem that can be viewed as a generalization of Minimum Graph Coloring. Our problem takes as input an undirected graph $$G = (V, E)$$ G = ( V , E ) in which every edge $$\{u, v\} \in E$$ { u , v } ∈ E has two (potentially different and not necessarily positive) weights representing the lengths of its two possible directions ( u , v ) and ( v , u ), and asks for an orientation, i.e., an assignment of a direction to each edge of G , such that the length of a longest simple directed path in the resulting directed graph is minimized. A longest path in a graph is not always a maximal path when some edges have negative lengths, so the problem has two variants depending on whether all simple directed paths or maximal simple directed paths only are taken into account in the definition. We prove that the problems are NP-hard to approximate even if restricted to subcubic planar graphs, and develop fast polynomial-time algorithms for both problem variants for three classes of graphs: path graphs, cycle graphs, and star graphs.

BACKGROUND: Protein-protein interaction (PPI) data is an important type of data used in functional genomics. However, high-throughput experiments are often insufficient to complete the PPI interactome of different organisms. Computational techniques are thus used to infer missing data, with link prediction being one such approach that uses the structure of the network of PPIs known so far to identify non-edges whose addition to the network would make it more sound, according to some underlying assumptions. Recently, a new idea called the L3 principle introduced biological motivation into PPI link predictions, yielding predictors that are superior to general-purpose link predictors for complex networks. Interestingly, the L3 principle can be interpreted in another way, so that other signatures of PPI networks can also be characterized for PPI predictions. This alternative interpretation uncovers candidate PPIs that the current L3-based link predictors may not be able to fully capture, underutilizing the L3 principle. RESULTS: In this article, we propose a formulation of link predictors that we call NormalizedL3 (L3N) which addresses certain missing elements within L3 predictors in the perspective of network modeling. Our computational validations show that the L3N predictors are able to find missing PPIs more accurately (in terms of true positives among the predicted PPIs) than the previously proposed methods on several datasets from the literature, including BioGRID, STRING, MINT, and HuRI, at the cost of using more computation time in some of the cases. In addition, we found that L3-based link predictors (including L3N) ranked a different pool of PPIs higher than the general-purpose link predictors did. This suggests that different types of PPIs can be predicted based on different topological assumptions, and that even better PPI link predictors may be obtained in the future by improved network modeling.

We combine two fundamental optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency and minimally resolved supertree into a new problem, which we call q-maximum rooted triplets consistency ( q -MAXRTC). It takes as input a set R of rooted, binary phylogenetic trees with three leaves each and asks for a phylogenetic tree with exactly q internal nodes that contains the largest possible number of trees from R . We prove that q -MAXRTC is NP-hard to approximate within a constant, develop polynomial-time approximation algorithms for different values of q , and show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much branching information. To demonstrate the algorithmic advantage of using trees with few internal nodes, we also propose a new algorithm for computing the rooted triplet distance that is faster than the existing algorithms when restricted to such trees.

We consider the fundamental problem of assigning distinct labels to agents in the probabilistic model of population protocols. Our protocols operate under the assumption that the size n of the population is embedded in the transition function. Their efficiency is expressed in terms of the number of states utilized by agents, the size of the range from which the labels are drawn, and the expected number of interactions required by our solutions. Our primary goal is to provide efficient protocols for this fundamental problem complemented with tight lower bounds in all the three aspects. W.h.p. (with high probability), our labeling protocols are silent, i.e., eventually each agent reaches its final state and remains in it forever, and they are safe, i.e., never update the label assigned to any single agent. We first present a silent w.h.p. and safe labeling protocol that draws labels from the range [1,2n]. Both the number of interactions required and the number of states used by the protocol are asymptotically optimal, i.e., O(n log n) w.h.p. and O(n), respectively. Next, we present a generalization of the protocol, where the range of assigned labels is [1,(1+ε) n]. The generalized protocol requires O(n log n / ε) interactions in order to complete the assignment of distinct labels from [1,(1+ε) n] to the n agents, w.h.p. It is also silent w.h.p. and safe, and uses (2+ε)n+O(n^c) states, for any positive c < 1. On the other hand, we consider the so-called pool labeling protocols that include our fast protocols. We show that the expected number of interactions required by any pool protocol is ≥ (n²)/(r+1), when the labels range is 1,… , n+r < 2n. Furthermore, we provide a protocol which uses only n+5√ n +O(n^c) states, for any c < 1, and draws labels from the range 1,… ,n. The expected number of interactions required by the protocol is O(n³). Once a unique leader is elected it produces a valid labeling and it is silent and safe. On the other hand, we show that (even if a unique leader is given in advance) any silent protocol that produces a valid labeling and is safe with probability > 1-(1/n), uses ≥ n+√{(n-1)/2}-1 states. Hence, our protocol is almost state-optimal. We also present a generalization of the protocol to include a trade-off between the number of states and the expected number of interactions. Finally, we show that for any silent and safe labeling protocol utilizing n+t < 2n states, the expected number of interactions required to achieve a valid labeling is ≥ (n²)/(t+1).

Abstract The rooted triplet distance measures the structural dissimilarity of two phylogenetic trees or phylogenetic networks by counting the number of rooted phylogenetic trees with exactly three leaf labels (called rooted triplets, or triplets for short) that occur as embedded subtrees in one, but not both, of them. Suppose that $$N_1 = (V_1, E_1)$$ N 1 = ( V 1 , E 1 ) and $$N_2 = (V_2, E_2)$$ N 2 = ( V 2 , E 2 ) are phylogenetic networks over a common leaf label set of size n, that $$N_i$$ N i has level $$k_i$$ k i and maximum in-degree $$d_i$$ d i for $$i \in \{1,2\}$$ i ∈ { 1 , 2 } , and that the networks’ out-degrees are unbounded. Write $$N = \max (|V_1|, |V_2|)$$ N = max ( | V 1 | , | V 2 | ) , $$M = \max (|E_1|, |E_2|)$$ M = max ( | E 1 | , | E 2 | ) , $$k = \max (k_1, k_2)$$ k = max ( k 1 , k 2 ) , and $$d = \max (d_1, d_2)$$ d = max ( d 1 , d 2 ) . Previous work has shown how to compute the rooted triplet distance between $$N_1$$ N 1 and $$N_2$$ N 2 in $$\mathrm {O}(n \log n)$$ O ( n log n ) time in the special case $$k \le 1$$ k ≤ 1 . For $$k > 1$$ k > 1 , no efficient algorithms are known; applying a classic method from 1980 by Fortune et al. in a direct way leads to a running time of $${\Omega

In functional genomics, experimentally obtained protein-protein interaction (PPI) data is often incomplete. To deal with this issue, computational approaches are used to infer missing data and to evaluate confidence scores. Link prediction is one such approach that uses the structure of the network of PPIs known so far to find good candidates for missing PPIs. In a recent study by Kovács et al., a novel PPI-specific link predictor was proposed. Their link predictor is biologically motivated by the so-called L3 principle and it was shown to be superior to other general link predictors when applied to PPI data. However, the L3 link predictor is only an approximate implementation of the L3 principle. As such, not only is the full potential of the L3 principle not realized, it may even penalize candidate PPIs that otherwise fit the L3 principle. In this paper, we formulate an L3-based link predictor without approximation, coined ExactL3. We show computationally that ExactL3 is better than the previously proposed methods on four major PPI datasets (STRING, BioGRID, IntAct/HuRI, and MINT). The predicted PPIs are also shown to be much more functionally relevant. This confirms that ExactL3 is a better link predictor for PPI networks, and demonstrates its ability to characterize PPIs by only the topological features of binary PPI networks.

In this paper, we study exact, exponential-time algorithms for a variant of the classic Longest Common Subsequence problem called the Repetition-Bounded Longest Common Subsequence problem (or RBLCS , for short): Let an alphabet S be a finite set of symbols and an occurrence constraint C o c c be a function C o c c : S → N , assigning an upper bound on the number of occurrences of each symbol in S . Given two sequences X and Y over the alphabet S and an occurrence constraint C o c c , the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s ∈ S appears at most C o c c ( s ) times in the obtained subsequence. The special case where C o c c ( s ) = 1 for every symbol s ∈ S is known as the Repetition-Free Longest Common Subsequence problem ( RFLCS ) and has been studied previously; e.g., in [1] , Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS . However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. Without loss of generality, we will assume that | X | ≤ | Y | and | X | = n . In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O ( 1.44225 n ) . Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O ( 1.44225 n ) for any occurrence constraint C o c c , and even less in certain special cases. In particular, for RFLCS , our DP-based algorithm runs in O ( 1.41422 n ) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances.

We combine two fundamental, previously studied optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency (MAXRTC) and minimally resolved supertree (MINRS) into a new problem, which we call q-maximum rooted triplets consistency (q-MAXRTC). The input to our new problem is a set R of resolved triplets (rooted, binary phylogenetic trees with three leaves each) and the objective is to find a phylogenetic tree with exactly q internal nodes that contains the largest possible number of triplets from R. We first prove that q-MAXRTC is NP-hard even to approximate within a constant ratio for every fixed q >= 2, and then develop various polynomial-time approximation algorithms for different values of q. Next, we show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much triplet branching information. As an extreme example, we show that allowing only nine internal nodes is still sufficient to capture on average 80% of the rooted triplets from some recently published trees, each having between 760 and 3081 internal nodes. Finally, to demonstrate the algorithmic advantage of using trees with few internal nodes, we propose a new algorithm for computing the rooted triplet distance between two phylogenetic trees over a leaf label set of size n that runs in O(q n) time, where q is the number of internal nodes in the smaller tree, and is therefore faster than the currently best algorithms for the problem (with O(n log n) time complexity [SODA 2013, ESA 2017]) whenever q = o(log n).

The tree inclusion problem is, given two node-labeled trees P and T (the "pattern tree" and the "text tree"), to locate every minimal subtree in T (if any) that can be obtained by applying a sequence of node insertion operations to P. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is from 1995 and runs in O(poly(m,n) * 2^{2d}) = O^*(2^{2d}) time, where m and n are the sizes of the pattern and text trees, respectively, and d is the maximum outdegree of the pattern tree. Here, we develop a new algorithm that improves the exponent 2d to d by considering a particular type of ancestor-descendant relationships and applying dynamic programming, thus reducing the time complexity to O^*(2^d). We then study restricted variants of the unordered tree inclusion problem where the number of occurrences of different node labels and/or the input trees' heights are bounded. We show that although the problem remains NP-hard in many such cases, it can be solved in polynomial time for c = 2 and in O^*(1.8^d) time for c = 3 if the leaves of P are distinctly labeled and each label occurs at most c times in T. We also present a randomized O^*(1.883^d)-time algorithm for the case that the heights of P and T are one and two, respectively.

This article presents two new deterministic algorithms for constructing consensus trees. Given an input of phylogenetic trees with identical leaf label sets and leaves each, the first algorithm constructs the majority rule (+) consensus tree in time, which is optimal since the input size is , and the second one constructs the frequency difference consensus tree in time.

This article presents a fast algorithm for finding the Adams consensus tree of a set of conflicting phylogenetic trees with identical leaf labels. Its worst-case running time is O(knlog⁡n), where k is the number of input trees and n is the size of the leaf label set; in comparison, the original algorithm of Adams has a worst-case running time of O(kn2). To achieve subquadratic running time, the centroid path decomposition technique is applied in a novel way that traverses the input trees by following a centroid path in each of them in unison. For k=2, an even faster algorithm running in O(n⋅log⁡nlog⁡log⁡n) time is provided, which relies on an extension of the wavelet tree-based technique of Bose et al. for orthogonal range counting on a grid. Our extended wavelet tree data structure also supports truncated range maximum/minimum queries efficiently.

This article studies the parameterized complexity of the unification problem with associative, commutative, or associative-commutative functions with respect to the parameter “number of variables”. It is shown that if every variable occurs only once then both of the associative and associative-commutative unification problems can be solved in polynomial time, but that in the general case, both problems are W[1]-hard even when one of the two input terms is variable-free. For commutative unification, an algorithm whose time complexity depends exponentially on the number of variables is presented; moreover, if a certain conjecture is true then the special case where one input term is variable-free belongs to FPT. Some related results are also derived for a natural generalization of the classic string and tree edit distance problems that allows variables.

In this paper, we have extended the concept of unordered tree inclusion to take the costs of insertions and substitutions into account. The resulting algorithm, MinCostIncl, has the same time complexity as the original algorithm of [4] for unordered tree inclusion (O(22Dmn)). Computational experiments on a large synthetic dataset as well as real datasets showed that our proposed algorithm is fast and scalable. Source codes of the implemented algorithms are available upon request.

The problem of constructing a minimally resolved phylogenetic supertree (i.e., having the smallest possible number of internal nodes) that contains all of the rooted triplets from a consistent set R is known to be NP-hard. In this paper, we prove that constructing a phylogenetic tree consistent with R that contains the minimum number of additional rooted triplets is also NP-hard, and develop exact, exponential-time algorithms for both problems. The new algorithms are applied to construct two variants of the local consensus tree; for any set S of phylogenetic trees over some leaf label set L, this gives a minimal phylogenetic tree over L that contains every rooted triplet present in all trees in S, where ``minimal'' means either having the smallest possible number of internal nodes or the smallest possible number of rooted triplets. The second variant generalizes the RV-II tree, introduced by Kannan, Warnow, and Yooseph in 1998.

A consensus tree is a single phylogenetic tree that summarizes the branching structure in a given set of conflicting phylogenetic trees. Many different types of consensus trees have been proposed in the literature; three of the most well-known and widely used ones are the majority rule consensus tree , the loose consensus tree , and the greedy consensus tree . This article presents new deterministic algorithms for constructing them that are faster than all the previously known ones. Given k phylogenetic trees with n leaves each and with identical leaf label sets, our algorithms run in O ( nk ) time (majority rule consensus tree), O ( nk ) time (loose consensus tree), and O ( n 2 k ) time (greedy consensus tree). Our algorithms for the majority rule consensus and the loose consensus trees are optimal since the input size is Ω( nk ). Experimental results show that the algorithms are fast in practice.

This paper presents a fast algorithm for finding the Adams consensus tree of a set of conflicting phylogenetic trees with identical leaf labels, for the first time improving the time complexity of a widely used algorithm invented by Adams in 1972 [1]. Our algorithm applies the centroid path decomposition technique [9] in a new way to traverse the input trees' centroid paths in unison, and runs in O(k n \log n) time, where k is the number of input trees and n is the size of the leaf label set. (In comparison, the old algorithm from 1972 has a worst-case running time of O(k n^2).) For the special case of k = 2, an even faster algorithm running in O(n \cdot \frac{\log n}{\log\log n}) time is provided, which relies on an extension of the wavelet tree-based technique by Bose et al. [6] for orthogonal range counting on a grid. Our extended wavelet tree data structure also supports truncated range maximum queries efficiently and may be of independent interest to algorithm designers.

This paper considers the problem of identifying all locations of subtrees in a large tree or in a large collection of trees that are similar to a specified pattern tree, where all trees are assumed to be rooted and node-labeled. The tree edit distance is a widely-used measure of tree (dis-)similarity, but is NP-hard to compute for unordered trees. To cope with this issue, we propose a new similarity measure which extends the concept of unordered tree inclusion by taking the costs of insertion and substitution operations on the pattern tree into account, and present an algorithm for computing it. Our algorithm has the same time complexity as the original one for unordered tree inclusion, i.e., it runs in O(|T1∥T2|) time, where T1and T2denote the pattern tree and the text tree, respectively, when the maximum outdegree of T1is bounded by a constant. Our experimental evaluation using synthetic and real datasets confirms that the proposed algorithm is fast and scalable and very useful for bibliographic matching, which is a typical entity resolution problem for tree-structured data. Furthermore, we extend our algorithm to also allow a constant number of deletion operations on T1while still running in O(|T1∥T2|) time.

A consensus tree is a single phylogenetic tree that summarizes the branching structure in a given set of conflicting phylogenetic trees. Many different types of consensus trees have been proposed in the literature; three of the most well-known and widely used ones are the majority rule consensus tree, the loose consensus tree, and the greedy consensus tree. This paper presents new deterministic algorithms for constructing them that are faster than all the previously known ones. Given k phylogenetic trees with n leaves each and with identical leaf label sets, our algorithms run in O(nk log k) time (majority rule consensus tree), O(nk) time (loose consensus tree), and O(n2k) time (greedy consensus tree).

The previously fastest algorithms for computing the R* consensus tree of two given (rooted) phylogenetic trees with a leaf label set of cardinality n run in Θ(n 3) time (Bryant and Berry in Adv. Appl. Math. 27(4):705–732, 2001; Kannan et al. in SIAM J. Comput. 27(6):1695–1724, 1998). In this manuscript, we describe a new $O(n^{2} \sqrt{\log n})$ -time algorithm to solve the problem. This is a significant improvement because the R* consensus tree is defined in terms of a set $\mathcal {R}_{\mathit{maj}}$ which may contain Ω(n 3) elements, so any direct approach that explicitly constructs $\mathcal {R}_{\mathit{maj}}$ requires Ω(n 3) time.

A recursive algorithm by Aho et al. [SIAM J. Comput., 10 (1981), pp. 405–421] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis, Ph.D. thesis, University of Canterbury, Christchurch, New Zealand, 1997], the tree output by the algorithm of Aho et al. is not always minimal; there may exist other trees which contain fewer nodes yet are still consistent with the input. In this paper, we prove strong polynomial-time inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MinRS). Furthermore, we show that the decision version of MinRS is NP-hard for any fixed positive integer $q\geq4$, where q is the number of allowed internal nodes, but linear-time solvable for $q\leq3$. In contrast, MinRS becomes polynomial-time solvable for any q when restricted to caterpillars. We also present an exponential-time algorithm based on tree separators for solving MinRS exactly. It runs in $2^{O(n\log p)}$ time when every node may have at most p children that are internal nodes and where n is the cardinality of the leaf label set. Finally, we demonstrate that augmenting the algorithm of Aho et al. with an algorithm for optimal graph coloring to help merge certain blocks of leaves during the execution does not improve the output solution much in the worst case.

BACKGROUND: To characterize the diversity of bacterial populations in metagenomic studies, sequencing reads need to be accurately assigned to taxonomic units in a given reference taxonomy. Reads that cannot be reliably assigned to a unique leaf in the taxonomy (ambiguous reads) are typically assigned to the lowest common ancestor of the set of species that match it. This introduces a potentially severe error in the estimation of bacteria present in the sample due to false positives, since all species in the subtree rooted at the ancestor are implicitly assigned to the read even though many of them may not match it. RESULTS: We present a method that maps each read to a node in the taxonomy that minimizes a penalty score while balancing the relevance of precision and recall in the assignment through a parameter q. This mapping can be obtained in time linear in the number of matching sequences, because LCA queries to the reference taxonomy take constant time. When applied to six different metagenomic datasets, our algorithm produces different taxonomic distributions depending on whether coverage or precision is maximized. Including information on the quality of the reads reduces the number of unassigned reads but increases the number of ambiguous reads, stressing the relevance of our method. Finally, two measures of performance are described and results with a set of artificially generated datasets are discussed. CONCLUSIONS: The assignment strategy of sequencing reads introduced in this paper is a versatile and a quick method to study bacterial communities. The bacterial composition of the analyzed samples can vary significantly depending on how ambiguous reads are assigned depending on the value of the q parameter. Validation of our results in an artificial dataset confirm that a combination of values of q produces the most accurate results.

We investigate the computational complexity of inferring a smallest possible multilabeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. This problem has not been studied previously in the literature. We prove that even the very restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is an NP-hard problem. Furthermore, we show that the general minimization problem is difficult to approximate, although a simple polynomial-time approximation algorithm achieves an approximation ratio close to our derived inapproximability bound. Finally, we provide an exact algorithm for the problem running in exponential time and space. As a by-product, we also obtain new, strong inapproximability results for two partitioning problems on directed graphs called ACYCLIC PARTITION and ACYCLIC TREE-PARTITION.

We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. This problem is closely related to the job scheduling on parallel machines, called the machine covering problem, where its goal is to assign jobs to parallel machines such that each machine is covered as much as possible. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 = ¿ for constant ¿ > 0 in polynomial time unless P = NP, even if all edge weights belong to {2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time wmax/wmin- approximation algorithm for MAXMINO where wmaxand wmindenote the maximum and minimum weights among all the input edges. Furthermore we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than wminis at most logarithmic in the number of vertices. Finally, we, show that MAXMINO is solvable in polynomial time if the input is a cactus graph.

This paper considers the problem of determining whether a given set $\T$ of rooted triplets can be merged without conflicts into a galled phylogenetic network and, if so, constructing such a network. When the input $\T$ is dense, we solve the problem in $O(|\T|)$ time, which is optimal since the size of the input is $\Theta(|\T|)$. In comparison, the previously fastest algorithm for this problem runs in $O(|\T|^2)$ time. We also develop an optimal $O(|\T|)$-time algorithm for enumerating all simple phylogenetic networks leaf-labeled by L that are consistent with $\T$, where L is the set of leaf labels in $\T$, which is used by our main algorithm. Next, we prove that the problem becomes NP-hard if extended to nondense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set $\T$ of rooted triplets on n leaves such that any galled network can be consistent with at most $0.4883 \cdot |\T|$ of the rooted triplets in $\T$. On the other hand, we provide a polynomial-time approximation algorithm that always outputs a galled network consistent with at least a factor of $\frac{5}{12}$ ($> 0.4166$) of the rooted triplets in $\T$.