Partially Polynomial Kernels for Set Cover and Test Cover

DOI10.1137/15M1039584zbMath1344.68270MaRDI QIDQ5741085

Saket Saurabh, M. S. Ramanujan, Mathew C. Francis, Manu Basavaraju

Publication date: 22 July 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

fixed parameter tractabilityset covertest coverpartially polynomial kernels

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Extremal set theory (05D05)

Related Items (8)

System of unbiased representatives for a collection of bicolorings ⋮ Dual parameterization of Weighted Coloring ⋮ Induced-bisecting families of bicolorings for hypergraphs ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. ⋮ Dual parameterization of weighted coloring

Cites Work

• Parameterizations of test cover with bounded test sizes
• Fixed-parameter tractability of satisfying beyond the number of variables
• Infeasibility of instance compression and succinct PCPs for NP
• Average parameterization and partial kernelization for computing medians
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• On two techniques of combining branching and treewidth
• On problems without polynomial kernels
• (Non-)existence of polynomial kernels for the test cover problem
• Parametrized complexity theory.
• Induced subsets
• Parameterized Study of the Test Cover Problem
• Partially Polynomial Kernels for Set Cover and Test Cover

This page was built for publication: Partially Polynomial Kernels for Set Cover and Test Cover