Preprocessing to reduce the search space: antler structures for feedback vertex set

DOI10.1007/978-3-030-86838-3_1OpenAlexW3204469131MaRDI QIDQ2672419

Huib Donkers, Bart M. P. Jansen

Publication date: 8 June 2022

Full work available at URL: https://arxiv.org/abs/2106.11675

zbMATH Keywords

graph decompositionfeedback vertex setkernelizationpreprocessing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Kernelization for feedback vertex set via elimination distance to a forest

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Infeasibility of instance compression and succinct PCPs for NP
• Improved upper bounds for vertex cover
• Center-based clustering under perturbation stability
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• A cubic kernel for feedback vertex set and loop cutset
• A completeness theory for polynomial (Turing) kernelization
• Crown structures for vertex cover kernelization
• Parametrized complexity theory.
• A 4 k ² kernel for feedback vertex set
• (Meta) Kernelization
• Presolve Reductions in Mixed Integer Programming
• New Limits to Classical and Quantum Instance Compression
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• Reducibility Among Combinatorial Problems
• Vertex packings: Structural properties and algorithms
• Color-coding
• Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
• Kernelization
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Faster Parameterized Algorithms Using Linear Programming
• Kernelization Lower Bounds by Cross-Composition
• Representative Sets and Irrelevant Vertices
• Scalable Kernelization for Maximum Independent Sets
• Mixed Integer Programming: Analyzing 12 Years of Progress
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science
• The Problem of Simplifying Truth Functions
• The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)
• Graph-Theoretic Concepts in Computer Science