Algorithms · Reductions, NP-completeness, and approximation
Consider SET COVER parameterized by the universe size p=|U|, while the number m of…
Problem
Consider SET COVER parameterized by the universe size \(p=|U|\), while the number \(m\) of available sets may be much larger. Encode subsets of \(U\) as \(p\)-bit masks and design a dynamic program that computes, for every mask, the minimum number of available sets whose union covers that mask. Prove the recurrence by considering the last set added, show how to reconstruct an optimum cover, and derive \(O(m2^p)\) time and \(O(2^p)\) space bounds. Use the result to decide whether a cover of size at most \(k\) exists, and prove that this is fixed-parameter tractable in \(p\) even though SET COVER is NP-complete when \(p\) is unrestricted.
Hint
Let the subproblem mask represent elements still required rather than the exact union already formed.
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Algorithms sample problem: Try the free sample problem.
More Algorithms practice problems
- Let all logarithms have base 2, and let all functions have domain the positive integersCorrectness proofs and asymptotic complexity
- There are n jobs in fixed order with positive integer sizes s_1,…,s_n, and d≥1…Correctness proofs and asymptotic complexity
- Two disjoint color classes contain r≥1 red and b≥1 blue planar pointsDivide-and-conquer algorithms
- Using only comparisons, return both minimum and maximum among n≥1 distinct keysDivide-and-conquer algorithms
- Consider the invalid coding rule that repeatedly combines the two partial trees of…Greedy algorithms and exchange proofs
- The n vertices of a cycle are numbered 1,…,n, and vertex i has an integer weightGreedy algorithms and exchange proofs
- Given an undirected graph with up to five million vertices, produce exactly the…Dynamic programming and state design
- Prim’s algorithm starts at an arbitrary root and repeatedly adds a minimum-weight edge…Dynamic programming and state design
- Let T[0..n-1] be a text and P[0..m-1] a pattern over the same alphabet, where 1≤ m≤ nGraph optimization and traversal algorithms