Efficient Exact Algorithms through Enumerating Maximal Independent
Sets and Other Techniques |
| |
Authors: | Venkatesh Raman Saket Saurabh Somnath Sikdar |
| |
Affiliation: | (1) The Institute of Mathematical Sciences, Chennai 600 113, India |
| |
Abstract: | We give substantially improved exact exponential-time algorithms for a number of NP-hard problems. These algorithms are obtained
using a variety of techniques. These techniques include: obtaining exact algorithms by enumerating maximal independent sets
in a graph, obtaining exact algorithms from parameterized algorithms and
a variant of the usual branch-and-bound technique which we call the "colored" branch-and-bound technique. These techniques
are simple in that they avoid detailed case analyses and yield algorithms that can be easily implemented. We show the power
of these techniques by applying them to several NP-hard problems and obtaining new improved upper bounds on the running time.
The specific problems that we tackle are: (1) the Odd Cycle Transversal problem in general undirected graphs, (2) the Feedback
Vertex Set problem in directed graphs of maximum degree 4, (3) Feedback Arc Set problem in tournaments, (4) the 4-Hitting
Set problem and (5) the Minimum Maximal Matching and the Edge Dominating Set problems. The algorithms that we present for
these problems are the best known and are a substantial improvement over previous best results. For example, for the Minimum
Maximal Matching we give an O*(1.4425n) algorithm improving the previous best result of O*(1.4422m) 35]. For the Odd Cycle Transversal problem, we give an O*(1.62n) algorithm which improves the previous time bound of O*(1.7724n) 3]. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|