CSE 421 Notes

Maximum number of edges in an undirected graph with n vertices: \(\frac{n(n-1)}{2}\). (every vertex connected to every other).

Maximum number of edges in a tree:

Lemma: A tree plus an extra edge is not a tree. Now there are two paths between the nodes connected by the new edge.

Using lemma ^^: Maintain a set of vertices and a set of edges. Add any one vertex to the vertex set. Repeatedly, choose any unexplored edge touching one of the explored vertices. This will add exactly one new vertex and one new edge to the maintained sets (certainly one edge. certainly not more than one vertex. Certainly at least one vertex because there's only one path to each vertex from the original vertex, and this is the first time exploring the path containing this edge, so it must be new). Thus, the size of the vertex set is always one greater than the size of the edge set. We terminate when all vertexes have been explored. At this point there will be n-1 edges. The set of explored edges and vertices is a tree (every two vertexes are connected by a path through the original vertex, and its a subgraph of a tree), and therefore there are always exactly n-1 edges.

Another way to prove: lemma: (assuming at least two vertices) at least one vertex has only a single edge. Else, you could keep going forwards on new edges, but finite number of vertices, so you'd eventually make a loop, which implies two ways to connect any two vertices in the loop, so not a tree. Now to use the lemma: Claim that each tree has n-1 edges. Suppose true for n-1 (i.e., tree with n-1 vertices has n-2 edges). Now take the tree with n vertices. One of the vertices has exactly one edge, by the lemma. Consider the tree formed by removing that vertex and edge. It's certainly still a tree, since no vertices were connected through the removed vertex. By inductive hypothesis, smaller tree has n-1 vertex and n-2 edges. Adding back in v, the full tree has n vertex and n-1 edges.

"Adjacency Array": Two arrays, first one is how many neighbors each vertex has, second stores the indexes of the neighbors.

Adjacency list: An array of linked list heads, each list being all the nodes touching that first node.

Adjacency matrix: Alright, but takes up lots of space, even though graphs are usually sparse.

Bipartite: Can choose two sets of vertices, so that all edges cross between sets.

Equivalently, a bipartite graph is "2-colorable": We can color each node such that it is only connected to nodes of the other color.

If a graph has an odd-length cycle, it's certainly not bipartite.

Color some node red. Add all the edges touching that node to a queue. Iterate the edges in the queue and if one side is colored, color the other side opposite. If already colored correctly, do nothing. If both sides have same color, return false. Every time a node is colored, add all its edges to the queue if not already processed.

The way taught in class: Do a BFS to generate levels away from some root vertex.

BFS and DFS on graphs are not trivial, because the graph is not already a tree. It's not quite as simple as when you do BFS or DFS on something that's already a tree. Instead, both BFS and DFS create a tree on top of the graph. There are different properties of these trees, and special properties of the non-tree edges.

A trivial application of BFS (or DFS) is to find the connected component around a node. (in undirected, at least)

"Nontree edges" in BFS are either between nodes at most one level apart (level = distance from root.)

To find the youngest common ancestor of two nodes, we can't really use BFS. Imagine the graph 1->2, 1->3, 2->4, 2->5, 3->4, 3->5. A reasonable BFS result is 1->2, 1->3, 2->4, 3->5. The youngest common ancestor of 4 and 5 is 2 or 3, but the BFS seems to indicate 1. Instead, we should use DFS here.

The edges in the DFS tree can be weird – between levels, or across the same level (level = minimum distance to starting point). However, the "non-tree" edges only go between ancestors. The only reason an edge x,y would not be explored by DFS is that, while some other edge from x was being explored, y was explored already. But this means y is a descendent of x.

An invariant maintained during DFS: If a node is fully explored (recursion returned from that node), then all descendants of that node are fully explored. (This is not true for BFS)

topological sort is possible iff the graph is a DAG. topo sort => DAG: cycle certainly prevents topo sort. DAG => topo sort: It's true that every DAG has a vertex with no incoming edges (else, you could keep traversing backwards indefinitely. Similarly, there must be one vertex with no outgoing edge, or you could traverse that way too). That vertex can go first. If we remove it, the graph is still a DAG, so we can choose a next vertex, etc, forming a topo sort.

One way to come up with a topo sort is to repeatedly find the vertex with no incoming edges. Keep a priority queue of nodes by the number of incoming edges. The lowest should have zero. Then decrement each node that had an edge with the removed node, and take the new lowest node. Time complexity is O(n+m log n); the O(n) is the simple loop through the vertices (also the time to build the heap) while m log n is to decrement each edge.

Using DFS we can do even better. An invariant maintained during DFS search is that, when we return from recursion on a given node, all descendents of that node have already been explored (though perhaps during earlier recursions on othe nodes). Because of this, during DFS we simply add each vertex to the front of a list once we return from its recursion, and we know that it's ahead of all its dependencies in the list. Every node gets added to the list, and every node precedes its descendants, so it's a topological sort in O(n+m) time!

Spanning tree: A subset of a graph which is a single connected tree and contains all the vertices.

Minimum spanning tree: A spanning tree which minimizes the sum of the cost of edges included in the tree.

Dijkstra's algorithm always finds a spanning tree, but it's not necessarily minimal. Eg, all edges have cost 1. Dijkstra from 1 may find 1->2->3 and 1->4->5. But if there's also an edge from 3-5, then the MST should be 1-2-3-5, not 3-2-1-4-5.

MSTs can be used to help optimize the cost of building a network (of roads, electricity, etc), and can approximate some problems like traveling salesman.

Cut: A set of edges such that if those edges are removed, the graph is split into exactly two nonempty connected components.

Cut property: For any valid cut, the lowest-cost (lightest) edge in the cut (means, removed by the cut) must be included in any MST. Certainly some edge of the cut must be included, otherwise the tree would not be connected. In fact, exactly one edge from the cut must be included. More than one would cause a loop (easy to see why). So we should certainly include the cheapest.

Cycle property: Most expensive edge of any given cycle is not in MST. If it were, then TODO

Given a whole bunch of time intervals, find the largest subset of the intervals that does not overlap.

The solution is to sort the jobs in terms of ascending end time of the job, and always select the first job from the list that's compatible with the jobs selected thus far.

Suppose there's a better schedule, with n intervals, where the first selected one does not have the earliest ending time. Now replace the first interval with the one with earliest ending time. There are still n intervals, so it's at least as good. We can repeat on all the intervals to show that ours will have at least n intervals too. So our earliest ending time algorithm produces a list of intervals at least as long as any other.

Closely related is the classroom scheduling problem: Given a whole bunch of class times, what's the minimum number of classrooms we need?

You can't just use the interval scheduling to stuff as many classes in each classroom as possible – sometimes not optimal. Eg, 1->2, 4->5, 1->3, 2->6. The greedy algo will require three classrooms. But it can be done in 2.

Define depth of the schedule: max_t {number of intervals including time t}. Certainly can't use less classrooms than the depth. Thus, if we develop an algorithm that results in using exactly depth many rooms, we know it's optimal.

When we order in terms of start time, if there are classes in d many rooms simultaneously, then that means the depth at that time is d as well. Consider what happens every time we place a class. Inductive hypothesis: The current number of classrooms in use is the depth just left of point, so adding the new classroom will not increase the depth to anything more than the depth right at point. Finally, adding the new class will not cause a conflict, because there are no future classes placed yet for it to conflict with.

You have some jobs to do (you're only one person). Each has a deadline \(d_j\), and takes a certain amount of time \(t_j\) to complete. What can you do to minimize the maximum lateness for any one job (sum doesn't matter)?

Selecting based on start time is certainly bad; the one with earliest start time might last the rest of the time!

You should always work on the task that's due soonest (choose arbitrarily if due at same time).

Take any given schedule. If there are two tasks that are not ordered in terms of first due first, then there exists an adjacent pair that's not ordered in terms of first due first (if not adjacent, the intermediate steps may make things worse). Swapping these two will not affect lateness of other tasks. Out of the two tasks, the one with later deadline cannot be the global latest, because the earlier deadline one would be even greater. The only alternative is that neither is the global latest. Either way, switching them can only decrease lateness. After switching adjacent pairs enough, the whole schedule will be ordered as described. Any schedule can be reduced to this one while only improving it, so it's optimal.

Given a list of things that will be stored in cache, in a given order, and a limited cache size, how do you choose which things to evict in order to minimize number of cache misses?

Evict the one that is only needed furthest in the future. Nontrivial proof? TODO

In making a good code, we want to give frequent symbols shorter representations while ensuring that one code is not a prefix for another. A "prefix code" is any code where one code is not a prefix of another.

An ideal character code minimizes \(\sum P(c)\ell(c)\), where P(c) is the probability of this character, and l(c) is the length of the code for that character.

Huffman's algorithm: We build a binary tree from the bottom up. The left child of each node has a 0, followed by the child code. The right is similar, with 1. Choose the two least frequent characters (using a priority queue), make a little subtree out of them (assigning 0 and 1 arbitrarily), and insert that subtree into the pqueue with its probability being the sum of its components. Repeat until the whole tree is built.

We want to have a party where everybody knows n people, but also does not know at least n people. That way they are comfortable but make new friends too. How do we select the maximum number of friends satisfying this criteria?

It's not trivial (ie, 0 people or all of them), because if there's someone with degree 1, we cannot add them, but still may be able to throw a party.

Start with the set of everybody. Until S stops changing, filter S down to those friends with degree at least 4 (in S only), then filter again to degree less than n-4 (still in S only). Once the loop is done, S is the set of friends to invite.

First, prove that S always contains the final set: Suppose S is a superset of the final set we're interested in, and then we perform one step of the loop. Any person with degree<4 certainly won't have degree>=4 in the final set, so they are safe to remove. Similarly, if there are less than four people the person doesn't know in the current S, then there are certainly less than four people who they don't know in the final result too.

Next, prove that the loop terminates, and the desired conditions are met at termination. At each loop cycle, S gets smaller or stays the same. It can only get smaller a finite number of times, and as soon as it stops getting smaller, the loop terminates, so it does always terminate. Finally, when it terminates, all nodes in S fit the criteria for inclusion in the final result. So final \(S\subseteq result\).

This is a different approach to a greedy problem. Most greedy problems add things one by one using a simple rule. To show correctness, you prove that each time you add something to the result, it remains correct, and that when the algorithm terminates, everything appropriate has been processed. In this party problem, we remove things one by one using a simple rule. At each step, we prove that nothing important was removed. Finally, we prove that the algorithm terminates at the correct state.

Generalization of BFS to arbitrary nonnegative edge weights. Maintain a queue of adjacent, unexplored nodes (just like BFS), but use a priority queue on shortest known path to each node instead of FIFO to determine which node to explore next.

Also include a set of explored nodes; no need to explore them again, the first time we see them, we have the shortest path.

Works on directed and undirected graphs.

Negative weights can break Dijkstra's. That's because, with negative weights, the cheapest path may begin with a very expensive prefix, which Dijkstra's will not explore first.

Dijkstra's counts as a greedy algorithm.

Time complexity is \(O(n\log n+m)\), because for each node we have remove and add things to a priority queue (TODO: why exactly this?)

Slight modification: How would you find the shortest, cheapest path? First thing that comes to mind is to keep track of lengths, and break ties in the priority queue by length. If all the edge costs are strictly positive integers, then we can simply add 1/n to the cost of each edge (where n is the number of nodes). This doesn't cause a problem because any shortest path has at most n-1 edges in it, so the extra contribution due to the 1/n will sum up to less than 1.

Bidirectional Dijkstra: Do dijkstra's from start and endpoints, stop when they meet. (TODO why?)

Memory: Merge sort naïvely requires you to create a new array to store each merge result. It's possible, but not simple, to create an in-place merge sort.

Locality: During merge, we have to look between the different merging arrays very frequently. With quicksort,

If we do quicksort with a randomly selected pivot, it has pretty much the same recurrence and by extension time complexity as merge sort.

Exponentiation for large exponents (esp. useful modular exponentiation).

Finding any one root of a function on an interval [a,b], given that f(a)<0 and 0<f(b). In 2d, keep bisecting the space, then checking endpoints to see if the IVT guarantees a root in that section. Always at least one subsection will have a guaranteed root by IVT, because of IVT on the root and induction. It is log(n) to find an interval of width \((b-a)2^{-n}\)

Given an array of positive real numbers, what consecutive subarray has the maximum product? Naïve is \(n^2\). But we can split in half, and for each half, calculate:

• Largest subarray overall.
• Largest subarray touching the left edge.
• Largest subarray touching the right edge.
• Product of the entire thing.

Combining the results is not too hard:

• Largest overall: Max(overall from either half, right edge of left*left edge of right)
• Largest touching left: Max(left of left, all of left*left of right)
• Largest touching right: Max(right of right, all of right*right of left)
• Entire thing: entire left*entire right

The base case is trivial.

(defun maxseq-divide-and-conquer (seq &optional (operation #'*))
  (labels ((op (&rest args)
             (apply operation args))
           (%%% (seq)
             (if (= 1 (length seq))
                 (let ((val (elt seq 0)))
                   (values val val val val)) ;; May not be totally right for all operations?
                 (let* ((left-length (floor (length seq) 2))
                        (right-length (- (length seq) left-length))
                        (left-array (make-array (list left-length) :displaced-to seq))
                        (right-array (make-array (list right-length) :displaced-to seq :displaced-index-offset left-length)))
                   (multiple-value-bind (b1 l1 r1 w1) (%%% left-array)
                     (multiple-value-bind (b2 l2 r2 w2) (%%% right-array)
                       (values (max b1 b2 (op r1 l2))
                               (max l1 (op w1 l2))
                               (max r2 (op r1 w2))
                               (op w1 w2))))))))
    (%%% seq)))

This is T(n)=2T(n/2)+1, which is O(n). An algorithm that needs to keep track of fewer things, at the cost of taking O(n log n) time, is to only record the maximal subsequence for each subproblem, and then manually calculate the largest one that goes between sections, which has T(n)=2T(n/2)+n.

There's something simpler we can do, though, suggested by one of the practice midterms. For each index in the array, we calculate the largest consecutive subarray which ends with that index. This is easy to do recursively, using the greatest product at the previous index. If the product at the previous index is greater than 1, then the greatest product at this index is the last one, times this one. On the other hand, if the product at the last index is <1, then the best at this index is just the current index.

(defun maxseq-linear (seq &optional (operation #'*))
  (loop with max = nil
        with result = nil
        with last = nil
        with lastseq = nil
        for item in seq
        do (progn
             ;; for only multiplication, we could simply check (> last 1)
             (if (and last (> (funcall operation last item) item))
                 (setq last (funcall operation last item)
                       lastseq (cons item lastseq))
                 (setq last item
                       lastseq (list item)))
             (when (or (null max) (> last max))
               (setq max last
                     result lastseq)))
        finally (return (nreverse result))))

Here's another algorithm: Given two lists of movie preferences, how many pairs of movies are there where user 1 prefers one movie, but user 2 prefers another? Ie, how many "inversions" are there between two permuted lists? Like often, we split the array into two blocks, calculate the number of inversions within each block, then somehow calculate the inversions between blocks. The base case is easy: A single element has no inversions.

Given two blocks, how do we find the inversions that cross between them? Note that we are doing divide and conquer on two lists simultaneously – user 1's preferences, and user 2's. So, when we split into 2 blocks, there are actually four blocks: \(a_l,\ a_r,\ b_l,\ b_r\). The idea is to find \(|a_l\cap b_r|\) and \(|a_r\cap b_l|\), then multiply the two together. This is basically the definition of a cross-section inversion. So how do we find the cardinalities of these sets? naïvely, it's n² and we're no better off than before. But now suppose we write our algorithm as an augmented merge sort, where just before merging (usually we'd merge a_l and a_r, then separately merge b_l and b_r), we do a "dry run" merge between a_l and b_r, then separately between a_r and b_l, which tells us how many elements are in common between the two!

The unfortunate extra requirement of this algorithm is that there is some (arbitrary) total ordering of the movies.

Not about finding the closest point to a given point, but rather finding the two points whose distance is minimal throughout the whole data set.

Repeatedly split the world in half, then recursively find the minimum distance sigma in that half. Splitting in half requires you to sort the points by one coordinate, n log n. Then, we need only check along a strip of width 2*sigma along the split axis.

The base case is an n² search, which is cheap if the square is small enough.

How do we efficiently check along the strip (recombination step)? Number of ways. One is to sort along the axis, then only check those within sigma on either side.

We can split the multiplicands into two sections with equal numbers of bits (approximately). Eg, \(x=2^{n/2}x_1+x_0\), and same for y. Then

\[xy=(2^{n/2}x_1+x_0)(2^{n/2}y_1+y_0)=2^nx_1y_1+2^{n/2}x_1y_0+2^{n/2}x_0y_1+x_0y_0\]

This requires four multiplications and O(n) recombination, which turns out to be O(n²), for no improvement over the naïve multiplication strategy. But there's a trick:

\[(x_1+x_0)(y_1+y_0)=x_1y_1+x_1y_0+x_0y_1+x_0y_0\]

So if we calculate \(x_1y_1\), \(x_0y_0\), and \((x_1+x_0)(y_1+y_0)\), we can find \(xy\) by just doing bitshifts and additions! This reduces the recursion to \(T(n)=3T(n/2)+O(n)\), which turns into \(O(n^{\log_2 3})\approx O(n^{1.585})\)

Strassen developed slightly faster ways to multiply 2x2 and 3x3 matrices. To apply to larger matrices, use divide and conquer with block matrix multiplication formulas.

Allows performing n-body gravity simulations or equivalent in linear time to the number of bodies! Another way to word it: For vectors \(v_1,\dots, v_n\), quickly compute \(Vx\) where \(V_{ij}=\|v_i-v_j\|_2^{-1}\).

Each item has weight and value. Our pack has a maximum weight. How can we choose items to maximize the value without exceeding max weight?

It's 2ⁿ to consider all possible combinations of items. Instead, let's use DP. Enumerate the items. Our subproblems return the best subset of items after some point i in the enumeration that weighless than a given weight (which may not be the same weight as in the original problem).

Assuming weights take nonnegative integer values up to a maximum W, the time complexity is clearly bounded above by O(Wn), because that's the number of possible unique subproblems. However, W can be exponential in n; imagine that the weight of the i-th item is 2ⁱ. Then there are exponentially many different combinations of weights, and no good way to reduce them.

The knapsack problem is related to how to pay for something with a minimal number of coins. Because of the way they are, US denominations allow coin choosing to be a greedy problem. But it is not so for arbitrary weights. Sometimes it's better to pick two medium-value, medium-weight items rather than one high-value, high-weight item.

RNA has four letters, AUCG. It's not just a linear sequence, though – there are loops. We therefore define the secondary structure of RNA as a list of pairs (b_i,bj) to indicate an extra connection (there is always an implicit connection b_i to \(b_{i+1}\)). Rules:

• At least three bases in between two paired bases. So, (b_j,bj) implies j-i≥4.
• No "crossing"s. So (b_i,bj) and (b_k,bn) implies i<k<n<j or k<i<j<n, but not i<k<j<n or k<i<n<j.
• A-U and G-C pairs are allowed, nothing else.

Goal is to maximize number of these "base pairs" without breaking the rules. This minimizes the "free energy" in the molecule.

TODO

Given a list, can it be decomposed into n subsets, each with an equal sum?

The extremely naïve way is to check all permutations, in n! time.

We can do it in n³ with DP. Our recursive subproblem is, given a list, can it be decomposed into n subsets with given sums x, y, and z? If the list has one element, easy base case. Else, remove the first element, and spawn three subproblems, with that first element subtracted from each of x, y, and z separately. Return true if any subproblem does.

We can add gaps to a word and also just replace characters. How can we go from one string to another minimizing the sum of gaps and replacements? This is edit/Levenshtein distance.

Calculate and store Levenshtein distance for the i-th and j-th suffixes of each string. This given mn time and space. If we go from shortest suffixes to longest, we don't need to store the entire n*m memoize matrix, only those for suffixes of length k-1 where k is the length currently being considered, reducing to nm runtime and n+m space.

This is sufficient for calculating the Levenshtein distance, but what if we also want to recover the instructions to perform the "alignment"? You can store the partial instruction in each memoize location, but that's going to take a lot of memory – near the end of execution, the amount stored in each memoize cell will be n+m, and you're storing n+m many of them, for … O((n+m)²), no good.

Something better is to keep track of TODO

Do DP using "longest path starting at node i".

Do DP on the longest increasing subsequence ending at each array item. Worst case n² if the whole sequence is increasing.

TODO: how to do in n log n with segtree?

Goal: Shortest path from fixed node s to all other nodes.

We disallow "negative cycles" because by going in a loop you can continually improve your path. This also means we disallow undirected edges, because that's a directed cycle.

Cannot use Dijkstra's because of negative weights.

For every node, the best path to s is the best path to s from each neighbor plus the weight of the edge to said neighbor. (True because shortest path must go through some neighbor). But how do you implement? Say we take some node, then just try to calculate it, DP'ing through the neighbors. An obvious problem is that loops can form. If A explores B and B explores A, neither knows whether the best path goes through the other. There might be a way to work around this.

Another way is to consider path lengths in increasing order. Ie, first find the minimum cost to reach each node from s in at most 0 steps (infinity everywhere), then in 1 step, then in 2 steps, etc. The maximum number of steps to reach any node is |V|-1. At each step, we look at all edges in the graph, and if one side is less than the other side + cost, we update it. So O(|V||E|) time.

The algorithm can be enhanced to check for negative cycles by running another |V|'th cycle and seeing if that causes any weights to decrease even further, which should be impossible.

The "original" DP problem was actually the "dynamic decision problem", which is really similar to the multi-armed bandit problem (we will analyze it without any probabilities). Formally, we have a graph with edge weights, and a "discount factor". What edges should we travel on to maximize our reward (off to infinity, guaranteed to be finite if discount < 1)

Similar to "Markov Decision Process"

Behavior is very dependent on the discount factor. With a small discount factor (close to zero), we prefer short-term payoffs.

DP solution: OPT can be defined using a sum across all the outgoing edges. The definition is pretty simple. It's problematic because we want to go out to infinity and have to handle loops, so there's not really any "base" of the DP recursion.

So we do something that's not exactly true DP. Rather, we do it just like the single source shortest path with negative weights: Iteratively update DP result at each node using results from the last step until convergence. In SSSP, we have some guarantee of convergence after a known number of steps (|V|-1).

At the t-th step, each node stores the highest reward that can be reached in t steps ending at that node.

Estimating: If \(\varepsilon_t=\max_u trueResult(u)-calculatedResult_t(u)\), then \(\varepsilon_{t+1}\le\gamma\varepsilon_t\). TODO: show

Time complexity: O(mT) where m is number of edges and T is the number of iterations. If we want result to within delta, then we need \(T=\log_\gamma (\varepsilon_0/\delta))\).

Brute force is n! over all orderings of cities. (assume you can take a straight path between any two cities, i.e., graph is complete)

With DP, subproblem is best path going through all of S and ending at vertex v. At each level (including the top level, which has an "undefined" ending vertex), loop through each vertex, setting it as the ending vertex for a subproblem with \(S\setminus\{v\}\). TODO: how exactly?

Given a directed graph, an s source vertex, a t target vertex, and a numeric "maximum capacity" of each edge, assign a "flow" to each edge such that the total flow from s to t is maximized. Flow must satisfy:

• Conservation: Flow in to a vertex is equal to flow out, except for s and t.
• Within capacity: Flow on an edge is nonnegative and less than or equal to the edge's capacity.

Basic application example: Given a rail network, with max capacity on each line between cities, what's the maximum achievable thoroughput between two given cities? And how many trains should you send on which routes to achieve that maximum thoroughput?

TODO

Ford Fulkerson has pseudo polynomial time; at every iteration, the solution strictly increases, and cannot exceed the optimal solution. Further, each run takes O(m) time.

For problems A and B, we say \(A\le_P B\) if A can be polynomially reduced to B: A can be solved using a polynomial number of calls to B, plus a polynomial amount of extra work. We say \(A\le_P^1 B\) if A is solved with a single call to B. Maybe \(\le_P^{O(1)}\) is what we really want.

For example, bipartite matching is \(\le_P^1\) maxflow.

Any polynomial time algorithm is \(\le_P\) any other polynomial time algorithm; you can just ignore the other, and do your algorithm using the extra work available to you.

A modern field called "Fine-grained complexity" studies differences between polynomial time algorithms. But in this course, we don't care.

More interesting examples relate non-polynomial algorithms. Eg, independent set: Is there a k-sized subset of a graph such that no two vertices are connected? Vs Clique: Is there a k-sized subset which is complete (all pairs connected)? Simple: To find independent, find complement of edges (takes |V|² time), then solve clique. So independent \(\le_P^1\) clique.

Another more interesting example: Determining existance of a vertex cover of size at most k, compared to determining the size of an independent set. Lemma: The complement of an independent set is a vertex cover and vice versa. Every vertex in an independent set connects to a vertex outside that independent set, so the complement is a cover. Further, the complement of any vertex cover is independent: If there is an edge inside the complement, then it would not be in the vertex cover, contradicting that it's a vertex cover.

Easier to define for yes/no "decision problems". Let X be the set of inputs for which the problem answer is "yes". A problem is in NP if we can create a polynomial-time certification algorithm C(x,t) such that the following are equivalent:

• \(x\in X\)
• There exists a certificate t such that \(C(x,t)=yes\).

Example: Maxflow. Of course, maxflow is polynomial, so we can verify it trivially…but there is a constant time way to check as well: Give the cut and the flow, then just check they are equal. We know this happens only for the maxflow.

The "certifier" for a polynomial decision algorithm can be trivial: Just ignore the certificate, run the algo, and check that the answer is equal to x.

There's a more interesting way to think about this "trivial" certifier. Instead, we can think of the certificate being the algorithm itself. Ie, the certifier is being told "Here's the solution. And as a certificate of correctness, I provide you this algorithm which will return the same result and which you can run in polynomial time."

A is NP-hard if \(\forall B\in NP,\ B\le_P A\). Further, A is NP-complete if A is NP-hard and also in NP.

How do you prove something is NP-complete? First, you need a more formal model of computation in order to formally define polynomial time. Perhaps the easiest problem to show NP-completeness for is 3-Sat. If a problem can be solved in polynomial time on a Turing machine, it can be solved using a boolean circuit with a polynomial number of gates. We can turn those gates and the relationship between them into a boolean expression with no more than 3 elements per clause!

Thus, we take the polynomial time verifier/certifier, convert it into a 3-sat style expression, then run 3-sat on it to find an input which satisfies the verifier.

Some NP-complete problems which might show up on the exam:

• 3-Sat
• Subset Sum: Is there a subset with a given sum? (equivalent to a fixed sum, say 1)
• Is a graph 3-colorable?
• Independent Set (finding a set of vertices of a given size such that no two vertices in the set share an edge)
• Vertex Cover (set of vertices of a given size such that all edges in the graph touch one of the vertices)
• Clique (set of vertices of a given size such that every pair in the clique has an edge)
• Set cover/packing (given list of subsets, find a set of k subsets that covers the entire set)