Search-space reduction via essential vertices

DOI10.1137/23M1589347zbMATH Open1547.05218MaRDI QIDQ6606914FDOQ6606914

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

Publication date: 17 September 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Recommendations

• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Preprocessing for treewidth: a combinatorial analysis through kernelization
• A cubic kernel for feedback vertex set and loop cutset
• Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
• Lossy kernelization

zbMATH Keywords

fixed-parameter tractabilityessential verticescovering versus packing

Mathematics Subject Classification ID

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

Cites Work

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

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 Q6606914)