Copertina

The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Schestag, Jannik, Zeh, Norbert
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
di: Holtgrefe, Niels, et al.
Pubblicazione: (2026)

Maximizing Phylogenetic Diversity under Time Pressure: Planning with Extinctions Ahead
di: Jones, Mark, et al.
Pubblicazione: (2024)

Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
di: Komusiewicz, Christian, et al.
Pubblicazione: (2024)

Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth
di: Holtgrefe, Niels, et al.
Pubblicazione: (2026)

Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond
di: van Iersel, Leo, et al.
Pubblicazione: (2024)

From FPT Decision to FPT Enumeration
di: Creignou, Nadia, et al.
Pubblicazione: (2025)

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

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

Generalized Graph Packing Problems Parameterized by Treewidth
di: Esmer, Barış Can, et al.
Pubblicazione: (2025)

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

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
di: Esmer, Barış Can, et al.
Pubblicazione: (2024)

Tree Containment Parameterized by Scanwidth
di: van Iersel, Leo, et al.
Pubblicazione: (2026)

Quantifier Elimination Meets Treewidth
di: Wu, Hao, et al.
Pubblicazione: (2026)

Minimum Stable Cut and Treewidth
di: Lampis, Michael
Pubblicazione: (2021)

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

Can You Link Up With Treewidth?
di: Curticapean, Radu, et al.
Pubblicazione: (2024)

Residue Domination in Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2024)

k-SUM Hardness Implies Treewidth-SETH
di: Lampis, Michael
Pubblicazione: (2025)

A Wild Sheep Chase Through an Orchard
di: Dempsey, Jordan, et al.
Pubblicazione: (2024)

Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
di: Ganian, Robert, et al.
Pubblicazione: (2026)

Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
di: van Iersel, Leo, et al.
Pubblicazione: (2026)

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

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
di: Foucaud, Florent, et al.
Pubblicazione: (2023)

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

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2025)

Core Stability in Additively Separable Hedonic Games of Low Treewidth
di: Hanaka, Tesshu, et al.
Pubblicazione: (2024)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
di: Bhaskar, Umang, et al.
Pubblicazione: (2025)

Hardness Results on Characteristics for Elastic-Degenerated Strings
di: Köppl, Dominik, et al.
Pubblicazione: (2024)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
di: Focke, Jacob, et al.
Pubblicazione: (2022)

Finding Minimum Matching Cuts in $H$-free Graphs
di: Lucke, Felicia, et al.
Pubblicazione: (2025)

On Computability of Computable Problems
di: Khaliq, Asad
Pubblicazione: (2023)

The Stochastic Arrival Problem
di: Webster, Thomas
Pubblicazione: (2022)

Continuous Defensive Domination Problems
di: Grüne, Christoph, et al.
Pubblicazione: (2026)

The Greedy Coin Change Problem
di: Gupta, Shreya, et al.
Pubblicazione: (2024)

On the Hardness of the Drone Delivery Problem
di: Bartlmae, Simon, et al.
Pubblicazione: (2025)

Parameterized Maximum Node-Disjoint Paths
di: Lampis, Michael, et al.
Pubblicazione: (2024)

Parameterized Critical Node Cut Revisited
di: Knop, Dušan, et al.
Pubblicazione: (2025)

Parameterized Complexity of the Star Decomposition Problem
di: Hajebi, Sahab, et al.
Pubblicazione: (2024)

On the Complexity of Problems on Tree-structured Graphs
di: Bodlaender, Hans L., et al.
Pubblicazione: (2022)

Reductions Between Code Equivalence Problems
di: Cheraghchi, Mahdi, et al.
Pubblicazione: (2025)