Cover Image

From FPT Decision to FPT Enumeration

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Creignou, Nadia, Merkl, Timo Camillo, Pichler, Reinhard, Unterberger, Daniel
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Consistent Query Answering over SHACL Constraints
by: Ahmetaj, Shqiponja, et al.
Published: (2024)

Diversity of Answers to Conjunctive Queries
by: Merkl, Timo Camillo, et al.
Published: (2023)

FPT Parameterisations of Fractional and Generalised Hypertree Width
by: Lanzinger, Matthias, et al.
Published: (2025)

The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth
by: Schestag, Jannik, et al.
Published: (2026)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
by: Gaikwad, Ajinkya, et al.
Published: (2025)

$O(n +f(k))$: Truly Linear FPT
by: Bumpus, Benjamin Merlin, et al.
Published: (2026)

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
by: Yi, Yongming
Published: (2026)

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
by: Chu, Huairui, et al.
Published: (2023)

The Space-Time Complexity of Sum-Product Queries
by: Deeds, Kyle, et al.
Published: (2025)

Query Answering under Volume-Based Diversity Functions
by: Arenas, Marcelo, et al.
Published: (2025)

Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue
by: Arenas, Marcelo, et al.
Published: (2024)

Local Enumeration and Majority Lower Bounds
by: Gurumukhani, Mohit, et al.
Published: (2024)

From Amortized to Worst Case Delay in Enumeration Algorithms
by: Capelli, Florent, et al.
Published: (2021)

Enumerating Minimal Defensive Alliances
by: Feng, Zhidan, et al.
Published: (2023)

Enumeration With Nice Roman Domination Properties
by: Mann, Kevin
Published: (2025)

Local Enumeration: The Not-All-Equal Case
by: Gurumukhani, Mohit, et al.
Published: (2025)

The Complexity of Maximal Common Subsequence Enumeration
by: Buzzega, Giovanni, et al.
Published: (2025)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
by: Kurita, Kazuhiro, et al.
Published: (2025)

FPT-Approximability of Stable Matching Problems
by: Chen, Jiehua, et al.
Published: (2025)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2023)

Emit As You Go: Enumerating Edges of a Spanning Tree
by: Casel, Katrin, et al.
Published: (2025)

Enumerating models of DNF faster: breaking the dependency on the formula size
by: Capelli, Florent, et al.
Published: (2018)

Hazard-free Decision Trees
by: Benson, Deepu, et al.
Published: (2025)

Complexity of Finding and Enumerating Interconnection Trees
by: Demange, Noé, et al.
Published: (2026)

On complexity of restricted fragments of Decision DNNF
by: Calí, Andrea, et al.
Published: (2025)

Explaining the Ubiquity of Phase Transitions in Decision Problems
by: Jackson, Andrew
Published: (2025)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
by: Fortnow, Lance
Published: (2025)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
by: Jackson, Andrew
Published: (2025)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
by: Alhamdan, Yousef M.
Published: (2025)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2024)

Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width
by: Razgon, Igor
Published: (2025)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

Polynomial-time completion of phylogenetic tree sets
by: Koshkarov, Aleksandr, et al.
Published: (2026)

Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins
by: Deeds, Kyle, et al.
Published: (2025)

Enumeration and updates for conjunctive linear algebra queries through expressibility
by: Muñoz, Thomas, et al.
Published: (2023)

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
by: Junchi, Ma, et al.
Published: (2024)

Enumeration of minimal transversals of hypergraphs of bounded VC-dimension
by: Mary, Arnaud
Published: (2024)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)

ManiFPT: Defining and Analyzing Fingerprints of Generative Models
by: Song, Hae Jin, et al.
Published: (2024)