On the effective enumerability of NP problems Conference Paper uri icon

abstract

  • In the field of computational optimization, it is often the case that we are given an instance of an NP problem and asked to enumerate the first few "best" solutions to the instance. Motivated by this, we propose in this paper a new framework to measure the effective enumerability of NP optimization problems. More specifically, given an instance of an NP problem, we consider the parameterized problem of enumerating a given number of best solutions to the instance, and study its average complexity in terms of the number of solutions. Our framework is different from the previously-proposed ones. For example, although it is known that counting the number of k- paths in a graph is #W[1]-complete, we present a fixed-parameter enumeration algorithm for the problem. We show that most algorithmic techniques for fixed-parameter tractable problems, such as search trees, color coding, and bounded treewidth, can be used for parameterized enumerations. In addition, we design elegant and new enumeration techniques and show how to generate small-size structures and enumerate solutions efficiently. Springer-Verlag Berlin Heidelberg 2006.

name of conference

  • Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zrich, Switzerland, September 13-15, 2006, Proceedings
  • Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings

published proceedings

  • PARAMETERIZED AND EXACT COMPUTATION, PROCEEDINGS

author list (cited authors)

  • Chen, J., Kanj, I. A., Meng, J., Xia, G. e., & Zhang, F.

complete list of authors

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

publication date

  • January 2006