Parameterized query complexity of hitting set using stability of sunflowers

DOI10.4230/LIPICS.ISAAC.2018.25MaRDI QIDQ5091015zbMATH OpenFDO

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

zbMATH Keywords

query complexityparameterized complexityhitting set

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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

Cites work

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

Cited in

(4)

• Almost optimal query algorithm for hitting set using a subset query
• On triangle estimation using tripartite independent set queries
• scientific article; zbMATH DE number 7250167 (Why is no real title available?)
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle

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)