Parameterized Algorithms and Computation Theory
Parameterized computation is a framework to cope with the intractability of computational problems. Different from the conventional approximation and heuristic approaches, parameterized computation seeks exact solutions for parameterized problems with the worst case time complexity f(k)nc, for some significant parameter k in the input as well as the input size n. Such algorithms are not always possible for NP-hard problems even f(k) is allowed exponential. For instance, determining the existence of a size k vertex cover in a graph of n vertices can be done in time O(2kn2), while for determining the existence of a size k dominating set in a graph, the known best algorithms need to run in time nO(k). This phenomenon has lead to the development of a structural classification of parameterized problems into class FPT for fixed-parameter tractable problems, and into a spectrum of classes W[t], t=1, 2, ..., for those possibly not admitting algorithms of time f(k)nc.
Research topics in parameterized computation may roughly be categorize as:
- Developing efficient parameterized algorithms by seeking novel algorithmic techiques to reduce the factor f(k) or the polynomial degree c in the time complexity,
- Investigating parameterized intractability and structure properties of parameterized intractable problems, and
- Establish relationships between the parameterized computation and the conventional computation theory.
My previous research in parameterized computation addressed a number of issues in all the above three categories. In particular, I was involved in the following research
projects:
- A standard parameterization of optimization problems,
making it possible to
investigate the relationship between parameterized algorithms and approximation algorithms. For example, the widely used notion of EPTAS (efficient polynomial-time approximation scheme) arose out of this work;
- The notion of limited nondeterminism to characterize parameterized intractable classes that were too difficult to comprehend within the conventional complexity theory framework;
- The characterization of parameterized algorithms as advice-computation, the earliest version of the kernelization method widely used for developing parameterized algorithms today;
- The surprising relationship between the existence of subexponential parameterized algorithms and the collapse of the W-hierarchy via a "engineering" parameterizationof optmization problems, making it possible to investigate the time lower bound of parameterized algorithms and that of approximation algorithms, and
-
Upper and lower bounded for time complexity of EPTAS on a large class optimization problems with planar structures [6].
My current research projects in this area focuses on establishing a larger vision on the parameterization computation theory and deeper insight into the efficiency issue of parameterized algorithms. I am currently investigating the following
issues:
- A new framework of fixed-parameter approximation (FPA) to
reveal the intrinsic relationship between parameterized tractability and approximability and to improve approximability of optimization problems,
- Systematic techniques to derive efficient parameterized algorithms with
Courcelle's Theorem by
parameterized reductions to monadic second order logic, and
- New techniques to improve the constant factor in the linear time complexity O(ctn) for MSO-expressible problems on graphs of bounded tree width t.