The problems discussed in this course are almost without exception optimization problems: we do not only want to find a valid solution, but every valid solution also has an associated measure of how good a solution it is, and we want to find the best solution. You have seen such problems in before: The shortest path problem does not only ask to find a path between two vertices in a graph, but a shortest path. The minimum spanning tree problem does not look for just any spanning tree, but for a spanning tree of minimum weight. The list of such problems is endless.

It turns out that many optimization problems can be expressed as assigning values to variables such that certain linear combinations of these variables have values in a given range, and even the objective function to be maximized or minimized is a linear combination of the variables. An optimization problem of this type is called a linear program. We use linear programs as the primary language to express optimization problems in this course. This approach proves fruitful because LP duality and complementary slackness, discussed later in the course, are key tools for developing efficient algorithms for problems expressed as linear programs.

In this topic, we use the single-source shortest paths problem to illustrate how classical combinatorial optimization problems can be expressed as linear programs.

Dijksta’s algorithm for solving the single-source shortest paths problem and Prim’s algorithm for computing a minimum spanning tree of a graph are virtually identical: the only difference is the assignment of priorities of vertices currently in the priority queue. When looking at these two problems through the lens of linear programming though, the MST problem seems to be much harder than SSSP though. While an LP formulation of SSSP, discussed in the previous topic, is fairly easy, there does not seem to be a natural way to express the MST problem as an LP. We use this as an opportunity to introduce integer linear programs, which are simply linear programs with the added constraint that all variables must be given integer values. MST and many other combinatorial optimization problems have fairly straightforward formulations as integer linear programs.

Integer linear programs are a very expressive tool for formulating combinatorial optimization problems, too expressive perhaps. It is easy to formulate a wide range of NP-hard problems as ILPs. The consequence is that even deciding whether an ILP has a feasible solution at all is NP-hard. In this topic, we prove this, by giving a straightforward reduction from 3-SAT to ILP.

Given that linear programs can be solved in polynomial time but integer linear programming is NP-hard, a natural question is whether we can convert ILPs into LPs whose solutions tell us something about what a maybe not optimal but very good solution of the ILP might look like. A relaxation of an ILP is an LP that has the same constraints and objective function as the ILP, but it does not require that the variables be given integer values. This topic will introduce the most important terminology and concepts for comparing solutions to ILPs and solutions to their relaxations. These tools will be used extensively in our discussion of approximation algorithms later in the course.

Algorithms for solving linear programs often expect them to be in a particular form. For example, the Simplex Algorithm, discussed in the next topic, requires that all constraints in the LP be equality constraints. A linear program that satisfies this condition is said to be in standard form. Another special form of linear programs is canonical form, which requires all constraints to be upper bound constraints, the objective to be to maximize the objective function. Canonical form is at the heart of LP duality and complementary slackness, both discussed later in the course, which in turn are the key for developing really elegant and efficient combinatorial algorithms for advanced optimization problems. This topic shows that every LP can be converted into an equivalent LP in canonical or standard form. This implies that LP duality can be applied to any problem we would like to solve, as can the Simplex Algorithm, as long as the problem can be expressed as an LP at all.

The Simplex Algorithm is one of the oldest algorithms for solving linear programs. In theory, it is not a polynomial-time algorithm. Other algorithms, not discussed in this course, solve linear programs in polynomial time. In practice though, the Simplex Algorithm remains one of the fastest and most widely used algorithms for solving linear programs. While our main focus in this course is on using linear programs simply as a language to express combinatorial optimization problems, and on using the insights gained from the LP formulations of these problems to develop purely combinatorial algorithms for these problems, a discussion of linear programming would not be complete without showing you at least one, fairly natural algorithm for solving linear programs. This topic develops the Simplex Algorithm, analyzes its worst-case running time, and illustrates the algorithm using an extended example.

Linear programs come in pairs. For every LP, called the primal LP in this context, there exists another LP that can be obtained from it via a purely mechanical transformation. This other LP is called the dual LP of the primal LP. The primal and dual together have a number of really interesting properties. First of all, the dual of the duel is just the primal, that is, applying the transformation that constructs the dual of an LP twice, we simply get the original LP back. Most importantly for this course, we will show that the optimal solution of the primal and the optimal solution of the dual always have the same objective function value. This will be at the heart of a number of techniques for developing efficient algorithms for various optimization problems.

LP duality in itself is useful, but its usefulness is enhanced greatly through the use of complementary slackness. Given a feasible solution of the primal and a feasible solution of the dual, complementary slackness provides easily tested conditions for these two solutions to be optimal solutions of their respective LPs, without having to directly compute or compare their objective function values. As we will see, this is at the heart of one of the most beautiful techniques for solving optimization problems, called the primal-dual schema. If you forget everything else in this course, the primal-dual schema is a gem you must remember. It will play a central role in network flow algorithms, matching algorithms, and some of the approximation algorithms we will discuss.

In the maximum flow problem, we are given a directed graph, two vertices \(s\) and \(t\), and edge capacities. Our goal is to send as much flow (water, goods, information, …) from \(s\) to \(t\) without exceeding the edge capacities. This is a problem that every computers scientist should understand, as there are many problems that on the surface do not look life flow problems at all but can be formulated as flow problems with a little creativity. Given efficient algorithms for network flows, we can solve all of those problems efficiently. This topic gives an introduction to the maximum flow problem and formulates at as a linear program. The next topics discuss different types of algorithms that can be solve the maximum flow problem.

The first type of maximum flow algorithm is the augmenting path algorithm. All augmenting path algorithms are variants of the Ford-Fulkerson algorithm. The idea is to find a path from \(s\) to \(t\) along which we can still move flow from \(s\) to \(t\), and then we move as much flow as we can along this path. We do this until this is no longer possible.

To prove that this algorithm produces a maximum flow (and to prove that any maximum flow algorithm produces a maximum flow), we use the Max-Flow Min-Cut Theorem. It states that the maximum amount of flow one can move from \(s\) to \(t\) equals the capacity of a minimum \(st\)-cut. We will define what an \(st\)-cut is, and we will prove the Max-Flow Min-Cut Theorem in this topic. While we will give a purely graph-theoretic proof of this theorem, it is actually LP duality in disguise. The lecture notes for this topic include a proof of the Max-Flow Min-Cut Theorem via LP duality.

A weakness of the Ford-Fulkerson algorithm is that it may not terminate if it chooses the augmenting path in each iteration poorly. What is worse, even if we decide to simply terminate the algorithm and take the flow it has found so far as an approximation of the maximum flow, it turns out that this flow it has found can be only a tiny fraction of the maximum flow. We will give an example that illustrates this in this topic.

In the next topic, we will discuss a very simple adjustment of the strategy Ford-Fulkerson uses to find the paths along which it moves flow from \(s\) to \(t\) that guarantees that Ford-Fulkerson terminates, in polynomial time.

The Edmonds-Karp algorithm is the same as the Ford-Fulkerson algorithm, with one minor adjustment: Flow is moved along a shortest path in the residual network (a concept central to all flow algorithms and one introduced during the discussion of the Ford-Fulkerson algorithm) in each iteration. We will prove that this guarantees that the algorithm terminates after at most \(nm\) iterations. Since each iteration takes \(O(m)\) time, this gives us an algorithm with running time \(O(nm^2)\).

Push-relabel algorithms represent a different approach to solving maximum flow problems. Whereas augmenting path algorithms have the property that the flow is feasible at all times, this is not the case for push-relabel algorithms. The idea of these algorithms is to greedily push as much flow from \(s\) to its neighbours as possible without exceeding the edge capacities. The neighbours push this flow along to their neighbours, and so on. At some point, a portion of this flow reaches \(t\), while the remainder of the flow cannot be moved all the way to \(t\). This remainder is moved back to \(s\), at which point we obtain a feasible flow, and we will prove that if we orchestrate this strategy right, we will have a maximum flow at this point.

The basic version of this algorithm, discussed here, is a little faster than the Edmonds-Karp algorithm. It runs in \(O(n^2m)\) time. This running time can also be achieved by a further adjustment of Ford-Fulkerson, called Dinitz’s algorithm. However, further improvements on the basic strategy of push-relabel algorithms lead to significantly faster running times that seem impossible to match with augmenting path algorithms. Both Dinitz’s algorithm and these improved variants of push-relabel algorithms are discussed in the lecture notes but will not be covered in class.

Push-relabel algorithms are interesting for another reason: they are the first primal-dual algorithm we discuss in class. We will not explore this formally, just as we did not discuss formally that the Max-Flow Min-Cut Theorem is just LP duality in disguise. However, it can be shown that the height function maintained by push-relabel algorithms really encodes an \(st\)-cut in the network. The basic idea of primal-dual algorithms is to maintain a pair of solutions, a solution of the primal LP and a solution of the dual LP. Usually, as here, the primal solution (our flow here) will not be feasible initially, while the dual solution (our height function here) is. Both solutions satisfy complementary slackness at all times. The algorithm then improves the dual solution and moves the primal solution closer and closer to feasibility. Once the algorithm terminates, we have two feasible solutions that satisfy complementary slackness, so they must be optimal solutions. Here, this means that we have found a maximum flow.

Matchings are another tool in our arsenal that can be used to express a range of problems that on the surface do not look like matching problems at all. Given a graph \(G = (V, E)\), a matching is a subset \(M \subseteq E\) such that no two edges in \(M\) share an endpoint. One can now impose many conditions for considering one matching better than another one, and many of these conditions capture important practical problems. Here, we focus on two particular optimality criteria. First, we aim to find a matching that is as big as possible: our goal is to maximize \(|M|\). This is the maximum matching problem. This can be generalized by assigning weights to the edges and trying to find a matching of maximum weight. This is the maximum-weight matching problem. A perfect matching \(M\) has the property that every vertex in \(G\) has an incident edge in \(M\). Such a matching may not always exist. If it exists though, we may be interested in finding such a matching that is as “cheap” as possible with respect to our edge weights. This is the minimum-weight perfect matching problem. In this topic, we will introduce these different matching problems. In the next three topics, we will discuss algorithms to solve them.

It turns out that all matching problems are significantly easier to solve if the input graph is bipartite. Depending on how you look at it, this may be a good thing, because most natural matching problems that arise in real-world applications involve pairing entities in one group with entities in another group, that is, the graphs involved are naturally bipartite. We use bipartite graphs to introduce the basic ideas necessary to develop fast matching algorithms. All of these ideas can be extended, sometimes with significant effort, to be applicable also to non-bipartite graphs. We will discuss this only for the maximum matching problem in a later topic.

In this topic, we show how to find a maximum matching in a bipartite graph. In the process, we will introduce the concept of an augmenting path (not to be confused with augmenting paths for flows; they have the same name, because both types of paths are used to augment the current solution, but are different) which is at the heart of virtually every matching algorithm.

The next problem we study is the minimum-weight perfect matching problem. The algorithm we use to solve it, the Hungarian algorithm, is probably one of the most beautiful applications of the complementary slackness and the primal-dual schema. Therefore, while it is possible to prove the correctness of this algorithm using purely combinatorial arguments in just a few lines, we will spent some time deriving this result directly via complementary slackness, and we will use this algorithm to crystallize the general form of any algorithm based on the primal-dual schema.

Once we have an algorithm to solve the minimum-weight perfect matching problem, we get an algorithm for the maximum weight matching problem for free: We will discuss how to reduce the maximum weight matching problem to the minimum-weight perfect matching problem.

The final problem in this class that can be solved in polynomial time is finding a maximum matching in arbitrary, not necessarily bipartite graphs. The algorithm we discuss for this problem, Edmonds’s algorithm, uses the same basic strategy as the algorithm for bipartite graphs: start with an arbitrary matching (the empty matching or a maximal matching is fine) and then find augmenting paths to make the matching bigger and bigger. What’s harder for non-bipartite graphs is finding these augmenting paths. We will discuss how to do this.

The remainder of the class is focused on solving NP-hard problems. This introductory topic outlines the strategies we have at our disposal to do this. The first is to insist on polynomial-time algorithms and to settle for not necessarily optimal solutions. This is what many heuristics do in practice. They may not even insist that the algorithm runs in polynomial time, only that it is really fast in practice. Since this is a theory course, we will insist on algorithms we can actually prove something about, so we will not explore heuristics. (Polynomial-time) approximation algorithms are algorithms that provably run in polynomial time and produce solutions for which we can prove that they are at most a certain factor away from an optimal solution.

The second approach is to accept that it takes exponential time to find a solution. In the same way that a linear-time algorithm is better than an \(O(n^3)\)-time algorithm though, an \(O(1.1^n)\)-time algorithm is better than an \(O(3^n)\)-time or \(O(n!)\)-time algorithm, and the difference is exponentially bigger. Thus, the goal is to develop exponential-time algorithms that are as fast as possible. Combined with heuristics that preserve the correctness of the algorithms, some of these algorithms can be blindingly fast in practice.

A third approach is a variant of the second approach, and it is the one closest to my heart. Using the input size as a measure how long we should expect it will take to solve a problem on a given input proved useful for developing a complexity theory of computational problems, but especially in the light of many problems we absolutely need to solve being NP-hard or worse, it turned out to be a rather crude measure. There are large inputs on which the problem of interest may be easy to solve, and some much smaller inputs turn out to be much harder nuts to crack. It is often the structure of the input rather than its size that determines whether a problem is hard or easy to solve on such an input. Parameterized algorithms associate hardness parameters with the input. The goal is to find algorithms whose running times depend exponentially on this hardness parameter but only polynomially on the input size, and we once again want this exponential dependence on the parameter to be as small as possible. We will discuss parameterized algorithms and exponential-time algorithms together, as there is significant overlap between the techniques used to develop these algorithms.

The next three topics give you a flavour of each of the three techniques we use to attack NP-hard approximation problems. We will use the vertex cover problem for all of these examples, as it is a problem that is simple enough to understand and solve. In this problem, we are given a graph \(G = (V, E)\), and our goal is to find a set \(C \subseteq V\) of minimum size such that every edge of \(G\) has at least one endpoint in \(C\). This set \(C\) is called a vertex cover of \(G\). As we will see, vertex cover is a special case of the more general set cover problem, which we will use as the introductory example to illustrate most techniques for developing approximation algorithms. Similarly, vertex cover will be the familiar ground we will return to every time we need to illustrate a new technique for developing exponential-time and parameterized algorithms. In this topic, we will see how to easily obtain a 2-approximation of an optimal vertex cover in linear time. This means that we compute a vertex cover \(C\) (every edge has at least one endpoint in \(C\)) that is at most twice as big as the smallest such set for the given input graph.

Developing an exponential-time algorithm that finds the smallest possible vertex cover for a graph in \(O(2^nm)\) time is easy: just try every subset of vertices, check for each whether it is a vertex cover, and remember the smallest set we have seen. In this topic, we will discuss a different approach to achieve this running time for the vertex cover problem. While the try-every-subset-of-vertices approach is hard to tweak to make it faster, the approach we discuss in this topic will be the foundation for the parameterized algorithm we discuss in the next topic, and for faster exponential-time and parameterized algorithms discussed later in this class. This technique, called branching, is rather important for developing efficient algorithms for many NP-hard problems. The basic idea is to identify “elementary decisions” to be made while constructing a solution. By repeatedly making the correct choice, we will obtain an optimal solution. Given that the problem is NP-hard though, we do not know how to locally make the best choice. Thus, we try each choice in turn and recurse on the subproblem we obtain after making each choice. To obtain the fastest possible algorithm for a given problem, it is crucial to set up these elementary decisions so that the number of options we can choose from is small and/or each choice we make leads to a subproblem that is substantially smaller than the current problem or whose parameter is substantially smaller than the parameter for the current problem. We will explore later how to design branching rules that achieve this goal and lead to fast algorithms for NP-hard optimization problems.

This topic gives you a glimpse of how to develop parameterized algorithms. This introductory topic will build on the branching algorithm from the previous topic. Now, however, our focus is on ensuring not only that the input size decreases in each recursive call but that the parameter decreases in each recursive call. This limits the recursion depth to our parameter \(k\) instead of the input size \(n\) and immediately leads to an \(O(2^km)\)-time algorithm for the vertex cover problem. This approach of limiting the search depth of branching algorithms by some function of the parameter is called, quite naturally, depth-bounded search. It is one of the most elementary techniques for designing parameterized algorithms, but it is also the one that is most effective for designing practically efficient parameterized algorithms.

After the previous overview topics on how to approach NP-hard problems, the next topics will delve a little deeper into developing approximation algorithms. You hopefully remember greedy algorithms from CSCI 3110 (or an equivalent course if you’re a grad student who didn’t do his undergrad at Dal). The basic principle of these algorithms, as studied in CSCI 3110, is that they can be used to find optimal solutions quickly if the problem we are trying to solve can be solved by making locally optimal choices without regard for how these choices may affect future decisions. NP-hard problems do not have this property, but we may still be able to prove that making greedy, locally optimal choices gives us at least a solution that is not too far from an optimal solution. Whenever this is the case, we often obtain really fast approximation algorithms because making local choices greedily is fast. In this topic, we illustrate this approach using the bin packing problem as an example. Specifically, we will develop a simple 2-approximation algorithm for this problem.

The set cover problem will be our familiar friend that we will use to illustrate almost all techniques for developing approximation algorithms discussed in this course. In this problem, we are given a set \(U\), called the universe, and a collection \(\mathcal{S}\) of subsets of \(U\). Each set in \(\mathcal{S}\) has a positive weight. Our goal is to cover all of \(U\) with sets in \(\mathcal{S}\) as cheaply as possible, that is, we want to find a subset \(\mathcal{C} \subseteq \mathcal{S}\) such that the sets in \(\mathcal{C}\) have minimum weight and the union of these sets is \(U\). In this topic, we will see that a fairly simple greedy choice allows us to obtain an \(O(\lg n)\)-approximation algorithm for this problem, where \(n = |U|\). The analysis will be fairly involved. Later, we will discuss dual fitting as technique not for designing but for analyzing approximation algorithms. Using this technique will simplify the analysis of this set cover algorithm significantly, and it will even allow us prove a slightly better approximation guarantee of \(O(\lg k)\), where \(k\) is the size of the largest set in \(\mathcal{S}\), which may be significantly smaller than \(n\).

Parametric pruning is a beautiful technique that unfortunately doesn’t seem to have a particular wide range of applications. Still, the idea is beautiful, so we will illustrate it using one example here. The basic idea is a little difficult to explain succinctly enough for this brief synopsis of this topic, but I’ll try to give an intuitive (albeit quite imprecise) description here anyway. For some problems, we can find an optimal solution by throwing away exactly those parts of the input that are not part of the optimal solution. Now, we cannot hope to identify these parts precisely, but we can often obtain a reasonable lower bound on the cost of an optimal solution, and it may be possible to obtain an upper bound on this cost from the lower bound; we know a range of values within which the optimal solution must lie. We then throw away all parts of the input that are guaranteed not to be part of a solution whose cost is at most our upper bound. This is the “pruning” part. Now we may be able to compute an almost arbitrary solution in this pruned instance and be able to guarantee that this arbitrary solution has a cost that is at most some factor away from our lower bound and, therefore, also at most the same factor away from the optimal solution, so we obtain a good approximation of an optimal solution. In this topic, we illustrate this technique by obtaining a 2-approximation for the metric \(k\)-center problem, and a 3-approximation for the weighted version of this problem.

Dual fitting is based directly on the fact that, due to weak LP duality, any feasible solution of the dual of the LP relaxation of an ILP provides a lower bound on the objective function value of the solution of the ILP. We can exploit this to prove that some algorithms achieve a good approximation guarantee. In particular, dual fitting is not an algorithm design technique but purely an analysis technique to prove approximation guarantees of algorithms. Given the solution computed by some algorithm, we construct a feasible dual solution based on how the algorithm arrived at the primal solution, and we prove that the cost of this dual solution is not too far away from the cost of the primal solution the algorithm has computed. The optimal solution must be sandwiched somewhere between these two solutions, so we obtain a guarantee of how far the computed solution is from an optimal solution. In this topic, we revisit the greedy set cover algorithm and use dual fitting to obtain a slightly better bound on its approximation ratio than before, and much more easily.

Remember the primal-dual schema: it maintains an initially infeasible primal solution and a feasible dual solution. It moves the primal solution closer and closer to feasibility and updates the dual so that it remains feasible and the primal and dual satisfy complementary slackness at all times. Thus, once the primal solution becomes feasible, it must be an optimal primal solution.

The same strategy can be employed to develop approximation algorithms, only we ensure that the two solutions satisfy only some relaxed version of complementary slackness. Depending on how much we relax the complementary slackness conditions (as little as possible), we will then be able to prove that once both the primal and dual solutions have objective function values not too far from each other. The optimal solution must once again be sandwiched between these two solutions, so the gap between the primal and dual solutions immediately becomes a bound on the approximation ratio of the algorithm.

In this topic, we introduce relaxed complementary slackness and the general primal-dual framework for obtaining approximation algorithms based on it. The next two topics show this technique in action using the set cover problem and metric facility location as examples.

This section applies the primal-dual schema to obtain an \(f\)-approximation of the primal-dual schema, where \(f\) is the maximum number of sets in \(\mathcal{S}\) that any element in the universe \(U\) belongs to. In the set cover formulation of the vertex cover problem, we have \(f = 2\), so this gives another 2-approximation algorithm for the vertex cover problem, but one that is more general than the one we discussed earlier. Our earlier vertex cover algorithm computed a vertex cover of at most twice the optimal size. The primal-dual algorithm in this section allows us to assign weights to the vertices and then find a vertex cover of at most twice the optimal weight.

In all the algorithms we have developed so far, we used (I)LPs and LP duality only to guide the development of the algorithm and its analysis. Our next topic is deviates from this in that it directly uses a polynomial-time LP solver to obtain a solution of the LP relaxation of the ILP, and then it uses the computed fractional solution to guide the search for a good integral solution. In a nutshell, the idea goes as follows: We know that the computed optimal fractional solution of the LP relaxation is no worse than the optimal integral solution of the ILP, but it is not a feasible solution of the ILP because it may not assign integer values to the variables. Now we want to round the variable values in the fractional solution so that the resulting integral solution is feasible and the objective function value does not increase too much in the rounding process. This guarantees that we obtain an integral solution that is at most some factor away from the optimal fractional solution and, therefore, it as also at most the same factor away from the optimal integral solution. This topic introduces the general framework of LP rounding. The next 6 topics discuss different approaches to rounding.

The simplest approach to LP rounding is half-integrality, but it is applicable only to problems with a particularly favourable structure. Specifically, for some problems, we can prove that every optimal fractional solution assigns values to all variables that are multiples of \(\frac12\). For others, it may not be the case that every fractional solution has this property, but there does at least exist such an optimal solution and we can find it efficiently. Given such a half-integral optimal solution, we can now round every variable value up to the closest integer. This at most doubles the objective function value, maintains feasibility, and produces an integral solution. Thus, we immediately obtain a 2-approximation of an optimal integral solution. In this topic, we illustrate this technique for the vertex cover problem. The vertex cover problem is one of those problems where at least every optimal fractional solution found by the Simplex Algorithm is half-integral.

In the multiway cut problem, we are given an vertex-weighted graph \(G\) set \(T\) of vertices of \(G\), and we want to find a vertex set of minimum weight such that cutting these edges separates all vertices in \(T\) from each other. In other words, every path between two vertices in \(T\) must contain at least one vertex in the chosen set. This problem has optimal fractional solutions that are not half-integral, but any such solution can always be rounded to produce a half-integral solution of at most the same objective function value. By rounding this solution further to make it integral, we obtain a 2-approximation of an optimal integral solution.

For problems whose LP relaxations do not have half-integral optimal solutions, rounding becomes much harder. A highly effective strategy is to round variable values up or down at random. If we do this often enough, we are bound to find a decent solution eventually. This is discussed in the next topic. Since I suspect you have not had much exposure to randomized algorithms in general, this topic briefly reviews the main ideas of how to incorporate random choices into algorithms and how to bound the probability that the resulting algorithm finds a good solution and/or that it does so quickly.

Given a fractional solution of the LP relaxation of an ILP, we can view the fractional parts of the variable values in this solution as probabilities to round up or down. Doing this once is highly unlikely to produce a feasible integral solution in a sense we will discuss in this topic. However, rounding multiple times and taking the union of the resulting integral solutions produces a feasible solution with sufficiently high probability, and the solution as not too far from an optimal integral solution, also with sufficiently high probability. By repeating this process until we can guarantee that the solution we obtained represents a good enough approximation of an optimal solution, we obtain a Las Vegas approximation algorithm, that is, one that guarantees the approximation ratio of the solution it produces but that runs in polynomial time only with high probability. We use the set cover problem as the introductory example to illustrate this technique.

MAX-SAT is a natural extension of the satisfiability problem (SAT). In SAT, we are given a Boolean formula and want to find a solution that satisfies this formula. This is probably the most well-known NP-hard problem. Often, different parts of the formula satisfy constraints that a solution must satisfy. Whenever such formulas are constructed to model real-world constraints, it is common that we obtain an over-constrained problem, one that does not have a solution that satisfies all of these constraints. The MAX-SAT problem is the optimization version of SAT, which asks us to find a solution that satisfies as many constraints as possible.

There exist two simple randomized algorithms for this problem, one with approximation ratio \(\frac12\) and one, based on randomized rounding, with approximation ratio \(1 - \frac1e\). Each algorithm shines and achieves a significantly better approximation ratio than these worst-case bounds for certain types of input formulas. We will prove that by choosing one of these two algorithms at random, we have a decent probability that the computed solution is at least a \(\frac34\)-approximation for any input, that is, the random mixture of the two algorithms is strictly better than each algorithm individually. In this topic, we explore these two algorithms and their random mixture.

Randomized algorithms are often much simpler than equally good deterministic algorithms. There even exist problems for which randomized solutions achieve provably better approximation guarantees or provably better running times than what is achievable using deterministic algorithms. Thus, a question that has been studied extensively is when and how we can convert randomized algorithms into equally good deterministic ones. This topic explores one of these techniques, the technique of conditional expectations. We apply this technique to the randomized MAX-SAT algorithm from the previous topic to obtain a deterministic algorithm that is guaranteed to produce a \(\frac34\)-approximation of an optimal solution.

For the remainder of this course, we return to focusing on computing optimal solutions to optimization problems, not just approximations. As discussed before, if the problem is NP-hard, we can do this only if the running time of the algorithm depends exponentially on the input size or on some parameter of the input that must be polynomial in the input size in the worst case but may be, and hopefully is in many instances, much smaller than the input size. Our first topic in this final part of the course is focused on a general technique for designing parameterized algorithms for NP-hard problems.

The hard core of almost every NP-hard problem can be phrased as a decision problem: For example, instead of asking for a vertex cover of minimum size in a graph \(G\), we can ask whether \(G\) has a vertex cover of size at most \(k\), where \(k\) is given as part of the input. It is not hard to see that we can find an optimal vertex cover by solving the decision problem for increasing values of \(k\) until we obtain our first positive answer. This increases the running time of the algorithm by at most a linear factor. In reality, it actually increases the running time by only a constant factor, as we will discuss.

Given such a decision problem then, our goal in this topic is to design an algorithm that takes an instance \((I, k)\) of this decision problem and constructs from it an instance \((I', k')\) such that \((I, k\)) is a yes-instance if and only if \((I', k')\) is, the size of \(I'\) is a function of only \(k\) and in particular is independent of the size of \(I\), and the construction of \((I', k')\) from \((I, k)\) takes only polynomial time. In this case, we call \((I', k')\) the kernel of \((I, k)\). To decide whether \((I, k)\) is a yes-instance then, we only need to decide whether \((I', k')\) is a yes-instance and, given that \(|I'| \le f(k)\), for some function \(f\), the latter takes \(g(k)\) time, for some function \(g\). Combined with the polynomial time to construct \((I', k')\) from \((I, k)\), we obtain a parameterized algorithm for our problem.

In this topic, we introduce the concept of kernelization and prove that it is of vital importance for the theory of parameterized algorithms in the sense that a problem has a parameterized algorithm if and only if it has a kernelization. Prepare to be underwhelmed though; the part of the proof that shows that if a problem has a parameterized algorithm, it also has a kernelization, does not provide any insights into how to actually find small kernels. It will feel a bit like cheating.

If we want to use kernelization as a tool for designing parameterized algorithms, we need efficient methods for constructing kernels. The next few topics take us on a tour of the most important techniques for constructing kernels. By far the most important one is reduction rules. These rules allow us to construct smaller inputs from bigger ones, in polynomial time, and with the guarantee that the original input is a yes-instance if and only if the constructed input is a yes-instance. These are the same conditions as for a kernelization, only the condition that the reduced instance should have a size bounded by some function of the parameter is replaced by the weaker condition that the reduced instance should simply be smaller than the input instance. In addition reduction rules come with conditions under which they are applicable.

A kernelization procedure based on reduction rules applies these reduction rules until the input does not satisfy the conditions for any of these rules to be applicable. We call the resulting input fully reduced. If we design the reduction rules correctly, then we will be able to prove that a fully reduced instance has a size that is a function of the parameter and is therefore independent of the size of the instance we started with. Thus, we have a kernelization procedure. In this topic, we illustrate this idea by discussing reduction rules that allow us to find a kernel of the vertex cover problem with at most \(k^2\) edges and at most \(k^2 + k\) vertices, where \(k\) is the size of the vertex cover.

The next technique for designing reduction rules is crown reduction. A crown is a subgraph of a given graph with a particular structure. We will show that a crown can be found in polynomial time and that we can develop a reduction rule based on the found crown that guarantees that for the vertex cover problem, the reduced instance has at most \(3k\) vertices.

The final kernelization technique we discuss in this course is based on solving an LP relaxation of the problem we want to solve. We already discussed that the vertex cover problem has the property that every optimal (extreme point) solution of it assigns values in \(\{0, \frac12, 1\}\) ta all variables. It turns out that the vertices whose corresponding variables have value \(\frac12\) form a kernel for the vertex cover problem. Since there can be at most \(2k\) such vertices if there exists a vertex cover of size \(k\), this gives a kernel for the vertex cover problem with only \(2k\) vertices.

Having used vertex cover as the example to introduce various kernelization techniques, this topic and the next applies these techniques to other problems. In this topic, we consider cluster editing. We are given a graph and we want to decide whether it is possible to add or remove at most \(k\) edges so that every connected component of the resulting graph is a clique. This is a natural formulation of the clustering problem, which is of great importance in machine learning and general data summarization tasks. In this topic, we discuss reduction rules that guarantee that a fully reduced instance has only \(O(k^2)\) vertices and \(O(k^3)\) edges.

I hope you remember the MAX-SAT problem, which we discussed as part of our discussion of LP rounding. Here, we consider the parameterized version of this problem, that is, we ask whether it is possible to satisfy at least \(k\) clauses in the formula. We will see that the answer is obviously yes if there are at least \(2k\) clauses in the formula. Thus, any interesting instance has at most \(2k\) clauses but may have a many variables. In this topic, we use crown reduction to reduce the number of variables to \(O(k)\) as well.

We already saw branching algorithms in the introduction to the different approaches we can use to solve NP-hard problems. The idea is to formulate the process of searching for a solution as a sequence of elementary choices (e.g., do I include this vertex in my vertex cover or not). If we can bound the number of such elementary choices to be made by some function of the input size or of the parameter, and we can bound the number of options to choose from in each step by some constant or at least by a function of the parameter, then we obtain a decent exponential-time or parameterized algorithm for the problem we are trying to solve. The next few topics explore both exponential-time and parameterized branching algorithms for a number of problems. In this topic, we introduce a general framework for analyzing the running times of branching algorithms that allows us to obtain bounds on their running times much more easily than solving recurrence relations from scratch for every single algorithm.

This topic revisits our depth-bounded search algorithm for the vertex cover problem from earlier and formally introduces the idea of depth-bounded search. The exponential-time branching algorithm from the previous topic can also be used with only minor modifications to find a maximum independent set. This raises the question of whether we can also use the depth-bounded version of this algorithm to obtain a parameterized algorithm for the maximum independent set problem. We will see that the answer is yes if the parameter is \(|V|\) minus the size of the independent set (essentially because every independent set is the complement of a vertex cover and vice versa) but that the answer is no if the parameters is the size of the independent set itself. We will explore briefly why this fails for this particular algorithm. We do no have time in this course in greater depth, but one can show that maximum independent set parameterized by the size of the independent set is W[1]-hard, which means that there does not exist a parameterized algorithm for this parameterization of maximum independent set.

In this topic, we revisit the cluster editing problem and develop a depth-bounded search algorithm for it with running time \(O(3^k \cdot m)\), where \(k\) is the number of edges we are allowed to add or remove.

Given a set of strings all of the same length, our goal in the closest string problem is to find a string \(\sigma\) such that every input string differs from \(\sigma\) in at most \(k\) characters. We develop a depth-bounded search algorithm for this problem with running time \(O((k + 1)^kn)\). This algorithm is interesting primarily because it is the only branching algorithm we discuss in this course where the number of options we choose from in each step is not bounded by a constant but by a (linear) function of the parameter instead.

All our branching algorithms so far had a single “branching rule”, that is, a single substructure in the input that we focused on to make a decision on what the computed solution should look like within this substructure. For the vertex cover problem, we focused on a single vertex and its neighbours, and we chose whether to include the vertex or all its neighbours in the vertex cover. For cluster editing, we focused on a triple of vertices with two of the three possible edges present in the graph, and we decided whether to add the missing edge or delete one of the two present edges.

In order to obtain faster algorithms, it often helps to perform fine-grained analyses that look for different substructures in the input and use a separate branching rule for each type of substructure. In this topic, we illustrate this for the vertex cover and independent set problems. Each rule still looks at a vertex and its neighbours, but it treats them differently based on the number of neighbours there are.

This topic focuses not so much on obtaining faster algorithms but on proving that the algorithm we already have is faster than a naive analysis suggests. Our goal is to improve the analysis of the algorithm rather than the algorithm itself. The analysis of the running time of an algorithm based on branching vectors and branching numbers uses the worst possible branching number of all the different branching rules and assumes that every recursive call of the algorithm runs into this worst case. Clearly, the algorithm cannot behave worse than that. It is possible though that the algorithm cannot possibly always encounter the worst case. Often after using the worst possible branching rule for a number of recursive calls, the next recursive call must be able to use one of the better branching rules or the branching rule that leads to the worst-case analysis must in fact behave better than in the worst case. The key to proving this is to consider the interaction between sequences of recursive calls or more generally, to consider a small constant-size subtree of the recursion tree and analyze the branching vector of this subtree instead of a single recursive call. We illustrate this technique using cluster editing as an example.

Dynamic programming should be another familiar friend from CSCI 3110. The development of a dynamic programming algorithm always starts with a recursive algorithm to solve a given problem. We the “memoize” this recursive algorithm, meaning that we store the results of all recursive calls in a lookup table. Whenever we encounter a recursive call on a subproblem we have considered before, then we do not compute the solution from scratch but use the solution already stored in the table. In the discussion in CSCI 3110, you should have learned that this is useful whenever the number of possible subproblems to be solved is polynomial in the input size, because this means that while the basic recursive algorithm often takes exponential time, solving the same subproblems over and over again, the dynamic programming algorithm solves each subproblem only once and thus takes polynomial time.

This requirement that there be only polynomially many subproblems to consider is necessary only if our goal is to obtain a polynomial-time algorithm. If we are happy with an exponential running time and our goal is to obtain the fastest exponential-time algorithm we can, then it suffices that the number of distinct subproblems the algorithm may encounter is less than the number of recursive calls the basic recursive algorithm would make. In this topic, we illustrate this using the travelling salesman problem as an example. The naive algorithm would take \(O(n!)\) time, whereas the dynamic programming algorithm we develop takes only \(O(2^n)\) time.

The Steiner tree problem is a generalization of both the minimum spanning tree problem and the shortest path problem. In the minimum spanning tree problem, we are looking for the cheapest possible subtree of an edge-weighted graph that connects all the vertices with each other. In the shortest path problem, we are looking for the cheapest possible subtree that connects two vertices with each other; obviously, this subtree is always a path in this case. In the Steiner tree problem, we are given an arbitrary subset of the vertices of the graph, and our goal is to find the cheapest possible subtree that connects these vertices with each other. This subtree may contain additional vertices if this allows us to connect the given vertices to each other using cheaper edges than the ones connecting them directly, but it doesn’t have to contain additional vertices.

It is not hard to see that the hard part of the Steiner tree problem is deciding which vertices to include in the Steiner tree. Given this set of vertices, the Steiner tree is simply a minimum spanning tree over these vertices. Thus, we can compute a Steiner tree in \(O(2^n \cdot \mathrm{poly}(n))\) time by trying every possible superset of the vertices we want to connect, computing a minimum spanning tree for this set of vertices, and reporting the cheapest tree we find.

In this topic, our goal is to obtain a parameterized algorithm for this problem, the parameter being the number of vertices we want to connect. We will use dynamic programming to obtain an algorithm with running time \(O(3^k \cdot \mathrm{poly}(n))\).

Whenever we use dynamic programming to solve an NP-hard problem, our dynamic programming table usually has exponential size. On today’s hardware, exponential space is arguably a much greater impediment to an efficient solution than exponential time. For some problems, inclusion-exclusion offers an elegant alternative to dynamic programming that allows us to solves these problems in exponential time but only polynomial space. Branching algorithms also use only polynomial space.

Inclusion-exclusion is a standard technique in combinatorics to count how many objects with a particular set of properties there are. It does so by counting for every subset of these properties how many objects there are that have this subset of properties and possibly but not necessarily additional properties. We can then write down the list of properties that define a solution to the problem we want to solve and use inclusion-exclusion to count how many objects there are that have all these properties. If there is at least one, then there exists a solution to our problem. If there is none, then, well, there is no solution. It turns out that we can implement inclusion-exclusion in only polynomial space, but it only tells us whether there exists a solution. If the problem we try to solve is self-reducible, then we can find a solution by applying inclusion-exclusion to prune the input instance and do so repeatedly until the pruned instance is the solution. In this topic, we lay the combinatorial foundations for this technique. The next two topics apply this technique to the Hamiltonian cycle problem and to graph colouring.

The Hamiltonian cycle problem is the little sibling of the Travelling salesman problem. In the latter, we are looking for a cycle that visits all vertices in the graph and has minimum length (with respect to given edge weights) among all such cycles. The Hamiltonian cycle problem only asks whether such a cycle exists at all. Since we can solve the travelling salesman problem in \(O(2^n \cdot \mathrm{poly}(n))\) time, we can do the same for the Hamiltonian cycle problem, but this solution involves dynamic programming and uses exponential space.

We can use inclusion-exclusion to achieve the same running time but using only polynomial space. This uses a number of reductions. First, the hard part of finding a Hamiltonian cycle is to find a path of length \(n - 1\) from some vertex \(v\) to any neighbour of \(v\). If we can count these paths, then we can decide whether a Hamiltonian cycle exists. Counting paths is hard though. Counting walks, which may visit vertices more than once, is much easier. So we count walks of length \(n - 1\), but not just any walks. We count walks of this length that avoid a certain subset of vertices, for every possible choice of this subset. Using inclusion-exclusion, we then obtain the number of walks of length \(n - 1\) that do not avoid any of the vertices in the graph. But this means that any such walk has length \(n - 1\) and visits all vertices in the graph. The only way this is possible is if the walk visits every vertex exactly once, that is, it is a path; we have found a sneaky way to count paths after all.

Graph colouring is one of the most iconic NP-hard problems. Given a graph, we want to find the smallest number of colours so that we can colour every vertex with one of these colours without giving the same colour to any two adjacent vertices. The decision version asks whether there exists such a colouring of the vertices of the graph with at most \(k\) colours.

Since no two adjacent vertices can have the same colour, an alternative formulation of this problem is that we want to partition the vertex set of the graph into \(k\) independent sets. So, we should try to count the number of such partitions of the vertices of into independent sets. Once again, this is hard. What’s much easier, using inclusion-exclusion again, is to count the number of tuples of \(k\) independent sets that cover a given subset of vertices but aren’t necessarily disjoint. If the subset we want to cover is the set of all vertices of the graph, then any such tuple can be turned into a colouring by removing every vertex that belongs to more than one of the independent sets from all but one of them. Thus, we have an algorithm that can decide whether a \(k\)-colouring of the graph exists. We will show that vertex colouring is self-reducible, so we can once again also find such a colouring if it exists.

Iterative compression is one of my favourite techniques for designing parameterized algorithms. It uses a really intuitive idea: If I give you an almost optimal solution to a given problem, this should somehow help me to guide the search for an optimal solution. Unfortunately, this intuition is wrong for many problems. When it is correct though, iterative compression can be used to solve the problem. We will illustrate this by showing how to obtain an \(O(2^k \cdot \mathrm{poly}(n))\)-time algorithm for vertex cover. We have already found faster branching algorithms for this problem. Our goal here is not to obtain an even faster algorithm but to illustrate this beautiful technique.

You may ask how we obtain this almost optimal solution though. By iteration. That’s the “iterative” part in this technique. This is best explained by using vertex cover as a concrete example. We construct a sequence of graphs \(\langle G = G_0, G_1, \ldots, G_{n-1}\rangle\) by removing the vertices of \(G\) one at a time. If \(G\) has a vertex cover of size at most \(k\), then so do all the graphs in this sequence. Such a vertex cover is easily found for \(G_{n-1}\): since \(G_{n-1}\) has no edges, the empty set is a vertex cover of \(G_{n-1}\). Now, given a vertex cover of \(G_i\) of size at most \(k\), we obtain a vertex cover of \(G_{i - 1}\) of size at most \(k + 1\) by adding the vertex removed to obtain \(G_i\) from \(G_{i - 1}\) to the vertex cover. This is the almost suboptimal vertex cover we need. The key then is to use this vertex cover to guide the search for a vertex cover of \(G_{i - 1}\) of size at most \(k\). We will see how to do this in \(O(2^k \cdot \mathrm{poly}(n))\) time.

Finding a shortest path is easy. Finding a longest path is hard. Specifically, the longest path problem asks us to find a path that visits as many vertices as possible. Clearly, a solution to this problem can be used to solve the Hamiltonian cycle problem, so this problem is NP-hard. The parameterized version asks whether there exists a path that visits \(k\) vertices.

The technique we use to solve this is colour coding, and it is the only technique in our discussion of parameterized algorithms that uses randomization. As it turns out, looking for a path of length \(k\) is quite hard but what is, surprisingly, much easier is to look for such a path with additional properties. Here, we start with a random assignment of \(k\) colours to the vertices of the graph. It is fine if adjacent vertices receive the same colour. Then we want to decide whether there exists a “colourful” path of length \(k\), that is, a path that visits exactly one vertex of each colour. This turns out to be much easier than finding an arbitrary path of length \(k\). The key observation is that if there exists a path of length \(k\), then it is a colourful path for any colouring that assigns distinct colours to the vertices on the path. Thus, if there exists a path of length \(k\), then if we repeat this process of randomly colouring the vertices and then looking for a colourful path often enough, we have a decent probability of finding such a colourful path. In particular, we obtain an algorithm with running time \(O(2^k \cdot \mathrm{poly}(n))\) that always answers no if there is no path of length \(k\), and finds such a path with probability at least \(e^{-k}\) if such a path exists.