Parameterized query complexity of hitting set using stability of sunflowers

DOI10.4230/LIPICS.ISAAC.2018.25MaRDI QIDQ5091015FDOQ5091015

Authors: Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh 

Publication date: 21 July 2022

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

Recommendations

• Towards optimal and expressive kernelization for \(d\)-hitting set
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Computing Hitting Set Kernels By AC^0-Circuits
• Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
• Hitting Set for hypergraphs of low VC-dimension

zbMATH Keywords

query complexityparameterized complexityhitting set

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Parameterized algorithms
• Intersection Theorems for Systems of Sets
• Approximating average parameters of graphs
• Edge estimation with independent set oracles
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
• Introduction to Property Testing
• Computing exact minimum cuts without knowing the graph
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Set cover in sub-linear time
• Parameterized testability

Cited In (4)

• On triangle estimation using tripartite independent set queries
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Title not available (Why is that?)
• Almost optimal query algorithm for hitting set using a subset query

This page was built for publication: Parameterized query complexity of hitting set using stability of sunflowers

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