作者：
Chen, JECent S Univ
Coll Informat Sci & Engn Changsha 410083 Peoples R China
The theory of parameterized computation and complexity is a recently developed subarea in theoretical computer science. The theory is aimed at practically solving a large number of computational problems that are theo...
详细信息
The theory of parameterized computation and complexity is a recently developed subarea in theoretical computer science. The theory is aimed at practically solving a large number of computational problems that are theoretically intractable. The theory is based on the observation that many intractable computational problems in practice are associated with a parameter that varies within a small or moderate range. Therefore, by taking the advantages of the small parameters, many theoretically intractable problems can be solved effectively and practically. On the other hand, the theory of parameterized computation and complexity has also offered powerful techniques that enable us to derive strong computational lower bounds for many computational problems, thus explaining why certain theoretically tractable problems cannot be solved effectively and practically. The theory of parameterized computation and complexity has found wide applications in areas such as database systems, programming languages, networks, VLSI design, parallel and distributed computing, computational biology, and robotics. This survey gives an overview on the fundamentals, algorithms, techniques, and applications developed in the research of parameterized computation and complexity. We will also report the most recent advances and excitements, and discuss further research directions in the area.
Motivated by the practical application of protein structure-structure alignment, we have studied the problem of maximum common subgraph within the framework of parameterized complexity. We investigated the lower bound...
详细信息
ISBN:
(纸本)9789898425904
Motivated by the practical application of protein structure-structure alignment, we have studied the problem of maximum common subgraph within the framework of parameterized complexity. We investigated the lower bound for the exact algorithms of the problem. We proved it unlikely that there is an algorithm of time p(n,m) * k(o(m)) for the problem, where p is a polynomial function, k is a parameter of map width, and m and n are the numbers of vertices of the the two graphs respectively. In consideration of the upper bound of p(n,m)*k(m) based on the brute-force approach, our lower bound result is asymptotically tight. Although the algorithm with the running time p(n,m) k(m) could not be significantly improved from our lower bound result, it is still possible to develop efficient algorithms or the practical application of the protein structure-structure alignment. We developed an efficient algorithm integrating the color coding method and parameterized computation for identifying the maximum common subgraph of two prot structure graphs. We have applied the algorithm to protein structure-structure alignment and conducted experimental testing of more than 600 protein pairs. Our parameterized approach shows improvement in structure alignment efficiency and will be very useful for structure comparisons of proteins with large sizes.
parameterized computation is a recently proposed alternative approach to dealing with NP-hard *** efficient parameterized algorithms has become a very active research area in the current research in theoretical comput...
详细信息
parameterized computation is a recently proposed alternative approach to dealing with NP-hard *** efficient parameterized algorithms has become a very active research area in the current research in theoretical computer science. In this paper, we investigate a number of new algorithmic techniques that were proposed and initiated by ourselves in our research in parameterized computation. The techniques have proved to be very useful and promising,and have led to improved parameterized algorithms for many well-known NP-hard problems.
Based on well-known complexity theory conjectures, any polynomial-time kernelization algorithm for the NP-hard Line-Cover problem produces a kernel of size Omega(k2)\documentclass[12pt]{minimal} \usepackage{amsmath} \...
详细信息
Based on well-known complexity theory conjectures, any polynomial-time kernelization algorithm for the NP-hard Line-Cover problem produces a kernel of size Omega(k2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (k<^>2)$$\end{document}, where k is the size of the sought line cover. Motivated by the current research in massive data processing, we study the existence of kernelization algorithms with limited space and time complexity for Line-Cover. We prove that every kernelization algorithm for Line-Cover takes time Omega(nlogk+k2logk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (n \log k + k<^>2 \log k)$$\end{document}, and present a randomized kernelization algorithm for Line-Cover that produces a kernel of size bounded by k2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k<^>2$$\end{document}, and runs in time O(nlogk+k2(logkloglogk)2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}}(n \log k + k<^>2 (\log k \log \log k)<^>2)$$\end{document} and space O(k2log2k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}}(k<^>2\log <^>{2} k
We present a new parameterized algorithm for the feedback vertex set problem (fvs) on undirected graphs. We approach the problem by considering a variation of it, the disjoint feedback vertex set problem (disjoint-fvs...
详细信息
We present a new parameterized algorithm for the feedback vertex set problem (fvs) on undirected graphs. We approach the problem by considering a variation of it, the disjoint feedback vertex set problem (disjoint-fvs), which finds a feedback vertex set of size that has no overlap with a given feedback vertex set of the graph . We develop an improved kernelization algorithm for disjoint-fvs and show that disjoint-fvs can be solved in polynomial time when all vertices in have degrees upper bounded by three. We then propose a new branch-and-search process on disjoint-fvs, and introduce a new branch-and-search measure. The process effectively reduces a given graph to a graph on which disjoint-fvs becomes polynomial-time solvable, and the new measure more accurately evaluates the efficiency of the process. These algorithmic and combinatorial studies enable us to develop an -time parameterized algorithm for the general fvs problem, improving all previous algorithms for the problem.
We consider the problem of computing the squared volume of the largest j-simplex contained in an n-dimensional polytope presented by its vertices (a V-polytope). We show that the related decision problem is W[I]-compl...
详细信息
We consider the problem of computing the squared volume of the largest j-simplex contained in an n-dimensional polytope presented by its vertices (a V-polytope). We show that the related decision problem is W[I]-complete, with respect to the parameter j. We also improve the constant inapproximability factor given in [A. Packer, Polynomial-time approximation of largest simplices in V-polytopes, Discrete Appl. Math. 134 (1-3) (2004) 213-237], by showing that there are constants mu < 1, c > 1 such that it is NP-hard to approximate within a factor of c(mu n) the volume of the largest [mu n]-simplex contained in an n-dimensional polytope with O(n) vertices. (c) 2006 Elsevier B.V. All rights reserved.
The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are intere...
详细信息
The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are interested in whether the graph has a spanning tree with at least k internal vertices. Fomin et al. (2013) [4] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel, implying an 0*(8(k))-time parameterized algorithm. Using depth-2 local search, Knauer and Spoerhase (2015) [9] developed a (5/3)-approximation algorithm for the optimization version. We try deeper local search: We conduct a thorough combinatorial analysis on the obtained spanning trees and explore their algorithmic consequences. We first observe that from the spanning tree obtained by depth-3 local search, one can easily find a reducible structure and apply the reduction rule of Fomin et al. This gives an improved kernel of 2k vertices, and as a by-product, a deterministic algorithm running in time 0*(4(k)). We then go even deeper by considering the spanning tree obtained by depth-5 local search. It is shown that the number of internal vertices of this spanning tree is at least 2/3 of the maximum number a spanning tree can have, thereby delivering an improved approximation algorithm with ratio 1.5 for the problem. (C) 2016 Elsevier Inc. All rights reserved.
Motivated by the research in reconfigurable memory array structures, this paper studies the complexity and algorithms for the constrained minimum vertex cover problem on bipartite graphs (MIN-CVCB) defined as follows:...
详细信息
Motivated by the research in reconfigurable memory array structures, this paper studies the complexity and algorithms for the constrained minimum vertex cover problem on bipartite graphs (MIN-CVCB) defined as follows: given a bipartite graph G = (V, E) with vertex bipartition V = U boolean OR L and two integers k(u) and k(l), decide whether there is a minimum vertex cover in G with at most k(u) vertices in U and at most k(l) vertices in L. It is proved in this paper that the MIN-CVCB problem is NP-complete. This answers a question posed by Hasan and Liu. A parameterized algorithm is developed for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation theory are nicely combined and extended. The algorithm runs in time O(1.26(ku + kl) + (k(u) + k(l))\G\) and significantly improves previous algorithms for the problem. (C) 2003 Elsevier Inc. All rights reserved.
We study the theory and techniques developed in the research of parameterized intractability, emphasizing on parameterized hardness and completeness that imply (stronger) computational lower bounds for natural computa...
详细信息
We study the theory and techniques developed in the research of parameterized intractability, emphasizing on parameterized hardness and completeness that imply (stronger) computational lower bounds for natural computational problems. Moreover, the fundamentals of the structural properties in parameterized complexity theory, relationships to classical complexity theory and more recent developments in the area are also introduced.
We present an efficient parameterized algorithm solving the Set Packing problem, in which we assume that the size of the sets is bounded by m. In particular, if the size m of the sets is bounded by a constant, then ou...
详细信息
We present an efficient parameterized algorithm solving the Set Packing problem, in which we assume that the size of the sets is bounded by m. In particular, if the size m of the sets is bounded by a constant, then our algorithm is fixed-parameter tractable. For example, if the size of the sets is bounded by 3, then our algorithm runs in time O((5.7k)(k)n). (C) 2003 Elsevier Inc. All rights reserved.
暂无评论