The NP-hardness of many natural computational problems has become a strong obstacle to the real world of computing, where we are experiencing a pervasion of virtually all aspects of life by computers. Dealing with NP-hard problems in practice has become unavoidably important. A number of approaches have been proposed but none of them has perfectly satisfied the requirements posted in applications. This proposed research studies an alternative approach to NP-hard problems, parameterized computation, which has recently turned out to be very promising and useful, in particular when traditional approaches are not applicable. The research will emphasize the difference between parameterized computation and traditional computational approaches, and develop new and non-traditional algorithmic techniques that are effective and special for parameterized computation. More specifically, the following new algorithmic techniques in parameterized computation will be systematically investigated: (1) parameter dual bounds; (2) effective process of small unknown subsets; (3) new analysis techniques for parameterized algorithms; (4) parameterized computational lower bounds; and (5) parameterized algorithm libraries. The success of the proposed research will significantly advance our understanding on the concepts of computational tractability and intractability, and provide effective techniques and solutions for solving difficult computational problems in the real world of computing.
