Parameterized NP-hard problems are NP-hard problems that are associated with
special variables called parameters. One example of the problem is to find simple
paths of length k in a graph, where the integer k is the parameter. We call this
problem the p-path problem. The p-path problem is the parameterized version of
the well-known NP-complete problem - the longest simple path problem.
There are two main reasons why we study parameterized NP-hard problems.
First, many application problems are naturally associated with certain parameters.
Hence we need to solve these parameterized NP-hard problems. Second, if parameters
take only small values, we can take advantage of these parameters to design very
effective algorithms.
If a parameterized NP-hard problem can be solved by an algorithm of running
time in form of f(k)nO(1), where k is the parameter, f(k) is independent of n, and
n is the input size of the problem instance, we say that this parameterized NP-hard
problem is fixed parameter tractable (FPT). If a problem is FPT and the parameter
takes only small values, the problem can be solved efficiently (it can be solved almost
in polynomial time). In this dissertation, first, we introduce several techniques that can be used to
design efficient algorithms for parameterized NP-hard problems. These techniques
include branch and bound, divide and conquer, color coding and dynamic programming,
iterative compression, iterative expansion and kernelization. Then we present
our results about how to use these techniques to solve parameterized NP-hard problems,
such as the p-path problem and the pd-feedback vertex set problem.
Especially, we designed the first algorithm of running time in form of f(k)nO(1) for
the pd-feedback vertex set problem. Thus solved an outstanding open problem,
i.e. if the pd-feedback vertex set problem is FPT. Finally, we will introduce how
to use parameterized algorithm techniques to solve the signaling pathway problem and
the motif finding problem from bioinformatics.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2009-12-7222 |
| Date | 2009 December 1900 |
| Creators | Lu, Songjian |
| Contributors | Chen, Jianer, Sze, Sing-Hoi |
| Source Sets | Texas A and M University |
| Language | English |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | application/pdf |
Page generated in 0.002 seconds