Let c denote a non-negative constant. Suppose that we are given an edge-weighted bipartite graph G=(V,E) with its 2-layered drawing and a family X of intersecting edge pairs. We consider the problem of finding a maximum weighted matching M* such that each edge in M* intersects with at most c other edges in M*, and that all edge crossings in M* are contained in X. In the present paper, we propose polynomial-time algorithms for the problem for c=1 and 2. The time complexities of the algorithms are O((k+m)log n) for c=1 and O(m^4log n+k^3+n(k^2+log n)) for c=2, respectively, where n=|V|, m=|E| and k=|X|.
The MW-0-CPEMP is an extension of the longest common subsequence problem on given two sequences @cite_16 . It has an application in the sequence alignment problem that appears in bioinformatics @cite_12 and in natural language processing @cite_18 .
@cite_18 @cite_16 @cite_12
2115667895 2038268267 2583824051 2053947195
The longest common subsequence problem is examined from the point of view of parameterized computational complexity. There are several different ways in which parameters enter the problem, such as the number of sequences to be analyzed, the length of the common subsequence, and the size of the alphabet. Lower bounds on the complexity of this basic problem imply lower bounds on a number of other sequence alignment and consensus problems. An issue in the theory of parameterized complexity is whether a problem which takes input (x, k) can be solved in time ƒ(k) · nα where α is independent of k (termed fixed-parameter tractability). It can be argued that this is the appropriate asymptotic model of feasible computability for problems for which a small range of parameter values covers important applications — a situation which certainly holds for many problems in biological sequence analysis. Our main results show that: 1. (1) The longest common subsequence (LCS) parameterized by the number of sequences to be analyzed is hard for W[t] for all t. 2. (2) The LCS problem, parameterized by the length of the common subsequence, belongs to W[P] and is hard for W[2]. 3. (3) The LCS problem parameterized both by the number of sequences and the length of the common subsequence, is complete for W[1]. All of the above results are obtained for unrestricted alphabet sizes. For alphabets of a fixed size, problems (2) and (3) are fixed-parameter tractable. We conjecture that (1) remains hard. The problem of finding a longest common subsequence of two strings is discussed. This problem arises in data processing applications such as comparing two files and in genetic applications such as studying molecular evolution. The difficulty of computing a longest common subsequence of two strings is examined using the decision tree model of computation, in which vertices represent “equal - unequal” comparisons. It is shown that unless a bound on the total number of distinct symbols is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings. A general lower bound as a function of the ratio of alphabet size to string length is derived. The case where comparisons between symbols of the same string are forbidden is also considered and it is shown that this problem is of linear complexity for a two-symbol alphabet and quadratic for an alphabet of three or more symbols. We investigate combinatorial enumeration problems related to subsequences of strings; in contrast to substrings, subsequences need not be contiguous. For a finite alphabet E, the following three problems are solved. (1) Number of distinct subsequences: Given a sequence s ∈ Σ n and a nonnegative integer k ≤ n, how many distinct subsequences of length k does s contain? A previous result by Chase states that this number is maximized by choosing s as a repeated permutation of the alphabet. This has applications in DNA microarray production. (2) Number of ρ-restricted p-generated sequences: Given s ∈ Σ n and integers k ≥ 1 and p > 1, how many distinct sequences in Σ k contain no single nucleotide repeat longer than p and can be written as s[ r1 1 ... s rn n with 0 1, determine the number of sequences in E whose longest strictly increasing subsequence has length k, where 0 < k < K. This has applications to significance computations for chaining algorithms. Abstract In this paper we investigate the complexity of finding various kinds of common super- and subsequences with respect to one or two given sets of strings. We show that Longest Minimal Common Supersequence, Shortest Maximal Common Subsequence, and Shortest Maximal Common Non-Supersequence are MAX SNP-hard over a binary alphabet. Moreover, we show that Shortest Common Supersequence, Longest Common Subsequence, Longest Common Non-Supersequence, Shortest Common Non-Subsequence, and Longest Minimal Common Non-Supersequence are MAX SNP-hard over a binary alphabet if the number of zeros is fixed (by the instance). We show how these problems can be related to finding sequences consistent with respect to two given sets of strings. This leads to a unified approach for characterizing the complexity of such problems.