Skip to main content

Practice before assessment

Attempt before reading the key.

  1. For a three-leaf star, supply a minimum cover, a matching bound, and an output the maximal-matching algorithm may return. Distinguish feasibility and optimality.
  2. Prove Independent Set≤pVertex Cover, naming both thresholds and both implications. Identify which direction would transfer a polynomial-time algorithm.
  3. Construct the literal-occurrence graph for (a∨b∨c) AND (¬a∨¬b∨d). Exhibit a size-two independent set and its cover complement.
  4. Why does O(nW) work with W=2^b fail to establish polynomial work in b? Why does NP-hardness not establish undecidability?
  5. Prove the maximal-matching cover guarantee, including why the output covers every edge. Give a case achieving ratio two and a weighted counterexample.
  6. A solver returns cover size 8 and matching size 5. Bound OPT and the returned solution’s ratio. Then suppose a time-limited exact solver stops without exhausting smaller candidates: state what can still be claimed.