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

hitting setparameterized complexityquery complexity

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

(7)

• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• scientific article; zbMATH DE number 7250167 (Why is no real title available?)
• Almost optimal query algorithm for hitting set using a subset query
• Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
• Faster counting and sampling algorithms using colorful decision oracle
• Non-adaptive edge counting and sampling via bipartite independent set queries
• On triangle estimation using tripartite independent set queries

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)