Copertina

Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Sharma, Roohani, Włodarczyk, Michał
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Losing Treewidth In The Presence Of Weights
di: Włodarczyk, Michał
Pubblicazione: (2024)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
di: Wlodarczyk, Michal
Pubblicazione: (2023)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
di: Greilhuber, Jakob, et al.
Pubblicazione: (2026)

A Refined Kernel for $d$-Hitting Set
di: Liu, Yuxi, et al.
Pubblicazione: (2025)

Enumeration of Minimal Hitting Sets Parameterized by Treewidth
di: Kenig, Batya, et al.
Pubblicazione: (2024)

Hitting Meets Packing: How Hard Can it Be?
di: Focke, Jacob, et al.
Pubblicazione: (2024)

Designing Compact ILPs via Fast Witness Verification
di: Włodarczyk, Michał
Pubblicazione: (2025)

Going Beyond Surfaces in Diameter Approximation
di: Włodarczyk, Michał
Pubblicazione: (2025)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
di: Włodarczyk, Michał
Pubblicazione: (2024)

Does Subset Sum Admit Short Proofs?
di: Włodarczyk, Michał
Pubblicazione: (2024)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
di: Pilipczuk, Michał, et al.
Pubblicazione: (2025)

Linear Kernels for $l$-Exact Component Order Connectivity
di: Liu, Yuxi, et al.
Pubblicazione: (2026)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
di: Dong, Sally, et al.
Pubblicazione: (2023)

Optimal Padded Decomposition For Bounded Treewidth Graphs
di: Filtser, Arnold, et al.
Pubblicazione: (2024)

Boundaried Kernelization
di: Antipov, Leonid, et al.
Pubblicazione: (2025)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
di: Chang, Hsien-Chih, et al.
Pubblicazione: (2024)

Dynamic Detours
di: Dadush, Daniel, et al.
Pubblicazione: (2026)

Kernelization for Orthogonality Dimension
di: Haviv, Ishay, et al.
Pubblicazione: (2024)

Coresets for Kernel Clustering
di: Jiang, Shaofeng H. -C., et al.
Pubblicazione: (2021)

Dynamic Meta-Kernelization
di: Bertram, Christian, et al.
Pubblicazione: (2025)

Kernelization for $H$-Coloring
di: Berkman, Yael, et al.
Pubblicazione: (2025)

Optimized 2-Approximation of Treewidth
di: Belbasi, Mahdi, et al.
Pubblicazione: (2024)

Dynamic Treewidth in Logarithmic Time
di: Korhonen, Tuukka
Pubblicazione: (2025)

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

Space-Efficient Graph Kernelizations
di: Kammer, Frank, et al.
Pubblicazione: (2020)

Dynamic Kernel Graph Sparsifiers
di: Cao, Yang, et al.
Pubblicazione: (2022)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
di: Marx, Dániel, et al.
Pubblicazione: (2026)

Boundaried Kernelization via Representative Sets
di: Antipov, Leonid, et al.
Pubblicazione: (2025)

Spanning and Metric Tree Covers Parameterized by Treewidth
di: Elkin, Michael, et al.
Pubblicazione: (2025)

Testing Intersectingness of Uniform Families
di: Haviv, Ishay, et al.
Pubblicazione: (2024)

Expander Decomposition for Non-Uniform Vertex Measures
di: Agassy, Daniel, et al.
Pubblicazione: (2025)

Quadratic Kernel for Cliques or Trees Vertex Deletion
di: Kumabe, Soh
Pubblicazione: (2025)

Efficient Kernelization Algorithm for Bipartite Graph Matching
di: Wu, Guang, et al.
Pubblicazione: (2024)

Visualizing Treewidth
di: Chiu, Alvin, et al.
Pubblicazione: (2025)

Distributed Treewidth Computation and Courcelle's Theorem in the CONGEST Model
di: Jauregui, Benjamin, et al.
Pubblicazione: (2018)

E-Graphs as Circuits, and Optimal Extraction via Treewidth
di: Sun, Glenn, et al.
Pubblicazione: (2024)

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
di: Garg, Sachin, et al.
Pubblicazione: (2025)

The Probability to Hit Every Bin with a Linear Number of Balls
di: Walzer, Stefan
Pubblicazione: (2024)

Revisiting Forest Proximities via Sparse Leaf-Incidence Kernels
di: Aumon, Adrien, et al.
Pubblicazione: (2026)

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection
di: Huang, Chien-Chung, et al.
Pubblicazione: (2026)