Many problems of practical significance are known to be NP-hard, and hence, are unlikely
to be solved by polynomial-time algorithms. There are several ways to cope with
the NP-hardness of a certain problem. The most popular approaches include heuristic
algorithms, approximation algorithms, and randomized algorithms. Recently, parameterized
computation and complexity have been receiving a lot of attention. By
taking advantage of small or moderate parameter values, parameterized algorithms
provide new venues for practically solving problems that are theoretically intractable.
In this dissertation, we design efficient parameterized algorithms for several wellknown
NP-hard problems and prove strong lower bounds for some others. In doing
so, we place emphasis on the development of new techniques that take advantage of
the structural properties of the problems.
We present a simple parameterized algorithm for Vertex Cover that uses polynomial
space and runs in time O(1.2738k + kn). It improves both the previous
O(1.286k + kn)-time polynomial-space algorithm by Chen, Kanj, and Jia, and the
very recent O(1.2745kk4 + kn)-time exponential-space algorithm, by Chandran and
Grandoni. This algorithm stands out for both its performance and its simplicity. Essential
to the design of this algorithm are several new techniques that use structural
information of the underlying graph to bound the search space.
For Vertex Cover on graphs with degree bounded by three, we present a still better algorithm that runs in time O(1.194k + kn), based on an âÂÂalmost-globalâÂÂ
analysis of the search tree.
We also show that an important structural property of the underlying graphs âÂÂ
the graph genus â largely dictates the computational complexity of some important
graph problems including Vertex Cover, Independent Set and Dominating Set.
We present a set of new techniques that allows us to prove almost tight computational
lower bounds for some NP-hard problems, such as Clique, Dominating Set,
Hitting Set, Set Cover, and Independent Set. The techniques are further extended
to derive computational lower bounds on polynomial time approximation schemes for
certain NP-hard problems. Our results illustrate a new approach to proving strong
computational lower bounds for some NP-hard problems under reasonable conditions.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/4322 |
| Date | 30 October 2006 |
| Creators | Xia, Ge |
| Contributors | Chen, Jianer |
| Publisher | Texas A&M University |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | 1126964 bytes, electronic, application/pdf, born digital |
Page generated in 0.0016 seconds