Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems

DOI10.1016/j.tcs.2011.06.018zbMath1225.68096arXiv1010.5881OpenAlexW1974182574MaRDI QIDQ719315

D. Kharzeev

Publication date: 10 October 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1010.5881

zbMATH Keywords

hypergraphkernelfixed-parameter tractablehitting setparameterized problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation ⋮ Parameterized complexity of secluded connectivity problems ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ Dual parameterization of Weighted Coloring ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ Partially Polynomial Kernels for Set Cover and Test Cover ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ Large Independent Sets in Subquartic Planar Graphs ⋮ Dual parameterization of weighted coloring

Cites Work

• Unnamed Item
• Unnamed Item
• A probabilistic approach to problems parameterized above or below tight bounds
• Vertex cover problem parameterized above and below tight bounds
• Finding odd cycle transversals.
• Total domination of graphs and small transversals of hypergraphs
• A kernelization algorithm for \(d\)-hitting set
• Parameterizing above or below guaranteed values
• On problems without polynomial kernels
• Almost 2-SAT is fixed-parameter tractable
• Covering all cliques of a graph
• Small transversals in hypergraphs
• The colour theorems of Brooks and Gallai extended
• Using nondeterminism to design efficient deterministic algorithms
• Betweenness parameterized above tight lower bound
• Parametrized complexity theory.
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterized and Exact Computation
• Computing and Combinatorics
• SOFSEM 2006: Theory and Practice of Computer Science

This page was built for publication: Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems