Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems

DOI10.1145/3293466MaRDI QIDQ4629983zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi, Stéphan Thomassé

Publication date 28 March 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3293466

zbMATH Keywords

implicit 3-hitting setimplicit 3-set packingkernelizationparameterized complexity

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Subquadratic kernels for implicit 3-hitting set and 3-set packing problems
• A Problem Kernelization for Graph Packing
• Kernelization Algorithms for d-Hitting Set Problems
• A Quadratic Kernel for 3-Set Packing
• Kernelization of packing problems

Cited in

(17)

• A Quadratic Kernel for 3-Set Packing
• Subquadratic kernels for implicit 3-hitting set and 3-set packing problems
• scientific article; zbMATH DE number 7559376 (Why is no real title available?)
• A tight approximation algorithm for the cluster vertex deletion problem
• A tight approximation algorithm for the cluster vertex deletion problem
• s-club cluster vertex deletion on interval and well-partitioned chordal graphs
• A polynomial kernel for 3-leaf power deletion
• A parameterized algorithm for subset feedback vertex set in tournaments
• Packing arc-disjoint cycles in oriented graphs
• \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
• Smaller kernels for 3-leaf power modifications problems
• Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
• Data reduction for directed feedback vertex set on graphs without long induced cycles. Three rules to rule them all
• Forgetfulness can make you faster: an O^*(8.097ᵏ)-time algorithm for weighted 3-set k-packing
• Breaking the barrier 2ᵏ for subset feedback vertex set in chordal graphs
• Subset feedback vertex set in tournaments as fast as without the subset
• A polynomial kernel for deletion to the scattered class of cliques and trees

This page was built for publication: Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems

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