We study the following combinatorial problem. Given a set of n y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers such that any two consecutive layers d...
详细信息
ISBN:
(纸本)9783031231001;9783031231018
We study the following combinatorial problem. Given a set of n y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers such that any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of wires) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. Deciding whether a given multiset of swaps admits a realizing tangle is known to be NP-hard [Yamanaka et al., CCCG 2018]. We prove that this problem remains NP-hard if every pair of wires swaps only a constant number of times. On the positive side, we improve the runtime of a previous exponential-time algorithm. We also show that the problem is in NP and fixed-parameter tractable with respect to the number of wires.
Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set T of binary b...
详细信息
Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set T of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an O(3(vertical bar X vertical bar) poly(vertical bar X vertical bar)) timealgorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.
Background: Over the past two decades, phylogenetic networks have been studied to model reticulate evolutionary events. The relationships among phylogenetic networks, phylogenetic trees and clusters serve as the basis...
详细信息
Background: Over the past two decades, phylogenetic networks have been studied to model reticulate evolutionary events. The relationships among phylogenetic networks, phylogenetic trees and clusters serve as the basis for reconstruction and comparison of phylogenetic networks. To understand these relationships, two problems are raised: the tree containment problem, which asks whether a phylogenetic tree is displayed in a phylogenetic network, and the cluster containment problem, which asks whether a cluster is represented at a node in a phylogenetic network. Both the problems are NP-complete. Results: A fast exponential-time algorithm for the cluster containment problem on arbitrary networks is developed and implemented in C. The resulting program is further extended into a computer program for fast computation of the Soft Robinson-Foulds distance between phylogenetic networks. Conclusions: Two computer programs are developed for facilitating reconstruction and validation of phylogenetic network models in evolutionary and comparative genomics. Our simulation tests indicated that they are fast enough for use in practice. Additionally, the distribution of the Soft Robinson-Foulds distance between phylogenetic networks is demonstrated to be unlikely normal by our simulation data.
The SUBSET SUM problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O*(2(n)(/2))-timealgorithm for SUBS...
详细信息
ISBN:
(纸本)9783959770019
The SUBSET SUM problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O*(2(n)(/2))-timealgorithm for SUBSET SUM by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O*(2((0.5-delta)n))-timealgorithm, with some constant delta > 0. Continuing an earlier work [STACS 2015], we study SUBSET SUM parameterized by the maximum bin size beta, defined as the largest number of subsets of the n input integers that yield the same sum. For every epsilon > 0 we give a truly faster algorithm for instances with beta <= 2((0.5- epsilon)n) as well as instances with beta >= 2(0)(.661n) Consequently, we also obtain a characterization in terms of the popular density parameter n/log(2)t: if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for SUBSET SUM and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.
We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly conc...
详细信息
ISBN:
(纸本)9783939897781
We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2(0.3399n) B-4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers.
It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O*(2(n)) time (O*(.) suppresses polynomial factors of the input length). In this short note, we show tha...
详细信息
It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O*(2(n)) time (O*(.) suppresses polynomial factors of the input length). In this short note, we show that for any constant r, SCS for strings of length at most r can be solved in time O*(2((1-c(r))n)) where c(r) = (1 + 2r(2))(-1). For this, we introduce so-called hierarchical graphs that allow us to reduce SCS on strings of length at most r to the directed rural postman problem on a graph with at most k = (1 - c(r))n weakly connected components. One can then use a recent O*(2(k)) timealgorithm by Gutin, Wahlstrom, and Yeo. (C) 2014 Elsevier B.V. All rights reserved.
Sorting by short block-moves is one of the several approaches recently used for genome rearrangement, and most of the minimum sorting questions by these approaches have been proved to be NP-complete or NP-hard or even...
详细信息
ISBN:
(纸本)9781424429011
Sorting by short block-moves is one of the several approaches recently used for genome rearrangement, and most of the minimum sorting questions by these approaches have been proved to be NP-complete or NP-hard or even PSPACE-complete. Nevertheless, the complexity of minimum sorting by block-moves remains unsolved, and approximation algorithms for it and polynomial-timealgorithms on special permutations fir it are continuously devised. This paper gives an exponential-time algorithm of minimum sorting by short block-moves, and verifies its practicability by a set of test data.
An L(2, 1)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are diff...
详细信息
An L(2, 1)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L(2, 1)-span of a graph is the minimum possible span of its L(2, 1)-labelings. We show how to compute the L(2, 1)-span of a connected graph in time O*(2.6488(n)). Previously published exact exponentialtimealgorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time O*(2.5944(n)) for claw-free graphs, and in time O*(2(n-r)(2 + n/r)(r)) for graphs having a dominating set of size r. (C) 2012 Elsevier B.V. All rights reserved.
An L(2, 1)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are diff...
详细信息
An L(2, 1)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L(2, 1)-span of a graph is the minimum possible span of its L(2, 1)-labelings. We show how to compute the L(2, 1)-span of a connected graph in time O*(2.6488(n)). Previously published exact exponentialtimealgorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time O*(2.5944(n)) for claw-free graphs, and in time O*(2(n-r)(2 + n/r)(r)) for graphs having a dominating set of size r. (C) 2012 Elsevier B.V. All rights reserved.
In this paper we introduce "hybrid" Max 2-CSP formulas consisting of "simple clauses", namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, which can be any i...
详细信息
In this paper we introduce "hybrid" Max 2-CSP formulas consisting of "simple clauses", namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, which can be any integer-valued functions of pairs of boolean variables. This allows an algorithm to use both efficient reductions specific to AND and OR clauses, and other powerful reductions that require the general CSP setting. We use new reductions introduced here, and recent reductions such as "clause-learning" and "2-reductions" generalized to our setting's mixture of simple and general clauses. We parametrize a hybrid instance by the fraction p of non-simple clauses. We give an exact, exponential-time but polynomial-space algorithm that is the fastest known for p = 0, which includes the well-studied Max 2-Sat problem but also instances with arbitrary mixtures of AND and OR clauses;for an m-clause instance it runs in time O*(2(m/6.321),.) The same algorithm is tied for fastest for general Max 2-CSP (p = 1), with running time O*(2(m/5.263)). The algorithm is the only one to treat mixtures of AND, OR, and general integer-valued clauses more efficiently than the general case, with intermediate running time bounds depending on the value of p. Since even a pure Max 2-Sat input instance may be transformed to a hybrid instance in the course of solving it, the algorithm's efficiency and generality go hand in hand. Our algorithm analysis and optimization use the familiar measure-and-conquer approach, but in a variation resulting in mathematical programs that are convex rather than quasi-convex, and can be solved efficiently and with a certificate of optimality. We produce a family of running-time upper-bound formulas, each optimized for instances with a particular value of p but valid for all instances. (C) 2011 Elsevier Inc. All rights reserved.
暂无评论