Lu, Songjian (2009-12). Randomized and Deterministic Parameterized Algorithms and Their Applications in Bioinformatics. Doctoral Dissertation. Thesis uri icon

abstract

  • 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.
  • 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.

publication date

  • December 2009