Computational Upper and Lower Bounds via Parameterized Complexity

点击翻译按钮获取中文摘要

Many well-known NP-hard problems can be solved by straightforward enumeration algorithms of running time O(nk). For example, the clique problem (determine if a given graph of n vertices has a clique of k vertices) can be solved in time O(nk) by simply enumerating all subsets of k vertices in the graph. Based on the widely accepted assumptions in parameterized complexity theory, this proposed research will develop powerful new lower bound techniques to prove that the above enumeration algorithms are essentially the best possible solutions for a large group of well-known NP-hard problems. For example, it will be proved that the clique problem requires time n(k) even if one restricts the parameter values k to be of the order of any fixed function (n) n/ log n. The lower bound techniques will also provide new methods for the study of the trade-off between approximation ratio and running time of approximation algorithms, and for deriving computational lower bounds on polynomial time approximation schemes for certain NP-hard problems, in particular for some problems arising in computational biology. New design and analysis techniques for the development of improved algorithms will also be investigated for well-known parameterized problems with important applications in the real-world of computing. The intellectual merit of the proposed activity. Computational lower bounds have been one of the most difficult topics in the study in theoretical computer science. The proposed research will tackle this difficult problem by introducing a new methodology based on parameterized complexity theory, by which computational lower bounds on well-known NP-hard problems can be effectively derived. The research will also study new design and analysis techniques for the development of improved algorithms for important parameterized problems in practical applications. Our research agenda is motivated by, and will build on, the success we have already achieved recently in our current study on parameterized computation and complexity. The proposed research will significantly advance the understanding on the concepts of computational tractability and computational intractability, from both theoretical and practical points of view. The broader impacts resulting from the proposed activity. Progress made in this proposed research will have significant impact in education, science, and computational technology. First of all, the proposed research will be expected to strongly interact on other research fields in science and engineering, leading to collaborations of interdisciplinary research in Texas A&M University. The project will establish an excellent environment to broaden students' knowledge and research experience, benefit the undergraduate and graduate students from all areas involved in the research, and encourage underrepresented minorities and women to participate in advanced research. The results produced by the proposed research will enhance the undergraduate and graduate curriculum in computer science education.