Cover Image

Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Houari-Durand, Séhane Bel, Eiben, Eduard, Wahlström, Magnus
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

FPT algorithms over linear delta-matroids with applications
by: Eiben, Eduard, et al.
Published: (2025)

Determinantal Sieving
by: Eiben, Eduard, et al.
Published: (2023)

Representative set statements for delta-matroids and the Mader delta-matroid
by: Wahlström, Magnus
Published: (2023)

Kernelization for list $H$-coloring for graphs with small vertex cover
by: Piecyk, Marta, et al.
Published: (2025)

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
by: Eiben, Eduard, et al.
Published: (2024)

Parameterized Complexity of MinCSP over the Point Algebra
by: Osipov, George, et al.
Published: (2023)

Minimizing Reachability Times on Temporal Graphs via Shifting Labels
by: Deligkas, Argyrios, et al.
Published: (2021)

Quadratic Kernel for Cliques or Trees Vertex Deletion
by: Kumabe, Soh
Published: (2025)

Maximizing Reachability via Shifting of Temporal Paths
by: Deligkas, Argyrios, et al.
Published: (2026)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
by: Gaikwad, Ajinkya, et al.
Published: (2026)

Parameterized Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2025)

Optimal FPT-Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2026)

A Randomized Rounding Approach for DAG Edge Deletion
by: Kalantarzadeh, Sina, et al.
Published: (2025)

Faster algorithms on linear delta-matroids
by: Koana, Tomohiro, et al.
Published: (2024)

A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees
by: Jacob, Ashwin, et al.
Published: (2024)

Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
by: Goldmann, Lito, et al.
Published: (2023)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
by: Kim, Eun Jung, et al.
Published: (2022)

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

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
by: Jonsson, Peter, et al.
Published: (2025)

Edge-Minimum Walk of Modular Length in Polynomial Time
by: Amarilli, Antoine, et al.
Published: (2024)

A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees
by: Jacob, Ashwin, et al.
Published: (2026)

Individual Rationality in Topological Distance Games is Surprisingly Hard
by: Deligkas, Argyrios, et al.
Published: (2024)

Pathfinding in Self-Deleting Graphs
by: Dvořák, Michal, et al.
Published: (2025)

Streaming Maximal Matching with Bounded Deletions
by: Khanna, Sanjeev, et al.
Published: (2025)

Adversarial Robustness on Insertion-Deletion Streams
by: Gribelyuk, Elena, et al.
Published: (2026)

Cluster Vertex Deletion on Chordal Graphs
by: Cao, Yixin, et al.
Published: (2026)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
by: Haeupler, Bernhard, et al.
Published: (2026)

Polynomial Kernels for Spanning Tree with Diversity Requirements
by: Golovach, Petr A., et al.
Published: (2026)

Algorithms and Complexity of Hedge Cluster Deletion Problems
by: Konstantinidis, Athanasios L., et al.
Published: (2025)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
by: Gaikwad, Ajinkya
Published: (2025)

Coordinated Motion Planning is FPT on Discretized Simple Polygons
by: Deligkas, Argyrios, et al.
Published: (2026)

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

On the Parameterized Complexity of Eulerian Strong Component Arc Deletion
by: Blažej, Václav, et al.
Published: (2024)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
by: Pham, Ninh, et al.
Published: (2025)

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

Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
by: Chandrasekaran, Karthekeyan, et al.
Published: (2023)

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions
by: Berg, Magnus
Published: (2024)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
by: Jiang, Tianle, et al.
Published: (2024)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
by: Deligkas, Argyrios, et al.
Published: (2025)

On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2023)