Independent set
Watch on YouTube →
Overview
Kent Quanrud uses maximum independent set to compare the complexity of general graphs with two structured cases, intervals and trees. A reduction from 3-SAT shows independent set is hard on general graphs, while an interval-to-DAG dynamic program runs in O(n log n) and a rooted-tree dynamic program runs in O(n), illustrating how structure and carefully chosen subproblems enable efficient algorithms.
Key takeaways
- A 3-SAT formula with M clauses reduces to independent set by making one triangle per clause and connecting contradictory literal occurrences; satisfiability is equivalent to an independent set of size M.
- The weighted interval recurrence compares skipping interval k with taking it and jumping to the first interval that starts after k ends; sorting and binary search make the full algorithm O(n log n).
- For intervals, directed edges between non-overlapping pairs form a DAG ordered by start time, and paths correspond to compatible interval sets.
- Dynamic programming becomes efficient when subproblems have a compact structure: arbitrary interval choices can yield exponentially many states, while sorted suffixes yield only n states.
- Rooting a tree turns its descendant sets into subproblems; adding an exclude-root flag captures the constraint from a selected parent and gives an O(n)-time maximum-weight independent-set algorithm.
Chapters
- The recap connects 3-SAT to SAT through a polynomial-time reduction that preserves whether an instance is satisfiable.
- Maximizing satisfied 2-SAT clauses can encode 3-SAT, despite ordinary 2-SAT being solvable in polynomial time.
- Subset sum can encode many constraints in the bits of its numbers, while longest path is tractable on DAGs but hard on general graphs.
- An independent set is a collection of vertices with no edge between any selected pair.
- The opening graph exercise finds a set of 5 vertices and asks whether a sixth can be added.
- Variants include maximum-weight independent set and decision questions such as whether a graph has an independent set of size K.
- Interval scheduling becomes independent set by representing each job as an interval and connecting overlapping jobs.
- Trees are a special graph class with no cycles, while interval overlap graphs are another structured special case.
- The class predicts that general graphs may be hard, then tests whether intervals and trees offer enough structure for algorithms.
- The reduction goal is to construct a graph and target K so that a 3-SAT formula is satisfiable exactly when the graph has an independent set of size K.
- Variable and negated-variable vertices can represent truth choices, with edges forbidding inconsistent choices.
- Clause gadgets must let the independent set select a choice that corresponds to a satisfying assignment.
- Each 3-literal clause becomes a triangle whose three vertices represent its literal choices.
- Because every pair of triangle vertices is adjacent, an independent set can select at most one vertex per clause.
- Edges between occurrences of a variable and its negation prevent the chosen clause literals from contradicting one another.
- For a formula with M clauses, the construction has an independent set of size M exactly when the formula is satisfiable.
- Given a satisfying assignment, select one true literal vertex from every clause; the assignment ensures no selected pair conflicts.
- Conversely, an independent set of size M must choose one vertex from each clause triangle, and its choices define a consistent satisfying assignment.
- For a clause with r literals, replace its triangle with a complete graph on r vertices so the independent set can choose at most one literal.
- The reduction's central rule is to represent each clause and enforce consistency between complementary variable choices.
- The lecture then shifts from general graphs to weighted interval scheduling.
- Each interval has a weight, such as a job's profit, and the goal is to maximize the total weight of non-overlapping intervals.
- The worked example selects intervals with weights 4, 2, 2, and 5, totaling 13.
- A greedy score based on how many intervals a choice eliminates can fail when many high-weight intervals overlap each other or eliminate the same alternatives.
- Although interval overlap graphs are a special case of general graphs, their geometry rules out many arbitrary graph patterns.
- Create an auxiliary graph with an edge between each pair of non-overlapping intervals, directed from the earlier start time to the later one.
- Paths in this DAG correspond to non-overlapping interval sets: sort a compatible set by start time to obtain a path, and read a path to obtain a compatible set.
- Building all pairwise edges can take O(n²), after which DAG longest path takes linear time in the constructed graph.
- The unrestricted recurrence tries taking or skipping an interval, but taking one can leave an arbitrary subset of intervals.
- Memoizing that recurrence may still create exponentially many distinct subproblems, with an estimated 2^n search.
- Sorting intervals by start time creates a sequential structure and allows subproblems to be represented by suffixes rather than arbitrary subsets.
- For the suffix beginning at interval k, compare skipping it, MWIS(k+1), with taking it, w_k plus the best suffix beginning at the first compatible interval.
- Sorting by start time makes the compatible successor searchable by its start point, using binary search instead of scanning all remaining intervals.
- There are n suffix subproblems and each successor lookup takes O(log n), so sorting and dynamic programming together take O(n log n).
- An arbitrary tree can be rooted at any vertex, turning the descendants of each vertex into a well-defined subtree.
- These subtrees provide natural dynamic-programming subproblems, much as sorting gives intervals a useful order.
- Vertex weights mean a parity-based choice is not sufficient, since a high-weight vertex may make skipping its neighbors worthwhile.
- Define a subproblem for the maximum-weight independent set in the subtree rooted at vertex v.
- If v is excluded, combine the best solutions for each child subtree; if v is included, its children must be excluded.
- Writing the include case directly requires recursing to grandchildren, which makes the recurrence and running-time analysis awkward.
- Add a Boolean flag indicating whether the root of a subtree must be excluded, making the recursive state explicit.
- When exclusion is required, sum the unrestricted child-subtree values; otherwise, take the maximum of excluding v or adding its weight and requiring every child to be excluded.
- The two states per vertex and the total number of child relationships are both O(n), yielding an O(n)-time dynamic program.
Transcript excerpt
0:05 Okay. All right, let's start. Yo, Digger. No, it's it's all good. Okay. All right, so today we're doing uh independent set and some related problems. So, okay, what have we been doing? Usual recap. So, we started looking at um SAT. Uh does anyone know what SAT stands for? Yeah, no trumpets. Um Anyway, so I just give you like a Boolean formula, right? Very simple uh looking thing. And all you want to do is figure out if there's some inputs that make it output true. It's very much like guess the password. And uh and somehow even though that seems like it should be easy for a computer, we don't have an algorithm for it. And we don't have algorithms for uh we
0:52 don't have an algorithm for it. That's like a big question. Uh but the weirdest thing is that we might not have algorithms for special cases, either. CNF SAT is where we kind of flatten out the tree. So, it's like a very uh kind of shallow formula. That too we can't solve. Even if we limit it to just three variables, we can't solve. We can't solve insofar as we showed that if you could solve three SAT, then you can solve the original Boolean SAT. Yeah, and somehow it's sort of a weird algorithmic answer without an algorithm. We wrote an algorithm or a sketched algorithm that takes a Boolean SAT formula and turns it into a three SAT formula and runs in polynomial time. So, that the resulting three SAT formula, if you can solve it, you can solve the original Boolean. So, it preserves everything, right? So, somehow you like made an algorithm to show there's no algorithm, which is kind of like a funny way to see things. But I'm
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.