From FPT Decision to FPT Enumeration
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915713809121280 |
|---|---|
| author | Creignou, Nadia Merkl, Timo Camillo Pichler, Reinhard Unterberger, Daniel |
| author_facet | Creignou, Nadia Merkl, Timo Camillo Pichler, Reinhard Unterberger, Daniel |
| contents | Fixed-parameter tractable (FPT) algorithms have been successfully applied to many intractable problems -- with a focus on decision and optimization problems. Their aim is to confine the exponential explosion to some parameter, while the time complexity only depends polynomially on the instance size. In contrast, intractable enumeration problems have received comparatively little attention so far. The goal of this work is to study how FPT decision algorithms could be turned into FPT enumeration algorithms. We thus inspect several fundamental approaches for designing FPT decision or optimization algorithms and we present ideas how they can be extended to FPT enumeration algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_24137 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | From FPT Decision to FPT Enumeration Creignou, Nadia Merkl, Timo Camillo Pichler, Reinhard Unterberger, Daniel Computational Complexity Fixed-parameter tractable (FPT) algorithms have been successfully applied to many intractable problems -- with a focus on decision and optimization problems. Their aim is to confine the exponential explosion to some parameter, while the time complexity only depends polynomially on the instance size. In contrast, intractable enumeration problems have received comparatively little attention so far. The goal of this work is to study how FPT decision algorithms could be turned into FPT enumeration algorithms. We thus inspect several fundamental approaches for designing FPT decision or optimization algorithms and we present ideas how they can be extended to FPT enumeration algorithms. |
| title | From FPT Decision to FPT Enumeration |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2512.24137 |