Given a set of strings of equal length and an integer , the closest string problem (CSP) requires the computation of a string of length such that for each , where is the Hamming distance between and . The problem is N...
详细信息
Given a set of strings of equal length and an integer , the closest string problem (CSP) requires the computation of a string of length such that for each , where is the Hamming distance between and . The problem is NP-hard and has been extensively studied in the context of approximation algorithms and fixed-parameter algorithms. fixed-parameter algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized fixed-parameter algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their time complexities are also significantly better than the previously best known (deterministic) algorithms.
We study the weighted improper coloring problem, a generalization of defective coloring. We present some hardness results and in particular we show that weighted improper coloring is not fixed-parameter tractable when...
详细信息
We study the weighted improper coloring problem, a generalization of defective coloring. We present some hardness results and in particular we show that weighted improper coloring is not fixed-parameter tractable when parameterized by pathwidth. We generalize bounds for defective coloring to weighted improper coloring and give a bound for weighted improper coloring in terms of the sum of edge weights. Finally we give fixed-parameter algorithms for weighted improper coloring both when parameterized by treewidth and maximum degree and when parameterized by treewidth and precision of edge weights. In particular, we obtain a linear-time algorithm for weighted improper coloring of interval graphs of bounded degree.
We study the agreement supertree approach for combining rooted phylogenetic trees when the input trees do not fully agree on the relative positions of the taxa. We consider two ways to deal with such conflict. The fir...
详细信息
We study the agreement supertree approach for combining rooted phylogenetic trees when the input trees do not fully agree on the relative positions of the taxa. We consider two ways to deal with such conflict. The first is to contract a set of edges in the input trees so that the resulting trees have an agreement supertree. We show that this problem is NP-complete and give a fixed-parameter tractable (FPT) algorithm for the problem parameterized by the number of input trees and the number of edges contracted. The second approach is to remove a set of taxa from the input trees so that the resulting trees have an agreement supertree. Guillemot and Berry (2010) gave an FPT algorithm for this problem when the input trees are all binary. We give an FPT algorithm for the more general case where the input trees are allowed to have arbitrary degree.
The new sequencing technologies, called next-generation sequencing, provide a huge amount of data that can be used to reconstruct genomes. However, the methods applied to reconstruct genomes often are not able to reco...
详细信息
The new sequencing technologies, called next-generation sequencing, provide a huge amount of data that can be used to reconstruct genomes. However, the methods applied to reconstruct genomes often are not able to reconstruct a complete genome and provide only an incomplete information. Here we consider two combinatorial problems that aim to reconstruct complete genomes by inserting a collection of missing genes. The first problem we consider, called One-sided scaffold filling, given an incomplete genome B and a complete genome A, asks for the insertion of missing genes into an incomplete genome B with the goal of maximizing the common adjacencies between genomes B' (resulting from the insertion of missing genes in B) and A. The second problem, called Two-sided scaffold filling, given two incomplete genomes A, B, asks for the insertion of missing genes into both genomes so that the resulting genomes A' and B' have the same multiset of genes and the number of common adjacencies between A' and B' is maximized. Both problems were proved to be NP-hard, while their parameterized complexity, when the parameter is the number of common adjacencies of the resulting genomes, was left as an open problem. In this paper, we settle this open problem by presenting fixed-parameter algorithms for One-sided scaffold filling and Two-sided scaffold filling. (C) 2014 Elsevier B.V. All rights reserved.
We present the first fixed-parameter algorithm for constructing a tree-child phylo-genetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such net...
详细信息
We present the first fixed-parameter algorithm for constructing a tree-child phylo-genetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such networks. The algorithm uses the recently introduced framework of cherry picking sequences and runs in O ((8k)(k)poly(n, t)) time, where n is the number of leaves of every tree, t is the number of trees, and k is the reticulation number of the constructed network. Moreover, we provide an efficient parallel implementation of the algorithm and show that it can deal with up to 100 input trees on a standard desktop computer, thereby providing a major improvement over previous phylogenetic network construction methods.
We consider the SHORTEST ODD PATH problem, where given an undirected graph G, a weight function on its edges, and two vertices s and t in G, the aim is to find an (s, t)-path with odd length and, among all such paths,...
详细信息
We consider the SHORTEST ODD PATH problem, where given an undirected graph G, a weight function on its edges, and two vertices s and t in G, the aim is to find an (s, t)-path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the SHORTEST ODD PATH problem had been open for 20 years, and was recently shown to be NP-hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E- of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between SHORTEST ODD PATH and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edgeweighted graph. It also relies on solving an intermediary problem variant called SHORTEST PARITY-CONSTRAINED ODD PATH where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving SHORTEST ODD PATH. The first FPT algorithm is parameterized by |E-|, the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of G spanned by E-, when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G, and the algorithm does not rely on conservativeness. (c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC license (http://***/licenses/by- nc/4.0/).
N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicityN-fold IPs, which e...
详细信息
N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicityN-fold IPs, which encode IPs succinctly by presenting a description of each block type and a vector of block multiplicities. Our goal is to design algorithms which solve N-fold IPs in time polynomial in the size of the succinct encoding, which may be significantly smaller than the size of the explicit (non-succinct) instance. We present the first fixed-parameter algorithm for high-multiplicity N-fold IPs, which even works for convex objectives. Our key contribution is a novel proximity theorem which relates fractional and integer optima of the Configuration LP, a fundamental notion by Gilmore and Gomory [Oper. Res., 1961] which we generalize. Our algorithm for N-fold IP is faster than previous algorithms whenever the number of blocks is much larger than the number of block types, such as in N-fold IP models for various scheduling problems.
The DIRECTED FEEDBACK VERTEX SET (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp's 21 NP-complete problems. Resolving the parameter...
详细信息
The DIRECTED FEEDBACK VERTEX SET (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp's 21 NP-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. (2008) showed its fixed-parameter tractability via a 4kk!nO(1)-time algorithm, where k = |S|. Here we show fixed-parameter tractability of two generalizations of DFVS:center dot Find a smallest vertex set S such that every strong component of G - S has size at most s: we give an algorithm solving this problem in time 4k(ks + k + s)! middot nO(1). This generalizes an algorithm by Xiao (2017) for the undirected version of the *** dot Find a smallest vertex set S such that every non-trivial strong component of G - S is 1-out-regular: we give an algorithm solving this problem in time 2O(k3) middot nO(1). We also solve the corresponding arc versions of these problems by fixed-parameter algorithms. (c) 2022 Published by Elsevier B.V.
This paper deals with the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Previously, [Tofi...
详细信息
This paper deals with the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Previously, [Tofigh A, Hallett M, Lagergren J, Simultaneous identification of duplications and lateral gene transfers, IEEE/ACM Trans Comput Biol Bioinf 517-535, 2011.] gave a fixed-parameter algorithm for this problem that runs in O(m + 3(k)n) time, where m is the number of vertices in S, n is the number of vertices in G, and k is the minimum cost of an LCA-reconciliation between S and G. In this paper, by refining their algorithm, we obtain a new one for the same problem that finds and outputs the solutions in a compact form within O(mn(2) + 3(k)) time. In the most interesting case where 3(k) >= mn(2) , our algorithm is O(n) times faster.
In this paper, we study the problem of finding a minimum weight spanning tree that contains each vertex in a given subset VNT of vertices as an internal vertex. This problem, called MINIMUM WEIGHT NON-TERMINAL SPANNIN...
详细信息
In this paper, we study the problem of finding a minimum weight spanning tree that contains each vertex in a given subset VNT of vertices as an internal vertex. This problem, called MINIMUM WEIGHT NON-TERMINAL SPANNING TREE, includes s-t HAMILTONIAN PATH as a special case, and hence it is NP-hard. In this paper, we first observe that NON-TERMINAL SPANNING TREE, the unweighted counterpart of MINIMUM WEIGHT NON-TERMINAL SPANNING TREE, is already NP-hard on some special graph classes. Moreover, it is W[1]-hard when parameterized by clique- width. In contrast, we give a 3k-vertex kernel and O*(2k)-time algorithm, where k is the size of non-terminal set VNT. The latter algorithm can be extended to MINIMUM WEIGHT NON- TERMINAL SPANNING TREE with the restriction that each edge has a polynomially bounded integral weight. We also show that MINIMUM WEIGHT NON-TERMINAL SPANNING TREE is fixed- parameter tractable parameterized by the number of edges in the subgraph induced by the non-terminal set VNT, extending the fixed-parameter tractability of MINIMUM WEIGHT NON- TERMINAL SPANNING TREE to a more general case. Finally, we give several results for structural parameterization.
暂无评论