Copertina

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Chu, Huairui, Lin, Bingkai
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
di: Herrmann, Anton, et al.
Pubblicazione: (2025)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
di: Dey, Palash, et al.
Pubblicazione: (2024)

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

Parameterized Capacitated Vertex Cover Revisited
di: Lampis, Michael, et al.
Pubblicazione: (2026)

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

Dominating Set Knapsack: Profit Optimization on Dominating Sets
di: Singh, Sipra
Pubblicazione: (2025)

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

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
di: Tale, Prafullkumar
Pubblicazione: (2025)

Parameterized Max Min Feedback Vertex Set
di: Lampis, Michael, et al.
Pubblicazione: (2023)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
di: Foucaud, Florent, et al.
Pubblicazione: (2024)

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

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
di: Bilò, Davide, et al.
Pubblicazione: (2025)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)

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

Exact Algorithms for Distance to Unique Vertex Cover
di: Fioravantes, Foivos, et al.
Pubblicazione: (2025)

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)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
di: Chakraborty, Dipayan, et al.
Pubblicazione: (2024)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
di: Gadekar, Ameet, et al.
Pubblicazione: (2025)

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

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

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
di: Clinch, Katie, et al.
Pubblicazione: (2025)

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

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

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
di: Saito, Rin, et al.
Pubblicazione: (2025)

Tight Inapproximability of Target Set Reconfiguration
di: Ohsaka, Naoto
Pubblicazione: (2024)

Rounding Large Independent Sets on Expanders
di: Bafna, Mitali, et al.
Pubblicazione: (2024)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

Deterministic Independent Sets in the Semi-Streaming Model
di: Ye, Daniel
Pubblicazione: (2025)

Parameterized Vertex Integrity Revisited
di: Hanaka, Tesshu, et al.
Pubblicazione: (2024)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
di: Bilò, Davide, et al.
Pubblicazione: (2024)

Bandwidth Parameterized by Cluster Vertex Deletion Number
di: Gima, Tatsuya, et al.
Pubblicazione: (2023)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
di: Tate, Elise, et al.
Pubblicazione: (2025)

Pushing the frontiers of subexponential FPT time for Feedback Vertex Set
di: Berthe, Gaétan, et al.
Pubblicazione: (2025)

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

On the Complexity of 2-club Cluster Editing with Vertex Splitting
di: Abu-Khzam, Faisal N., et al.
Pubblicazione: (2024)

Distance Vector Domination
di: Cordasco, Gennaro, et al.
Pubblicazione: (2024)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
di: Lehner, Lisa, et al.
Pubblicazione: (2025)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
di: Firbas, Alexander, et al.
Pubblicazione: (2024)

FPT Approximation for Capacitated Sum of Radii
di: Jaiswal, Ragesh, et al.
Pubblicazione: (2024)