Lecture 11: Karp's NP-Complete Problems - Partitions and Packing - Goldberg, March 4, 2026

Administrative Updates

Attendance Tracking

• Please text the word “present” to indicate attendance. Instructor will maintain attendance records using this method.

Course Notes Distribution

• Updated lecture notes will be sent at the end of the course (approximately 2 weeks from this date) rather than immediately after each lecture to avoid too many versions circulating.
• Current set of notes (Karp’s 21 NP-complete problems) will be used for approximately 1-3 more lectures, depending on pacing.

Next Class

• Class will continue on Monday (March 9, 2026).
• Same lecture notes will be used for the continuation of the Karp’s problems discussion.

Content Coverage

• Lecture 11 covers problems 4, 6, 12, 14, 18, 20, and 21 from Karp’s list of 21 NP-complete problems.
• Focus areas: partition-related problems (chromatic number, partition, max cut) and packing-related problems (set packing, set covering, exact cover, knapsack).

Continuing: Karp’s NP-Complete Problems

Problems 9, 10, 19: All Involve Permutations

Key Insight: These are the only three problems in Karp’s 21 that fundamentally involve permutations as their solution structure and brute-force search strategy.

Problem 9: Directed Hamiltonian Circuit

• Requires finding a permutation of vertices that visits each vertex exactly once and returns to the starting vertex
• The solution space is all permutations of vertices

Problem 10: Undirected Hamiltonian Circuit

• Similar to the directed version but works on undirected graphs
• Also requires finding a permutation of vertices with the same constraints

Problem 19: Job Sequencing (Scheduling)

Real-World Context: Imagine a manager contracts you to complete tasks. Each task has:

• An internal deadline by which it should be completed
• A penalty cost for missing that deadline

The manager understands that meeting all deadlines may not be possible but is willing to accept some penalty as long as the total penalty cost does not exceed a tolerance threshold (the manager is still okay because overall profit is high despite the penalty).

Problem Definition: Can one organize tasks in an order (permutation) such that when you check which tasks miss their deadlines and add up their penalty costs, the total is ?

Exhaustive Search Strategy: Generate all permutations of tasks. For each permutation, verify:

1. Check which tasks meet their deadlines
2. Sum the penalties for tasks that miss deadlines
3. Does this sum ?

The solution will be a permutation stored in an array of size .

Note: In Karp’s formal definition, the deadline information is given as (start date, number of days) or similar—however you specify it, you have the information needed to compute whether a task meets its deadline. Whether explicitly given or derived from start/end dates, the computational structure remains the same.

Note on Karp 17: The solution to Karp 17 (3D Matching) by having “no two elements of agree in any coordinate” results in a permutation of the values found in each of the coordinates. However, it is NOT included in the above list of three problems because this permutation property is incidental and has no bearing on the definition nor on the brute-force solution strategy.

---

Problems 12, 20, 21: (Fixed Size) Partitions of the Original Set

Understanding K-Partition vs. Partition

When dividing a set into subsets, there are two scenarios:

K-Partition: If you are told ahead of time how many subsets to create (the value ), it’s called a -partition. For example: “Divide these elements into exactly 5 groups.”

Partition: If you are not told ahead of time how many subsets to create (you decide how many groups you need), it’s called a partition. For example: “Group these elements however you like, and afterward tell me how many groups you created.”

The naming reflects whether is predetermined (k-partition) or determined after the grouping is complete (partition).

Reminder from Discrete Mathematics

To partition a set with elements means to divide it into nonempty subsets. Partition creates a set of subsets (also called “groups” or “boxes”).

Important: We assume we’re working with an unordered set (which automatically guarantees no duplicate elements) or an ordered set with explicitly no duplicates. This is critical because of constraint (2) below.

The Three Partition Constraints

Subsets must satisfy the following requirements to form a valid partition of set :

(1) Non-empty and Proper Subsets:

• No subset can be empty (no wasted groups or “boxes”)
• No single subset can equal the entire original set (unless )
• Each subset is a non-empty proper subset of

(2) Mutually Exclusive (No Duplicates): (for

Why This Matters: Imagine you’re packing items into boxes. You write an inventory for each box. You don’t want to rip open boxes later to verify the contents, so you rely on the written inventories. The only way this works is if no element appears in two different boxes—otherwise the inventory system breaks down.

This constraint only makes logical sense if:

• The original set is unordered (which guarantees no duplicates), OR
• The original set is ordered but explicitly has no duplicate elements

If either of these conditions is violated, you could have the same element in two different subsets, violating the mutual exclusivity constraint.

(3) Complete Coverage (Union):

• Every element of the original set must be placed into exactly one subset
• No element is left behind
• The union of all subsets equals the original set

This is the fundamental difference between partition and packing: In partition, “no one is left behind”—all elements must be assigned. In packing (problems 4, 6, 14, 18), elements can be left out.

Problem 12: Chromatic Number

Intuition: Imagine you are a painter hired to paint the vertices (nodes) of a graph such that no two adjacent vertices (vertices connected by an edge) have the same color. You’re given exactly paint colors to work with.

Real-World Example: In an interview, Taylor Swift described designing a ranch kitchen where cabinet knobs had kitchen themes (fork, spoon, knife). If a cabinet had two doors (connected nodes), the two knobs had to be different themes. You couldn’t have “spoon-spoon” or “fork-fork” on the same cabinet—this is the essence of the chromatic number constraint: adjacent nodes must have different colors.

Formal Definition: Given a graph and colors, assign each color to a subset of vertices such that:

• Each vertex has exactly one color
• No edge connects two vertices of the same color
• The solution uses exactly colors (where is a user-supplied parameter)

Why This Is a K-Partition:

At first glance, chromatic number might not seem like a partition problem. However, consider the following:

Once you’ve colored all vertices, you can group vertices by color:

• Color 1 subset: All vertices painted with color 1
• Color 2 subset: All vertices painted with color 2
• … and so on

This creates a -partition of the vertices into subsets (one per color). The three partition constraints are satisfied:

1. Non-empty subsets: No color is left unused (assuming colors are actually needed)
2. Mutually exclusive: No vertex is painted with two colors—each element (vertex) belongs to exactly one subset
3. Complete coverage: Every vertex must be painted with some color—all vertices are assigned

The Extra Constraint: After generating all possible -partitions of vertices, not all of them are valid chromatic colorings. You must verify that for every edge in the graph, and are in different color subsets (i.e., they have different colors).

Verification: Straightforward once the vertices have been painted—check that no edge has both endpoints with the same color.

Solution Storage: The solution can be stored in an array of length with values , where array[i] indicates the color of vertex .

Problem 20: Partition

Directly involves the partitioning of a set of weights/values into two groups such that the sum of weight of the first group equals the sum of weight of the second group.

Verification: Trivial—are the sum of weights of each of the two groups equal to each other.

Problem 21: Max Cut

A weighted graph problem. with (could be , either positive integer or positive reals).

Partition the vertices into two groups such that the sum of all the weighted edges between (and not inside) the groups is the most (max) as compared to any other such partition/grouping. The last two problems clearly require generating partitions with two groups whereas the first problem (chromatic color) requires partitioning into groups, one for each color chrome. But all of these are fixed values.

Verification: Trivial—are the sum of weights of each of the two groups equal to each other.

Note: With modification by Karp using a tolerance parameter : Can one find a max cut whose sum of the cut edges is at least ? This converts it to a decision problem with trivial verification.

---

Problems 4, 6, 14, 18: All Related to Packing

Key Distinction: These problems are inspired by the partition concept but differ in one fundamental way: elements do not have to be placed into a subset.

In partition, the rule is “no one is left behind”—all elements must be assigned. In packing, elements can and often do remain unpacked.

In the first three problems (Set Packing, Set Covering, Exact Cover), you have already packed boxes (predetermined subsets) and must choose which boxes to take. In knapsack, nothing is packed yet—you pre-assign items to weights and must select which items to include.

In all four packing problems, there’s a limitation: in Set Packing, Set Covering, and Exact Cover, you can only select boxes; in knapsack, there’s no limit on the number of items but a weight capacity constraint.

Important Note: The commonality here is that the application is similar (choosing from available options) but the brute-force approach is not necessarily the same.

Critical Principle: Just because a problem is defined a certain way does not mean that is the way to solve it.

For example, consider problems Karp 7 (Feedback Node Set) and Karp 8 (Feedback Arc Set). Both are defined in terms of finding and removing ALL cycles in a graph, yet the exhaustive search approach doesn’t actually generate and check all cycles. The definition and the solution strategy can differ significantly.

Problem 4: Set Packing

Already packed boxes; the question is to choose which boxes to take.

No two boxes taken may have similar elements.

Problem 6: Set Covering

Already packed boxes; the question is to choose which boxes to take.

Choose boxes such that every item is present (ignoring duplication).

Problem 14: Exact Cover

Already packed boxes; the question is to choose which boxes to take.

Choose boxes such that no duplication and every item is present (c.f. lines 106-7 above).

Problem 18: Knapsack

Nothing packed yet.

(c.f. lines 28-33 above).

---

Problems 4, 6, 14, 20: All Related to Partition

All of the following problem definitions are related to partitions and inspired by the mathematical notion of partition but not solved based on partition except Karp 20, which by name and definition is about partition.

Problem 4 (Karp 4): Choose boxes (subsets) such that there is no duplication between the boxes. (c.f. line 76 above, criteria 2 of partition definition)

Problem 6 (Karp 6): Choose boxes (subsets) such that the totality of the inventories in the boxes has at least one element of every item they have. This is termed “cover”. (c.f. line 106 above, criteria 3 of partition definition)

Problem 14 (Karp 14): Choose boxes (subsets) such that no duplication (c.f. line 105 above, criteria 2) AND covering all items manufacture (c.f. line 106 above, criteria 3).

Note: These three problems have a brute-force algorithm based on the Choose function .

Problem 20 (Karp 20): Directly involves the Partitioning of a set of weights/values into two groups such that the sum of weight of the first group equals the sum of weight of the second group.

Verification: Trivial—are the sum of weights of each of the two groups equal to each other.

Note: Karp 18 (knapsack) technically is not about Partition, because the items not packed are left out and partitions must place all items somewhere.

---

Problems 5, 15, 16, 17: The Rest of the Problems

These don’t have a single category to unify these problems.

Problem 5: Node Cover

Find a set of nodes (user decides on ) such that each edge of the entire graph has some vertex in common with a vertex found in the node cover.

Note: Any number of edges are allowed to be connected to the same vertex of the node cover. As such the mapping is surjective and not necessary to be injective.

Note: This problem can be grouped with other graph theory problems listed above, but then the category would be too generic, whereas the above categories are more specific (such as cycles or cliques).