Reduction direction and both implications
What this concept is
A polynomial many-one reduction A≤pB maps each input x of decision problem A to an input f(x) of B in polynomial time, with x a yes-instance exactly when f(x) is a yes-instance. A solver for B then solves A through this transformation.
Why it matters here
Reductions transfer algorithms and hardness in opposite verbal directions. To show target B is hard, reduce a known hard A to B, not merely B to A.
Concrete example
Independent Set asks whether G has at least k mutually nonadjacent vertices. On an n-vertex graph, map (G,k) to Vertex Cover (G,n−k). If I is independent, every edge has an endpoint outside I, so V minus I is a cover. Conversely, if C covers every edge, no edge has both endpoints in V minus C, so that complement is independent. Sizes transform in both directions.
Common confusion / misconception
One implication is insufficient. Reversing the arrow because the prose sounds similar can turn a hardness proof into an upper-bound argument. The graph complement and the complement of a vertex set are different objects.
How to use it
State source, target, transformation, runtime and yes/no equivalence. In the lab, restrict thresholds to 0≤k≤n; a general decision reduction handles out-of-range thresholds with trivial fixed yes/no outputs. The same-graph transformation is linear in the written graph size and only changes k. It establishes equivalence; to infer NP-hardness you still need a justified hard starting problem.
Check yourself
If B has a polynomial-time algorithm and A≤pB, which problem becomes polynomial-time solvable? What if only A has one?
Mini drill or application
On a four-vertex path, turn independent set {0,2} into a cover and reverse the step. Give an example showing why merely mapping every yes-instance to yes is not enough: a map sending every input to a fixed yes-instance loses no-instances.
Read this only if stuck
Use Erickson’s Algorithms and lecture notes for reductions and hardness, and the selective reading guide for the matching approximation. Full-book reading is not required.