Reductions
In short: a reduction shows that two problems are secretly the same problem. If you can turn any instance of problem A into an instance of problem B, solve B, and turn B's answer back into an answer for A, then A is "no harder than" B — and if the reverse translation also exists, they're exactly as hard as each other. This lesson builds one concretely: a group of bidders with no conflicts between them (an independent set) and the group left over once you remove it (a vertex cover) are the same object seen from two directions. Solve either search and the other answer falls out for free, with nothing left to compute.
Two conflicting bidders can't both win
Meridian's bid desk is handed a tender where some bidder pairs can't both be awarded — maybe they'd need the same depot slot at the same hour. Draw a node per bidder and an edge per conflict:
Four bidders, three conflicts. Which group can all be awarded together, and which group has to be turned away to clear every conflict?
Try acme and crane together. The edges acme-bolt and bolt-crane don't connect two chosen nodes, and crane-delta doesn't either — no conflict lands inside this group. It's independent. 4 nodes, 3 edges, undirected. Settled: acme, crane.
An independent set and a vertex cover of the same graph are complements of each other — every bidder is in exactly one of the two groups:
def is_independent_set(bidders, conflicts, group):
group_set = set(group)
return all(not (a in group_set and b in group_set) for a, b in conflicts)
def is_vertex_cover(bidders, conflicts, cover):
cover_set = set(cover)
return all(a in cover_set or b in cover_set for a, b in conflicts)
bidders = ["acme", "bolt", "crane", "delta"]
conflicts = [("acme", "bolt"), ("bolt", "crane"), ("crane", "delta")]
group = ["acme", "crane"]
cover = [b for b in bidders if b not in group]
print(is_independent_set(bidders, conflicts, group), is_vertex_cover(bidders, conflicts, cover))Brute force, both directions, same answer
Searching for the biggest independent set and searching for the smallest vertex cover are the same exponential search, just read in opposite directions — try every subset, check a condition, stop at the first success:
Neither direction is secretly faster. Proving A reduces to B is never a promise that either one got easier — it's a promise that they rise and fall together. If someone ever found a fast algorithm for vertex cover, the same reduction would hand you a fast algorithm for independent set, for free, by just complementing the answer.
This should return the complement of ["a", "c"] within ["a", "b", "c"], which is ["b"]. It currently returns ["a", "c"] itself. Flip the condition.
Quick practice
bidders = ["x", "y", "z"]
conflicts = [("x", "y"), ("y", "z")]
group = ["x", "z"]
cover = [b for b in bidders if b not in group]
print(sorted(cover))def both_sides_agree(bidders, conflicts, group):
cover = [b for b in bidders if b not in group]
group_set, cover_set = set(group), set(cover)
return len(group_set) + len(cover_set) == len(bidders)
print(both_sides_agree(["a", "b", "c", "d"], [], ["a", "b"]))🎯 Your turn
Build smallest_conflict_resolution(bidders, conflicts). Brute force the
largest independent set by trying subset sizes from biggest to smallest
and keeping the first one where no conflict pair lands fully inside it. Then
return {"independent_set": ..., "vertex_cover": ...}, where vertex_cover
is every bidder not in that set — both sorted.
smallest_conflict_resolution(["a","b","c","d"], [["a","b"],["b","c"],["c","d"]])→independent_set["a", "c"],vertex_cover["b", "d"].
Hint: itertools.combinations(bidders, size) tried from len(bidders)
down to 0 finds the largest valid group first. The cover is just
"everyone else."
Press ▶ Run, try the Live App chips, then ✓ Check.