Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jansen, Bart M. P., Verhaegh, Ruben F. A.
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

Preprocessing to Reduce the Search Space for Odd Cycle Transversal
by: Jansen, Bart M. P., et al.
Published: (2024)

Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set
by: Donkers, Huib, et al.
Published: (2021)

Faster Parameterized Vertex Multicut
by: Chu, Huairui, et al.
Published: (2026)

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange
by: Jansen, Bart M. P., et al.
Published: (2025)

A $O^*((2 + ε)^k)$ Time Algorithm for Cograph Deletion Using Unavoidable Subgraphs in Large Prime Graphs
by: Lafond, Manuel, et al.
Published: (2026)

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

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

Mimicking Networks for Constrained Multicuts in Hypergraphs
by: Cho, Kyungjin, et al.
Published: (2024)

Node-Weighted Multicut in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2026)

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

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)

Cluster Editing on Cographs and Related Classes
by: Lafond, Manuel, et al.
Published: (2024)

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

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
by: Esmer, Barış Can, et al.
Published: (2024)

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

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

Enumeration kernels for Vertex Cover and Feedback Vertex Set
by: Bougeret, Marin, et al.
Published: (2025)

Parameterized Vertex Integrity Revisited
by: Hanaka, Tesshu, et al.
Published: (2024)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)

Parameterized Capacitated Vertex Cover Revisited
by: Lampis, Michael, et al.
Published: (2026)

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
by: Hatzel, Meike, et al.
Published: (2022)

Space Complexity of Vertex Connectivity Oracles
by: Pettie, Seth, et al.
Published: (2022)

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

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

Revisiting a Successful Reduction Rule for Dominating Set
by: Geis, Lukas, et al.
Published: (2025)

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

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
by: Akhtar, Sheikh Shakil, et al.
Published: (2025)

The SpaceSaving$\pm$ Family of Algorithms for Data Streams with Bounded Deletions
by: Zhao, Fuheng, et al.
Published: (2023)

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

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

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

Structural Parameterizations of Vertex Integrity
by: Gima, Tatsuya, et al.
Published: (2023)

Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
by: Komusiewicz, Christian, et al.
Published: (2026)

The Trie Measure, Revisited
by: Alanko, Jarno N., et al.
Published: (2025)

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

Faster Deterministic Streaming Vertex Coloring
by: Chechik, Shiri, et al.
Published: (2026)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Dynamic $(Δ+ 1)$ Vertex Coloring
by: Benson-Tilsen, Noam
Published: (2026)