Search-space reduction via essential vertices

DOI10.1137/23M1589347MaRDI QIDQ6606914zbMATH OpenFDO

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)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1137/23M1589347

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) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

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

Cites work

• (Meta) kernelization
• 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
• Approximation and kernelization for chordal vertex deletion
• 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.
• Fundamentals of parameterized complexity
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• Improved upper bounds for vertex cover
• Kernelization -- preprocessing with a guarantee
• Kernelization. Theory of parameterized preprocessing
• Losing Treewidth by Separating Subsets
• Lower bounds for kernelization
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• New hardness results for routing on disjoint paths
• 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 Computational Complexity of Combinatorial Problems
• 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
• Presolve Reductions in Mixed Integer Programming
• 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 even-path problem for graphs and digraphs
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Vertex deletion parameterized by elimination distance and even less
• Vertex packings: Structural properties and algorithms
• Wheel-Free Deletion Is W[2]-Hard

Cited in

(1)

• Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion

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)