Search-space reduction via essential vertices

DOI10.4230/LIPICS.ESA.2022.30MaRDI QIDQ6969655zbMATH OpenFDO

Authors Benjamin Merlin Bumpus, Bart M. P. Jansen, Jari J. H. de Kroon

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.30

zbMATH Keywords

covering versus packingessential verticesfixed-parameter tractability

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cites work

• (Meta) Kernelization
• \textsc{Planar} \(\mathcal{F}\)-\textsc{deletion}: approximation, kernelization and optimal FPT algorithms
• A cubic kernel for feedback vertex set and loop cutset
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Algorithmic graph theory and perfect graphs
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Chordal editing is fixed-parameter tractable
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
• Experiments on data reduction for optimal domination in networks
• Faster parameterized algorithms using linear programming
• Finding odd cycle transversals.
• Graph minors. XIII: The disjoint paths problem
• Improved upper bounds for vertex cover
• Kernelization -- preprocessing with a guarantee
• Kernelization. Theory of parameterized preprocessing
• Lower bounds for kernelization
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• New limits to classical and quantum instance compression
• NP is as easy as detecting unique solutions
• On Independent Circuits Contained in a Graph
• On the odd-minor variant of Hadwiger's conjecture
• On the Parameterized Complexity of Approximating Dominating Set
• On the power of unique 2-prover 1-round games
• Packing non-zero \(A\)-paths in group-labelled graphs
• Parameterized algorithms
• Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
• Parameterized complexity of vertex deletion into perfect graph classes
• Perturbation Resilience
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Recent developments in kernelization: a survey
• Representative sets and irrelevant vertices: new tools for kernelization
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• Vertex deletion parameterized by elimination distance and even less
• Vertex packings: Structural properties and algorithms
• Wheel-Free Deletion Is W[2]-Hard

Cited in

(3)

• Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
• Preprocessing to reduce the search space for odd cycle transversal
• Safe sequences via dominators in DAGs for path-covering problems

This page was built for publication: Search-space reduction via essential vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6969655)