Math 428/529: Discrete Optimization

As stated, our main goal in this course is to develop efficient algorithms for solving problems of practical and theoretical interest. Of course, there is no good reason to believe that an efficient algorithm should always exist. Therefore, it is important to be able to identify problems which are inherently difficult and prove that (or, at least, provide evidence that) no efficient algorithm exists.

However, before this, we need to discuss what we mean when we say that an algorithm is efficient. Typically, an algorithm is thought of as being efficient if the running time is bounded above by a polynomial in the size of the input (i.e. a function of the form \(n^k\) where \(n\) is the size of the input and \(k\) is a constant (not necessarily an integer) that does not depend on the input). In this sense, both InsertionSort and MergeSort are efficient because \(n^2\) is a polynomial function of \(n\) and \(n\log(n)=O(n^{1+\varepsilon})\) for any \(\varepsilon>0\text{.}\) The “try every ordering” algorithm described in the previous section is not efficient as it takes time \(\Omega(n!)\) in the worst case and there does not exist a constant \(k\) such that \(n!=O(n^k)\text{.}\) A problem is said to be polynomial-time solvable if there exists an algorithm that can solve it in polynomial time.

So far, we defined the notion of an Optimization Problems in Definition 1.1.1 but, otherwise, we have mostly been working with a non-rigorous and intuitive definition of the term “problem.” While we will continue to employ a loose definition of the word “problem” throughout these notes, it will be useful to distinguish certain types of problems from others. One important notion is that of a “decision problem.”

An instance of a decision problem is called a yes instance if the answer to the problem with that input is yes and a no instance otherwise. The above definition is, admittedly, a bit vague, and so let us look at a few basic examples. A simple decision problem, related to the sorting problem, is as follows.

Clearly, the above problem has a simple yes/no answer and so it is, indeed, a decision problem. The input \(x_1,\dots,x_n\) is known as an instance of the problem. Here is another example.

In other words, the 3-Colourability problem asks whether it is possible to colour the vertices of \(G\) with three colours so that every pair of adjacent vertices have different colours; such a graph is said to be 3-colourable. While decision problems may seem more restrictive than the class of optimization problems from Definition 1.1.1, they are closely related, as the next example demonstrates.

The relevance of this decision problem to an optimization problem can be justified as follows. Suppose that the domain \(X\) was defined in terms of some sort of “input structure” of size \(n\text{.}\) For example, \(X\) is the set of all permutations of \(n\) real numbers, or the set of all matchings in a complete bipartite graph on \(n\) vertices. Now, if there exists some \(M_0\) such that the answer to the above problem is “Yes” when \(M=M_0\) and, if, for every \(M\text{,}\) the above problem can be solved in polynomial time with respect to \(n\text{,}\) e.g. time \(O(n^k)\) where \(k\) does not depend on \(n\) nor \(M\text{,}\) then the optimization problem from Definition 1.1.1 can be solved in time \(O(M_0 n^k)\) by simply solving Problem 1.4.4 for each \(1\leq M\leq M_0\) and outputting the smallest value of \(M\) for which the answer is “Yes”. In fact, by using a binary search, one can reduce the running time to \(O(\log_2(M_0) n^k)\text{.}\) So, if, additionally, \(\log_2(M_0)\) is bounded by a polynomial in \(n\text{,}\) then a polynomial-time algorithm for Problem 1.4.4 gives rise to a polynomial-time algorithm for the corresponding optimization problem.

A key idea in computational complexity is the idea that decision problems can be divided into equivalence classes based on “hardness.” Near the “easy” end of the spectrum is the class P consisting of every decision problem which can be solved via a polynomial-time algorithm (for every possible input). As we have said before, polynomial-time algorithms are often thought of as being “efficient” and so the problems in P are thought of as being “tractable.”

Another important set of problems is the class of non-deterministic polynomial time problems, denoted NP. A certificate for a decision problem is a mathematical object which contains enough information to determine the answer to the problem (either “yes” or “no”). For example, in Problem 1.4.3, a certificate for a “yes” answer could be a function \(f\) with the property described in the problem statement and, in Problem 1.4.4, a certificate for a “no” answer could be an element \(x\) of \(X\) such that \(f(x)>M\text{.}\) A decision problem is contained in NP if every yes instance of it admits a certificate which can be verified in polynomial time. For example, Problem 1.4.3 is in NP because, if \(G\) is a yes instance, then the function \(f\) in the statement of the problem is a certificate that can be verified in polynomial time. To verify it, simply check that \(f(u)\neq f(v)\) for each edge \(uv\) of \(G\text{,}\) one by one. Note that NP is defined in terms of the existence of a certificate that can be efficiently verified, but it says nothing about how much time is required to find such a certificate. So, the criteria for membership in NP is not about whether the problem itself (like 3-Colourability) can be solved in polynomial time, but it is rather about whether there exists a problem (like checking whether a 3-colouring is valid) that can be solved in polynomial time where the latter problem could be used to check whether a purported solution to the original problem is valid or not. This may seem like a rather arbitrary and obscure concept at first, but, if you give it a chance, then you are likely to see why it is a valuable notion later on. Here is another famous example of a problem in the class NP.

Clearly, Problem 1.4.5 is in NP. Indeed, if you wanted to convince someone that a given graph \(G\) is a yes instance, then it would be possible to do so by simply producing a Hamiltonian cycle in \(G\) and verifying that it is, indeed, a Hamiltonian cycle. The verification could be done in \(O(n)\) steps (i.e. a linear number of steps in terms of \(n\)) by simply checking that each of the required adjacencies are present in the graph \(G\text{.}\)

A huge number of problems that we encounter in mathematics and in practical applications belong to the class NP. Therefore, there is a huge incentive in settling Problem 1.4.6. On one hand, if \(\text{P}=\text{NP}\text{,}\) then the proof of this fact would immediately yield a polynomial time algorithm for a wide range of problems that are of high practical importance whereas, if \(\text{P}\neq\text{NP}\text{,}\) then we would finally have certainty that there is no hope in finding polynomial-time algorithms to solve the problems in \(\text{NP}\setminus \text{P}\text{.}\)

At this point, we would like to stress that the abbreviation NP stands for non-deterministic polynomial time, and does not stand for “non-polynomial time.” This is a misnomer that is commonly assumed by beginners in the area. There are several theoretical problems with this terminology, apart from the fact that it is not what NP stands for. As we have just discussed, every polynomial-time solvable decision problem is in NP (and so it is wrong to say that problems in NP are non-polynomial time) and, moreover, we do not know whether P is equal to NP (and so, theoretically, it could be true that every problem in NP is polynomial-time solvable).

While the complexity classes discussed above are interesting in their own right, we should mention that, in this course, most of the problems that we will encounter fall into the classes P, NP or co-NP. For any problem in NP, one can easily get an example of a problem in co-NP by simply negating it. For example, the problem of determining whether a graph is not 3-colourable is in co-NP, as is the problem of determining whether a graph does not have a Hamiltonian cycle. However, there are also some problems which naturally live in the class co-NP, as the next example shows.

Note that the same argument that we used to deduce that \(\text{P}\subseteq \text{NP}\) can be used to show that \(\text{P}\subseteq \text{co-NP}\text{.}\) Therefore, \(\text{P}\subseteq \text{NP}\cap \text{co-NP}\text{.}\) The set \(\text{NP}\cap \text{co-NP}\) is interesting in its own right, as it is the class of problems in which any instance has a certificate that can be checked in polynomial time. In many cases, the problems in this class exhibit a form of duality, like we discussed in Section 1.1. Sometimes in this course, we will show that a problem is in \(\text{NP}\cap\text{co-NP}\) and cite this fact as “evidence” that the problem may, in fact, be in P. This is supported by the following open problem which is a close relative of the P vs. NP Problem. The consensus view seems to be that the answer to this question is “yes;” see Figure 1.4.9.

Note that, in Problem 1.4.7, the size of the input is deemed to be the number of digits (i.e. \(n\)) not the value of the integer \(x\) itself. Of course, a natural certificate to show that \(x\) is not prime is a pair \(p,q>1\) of integers such that \(x=pq\text{.}\) Moreover, when provided with such a pair of integers, one can verify that \(x=pq\) in polynomial time with respect to \(n\text{;}\) in particular, the standard multiplication algorithm that you learned in elementary school would have a running time of \(O(n^2)\text{,}\) and there are even faster algorithms in the literature. As it turns out, the problem PRIME is actually polynomial-time solvable, as was shown in this landmark paper.

In order to show that a problem is tractable, one only needs to provide a polynomial-time algorithm to solve it. To be clear, this is often a highly non-trivial task, but at least it is a tangible goal. Moreover, every improved algorithm that we develop will reduce the running time. In contrast, it is often much harder to bound the amount of time required to solve a given problem from below, as doing so would require ruling out the existence of any faster algorithm to solve it. In particular, it is generally very hard to definitively prove that a problem is intractable. This difficulty is at the heart of the P vs. NP problem (Problem 1.4.6).

While it is often hard to formally prove that a given problem is intractable, a powerful idea in computational complexity is that it is often possible to prove that a given problem is “at least as intractable” (or, “at least as hard”) as another. As a trivial example, the problem of determining whether a general graph \(G\) has a Hamiltonian cycle is at least as intractable as the problem of determining whether a bipartite graph contains a Hamiltonian cycle. This is because, obviously, if we had an algorithm which could solve the first problem for any possible input, then the same algorithm could also solve the second problem, since it is nothing more than a restricted case of the first problem. To obtain some more interesting examples, we require the notion of a polynomial-time reduction.

When a problem A can be reduced to a problem B, then we think of the problem B as being “at least as hard” as A. This is because if we had an algorithm to solve B, then we would immediately have an algorithm for solving A by simply converting an instance of A into an instance of B and then running the algorithm for problem B on that instance. Note that, saying that B is at least as hard as A does not imply that A can be solved faster than B can. In fact, when converting an instance of A into an instance of B, it is possible that the instance of B that we obtain is much larger (by a polynomial function) than the instance of A was. For example, each instance of A of size \(n\) may correspond to an instance of B of size \(O(n^{100})\text{.}\) Thus, a linear-time algorithm for solving B would correspond to an algorithm for solving A with running time \(O(n^{100})\text{,}\) while a quadratic time algorithm for B would yield a \(O(n^{200})\) algorithm for A. So, when saying that one problem reduces to another, we should always be aware that the former problem is easier than the latter up to a polynomial loss in efficiency.

The notion of polynomial reductions allows us to divide the universe of all problems into equivalence classes of the same complexity. That is, two problems A and B can be thought of as having the “same” difficulty if A reduces to B and B reduces to A; when this is true, we say that A and B are polynomial-time equivalent. We will explore these topics more deeply in the context of NP-hard and NP-complete problems in the next section.