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

DOI10.1016/j.jcss.2024.103532MaRDI QIDQ6564613

Huib Donkers, Bart M. P. Jansen

Publication date: 1 July 2024

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

graph decompositionfeedback vertex setkernelizationpreprocessing

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• 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
• Dynamic programming algorithms for the zero-one knapsack problem
• Improved analysis of highest-degree branching for feedback vertex set
• A completeness theory for polynomial (Turing) kernelization
• Recent techniques and results on the Erdős-Pósa property
• Crown structures for vertex cover kernelization
• Parametrized complexity theory.
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• 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
• 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
• Reducibility among Combinatorial Problems
• Representative Sets and Irrelevant Vertices
• 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

This page was built for publication: Preprocessing to reduce the search space: antler structures for feedback vertex set