Parameterized top- K algorithms

We study algorithmic techniques that produce the best K solutions to an instance of a parameterized NP-hard problem whose solutions are associated with a scoring function. Our parameterized top- K algorithms proceed in two stages. The first stage is a structure algorithm that on a problem instance constructs a structure of feasible size, and the second stage is an enumerating algorithm that produces the K best solutions to the instance based on the structure. We show that many algorithm-design techniques for parameterized algorithms, such as branch-and-search, color coding, and bounded treewidth, can be adopted for designing efficient structure algorithms. We then develop new techniques that support efficient enumerating algorithms. In particular, we show that for a large class of well-known NP optimization problems, there are parameterized top- K algorithms that produce the best K solutions for the problems in feasible amount of average time per solution when the parameter value is small. Finally, we investigate the relation between fixed-parameter tractability and parameterized top- K algorithms.

Authors

• Jianer Chen
• Iyad A. Kanj
• Jie Meng
• Ge Xia
• Fenghui Zhang

Keywords

• Parameterized algorithms
• Enumeration algorithms