So far, we have (mostly) been looking at problems for which we know efficient algorithms that solve them exist. However, we've stumbled across some problems for which we don't know whether there are efficient algorithms that solve them. This leads to the question of why we don't know whether they have efficient algorithms and whether we should expect to be able to come up with them.
These questions are far more relevant than they might seem. If we can't know whether or not there is an efficient algorithm, should we keep on trying to find one? Or is it a waste of time? How can we tell when we're presented with a problem that is difficult in this sense? Maybe these problems are rare or not that useful? Or maybe we're just not trying hard enough?
The answers to these questions are not entirely obvious. After all, the entire discipline of computer science was born in the early 20th century out of the desire for mathematicians to (essentially) automate logic and theorem proving. One of the first models of computation, the Turing machine, was defined in order to show that this was not possible and that there were problems for which no algorithm to solve it exists. The nature of such problems are the subject of another course.
The questions we face are not quite as extreme, but they come from the same place. The existence of hard problems places a philosophical and practical limit on the power of computation. And that would be a reasonable conclusion, except that the state of our understanding of these problems is not even as clear as being able to say that these problems are definitely impossible to solve efficiently.
We will first explore the main mechanism by which we can determine how hard a problem is: reduction. Reductions formalize a way to compare the difficulty of one problem with another. We've already seen some examples of reduction, albeit informally, when we took problems like minimum cut or bipartite matching and turned them into maximum flow problems.
The intuition behind this idea is this: I know that if I can solve maximum flow, then I can solve bipartite matching, because I have a way of turning a bipartite matching problem into a maximum flow problem. So if I have an efficient way to solve maximum flow and an efficient way to transform a bipartite graph into an appropriate flow network, then I can efficiently solve bipartite matching. That means that bipartite matching should be at least as hard to solve as maximum matching.
Note that for this comparison, it doesn't actually matter if we have an efficient algorithm for solving maximum flow. We just know that if we can somehow solve maximum flow, then that gives us a baseline for how hard it would be to solve bipartite matching. This would be just as true whether we knew how maximum flow was solved or not. We could have a mysterious tungsten cube that magically solves it for that matter.
Let's formalize this notion.
An oracle for a problem $X$ is a computational device that, when given an instance of $X$ will solve it in a single computational step.
Here, an oracle is an all-powerful magical device that solves a particular problem for us in one step. Obviously, such devices don't actually exist, or else we could've skipped a lot of classes. Oracles are sort of like a thought experiment: if we could solve a particular problem efficiently, what else would that let us solve efficiently?
A problem $A$ is polynomial-time reducible to a problem $B$, denoted $A \leq_P B$, if an instance of $A$ can be solved by:
Reductions are a tool that have been used since the beginnings of computer science, before they made their way over to complexity theory. Reductions were first used as a way to show that certain problems were unsolvable. In other words, there are problems for which there is no algorithm that can solve it, which is much stronger than our interest in efficient alogorithms.
So how do we use reductions? The idea is that we get a schematic diagram that looks roughly like the following:
Here, the green box is our algorithm that transforms an instance $I$ of $A$ into an instance $I'$ of $B$. The mysterious blue box then solves $B$ on $I'$ for us for free.
One of the things this should make clear is that just because $A \leq_P B$, it doesn't mean that $B \leq_P A$. That is, reductions are not symmetric! This idea is captured by the diagram, but it's also captured by looking at bipartite matching and maximum flow: just because we have a way to turn bipartite matching into maximum flow doesn't mean this gives us a way to turn maximum flow into bipartite matching!
However, if we can prove such a relationship, we can prove some things if we know a few more things about the problems that we're relating. In particular, if we have an algorithm for one of the problems instead of a magical cube, we can say some more interesting things.
Let $A$ and $B$ be problems. If $A \leq_P B$, then
Suppose there is an algorithm that solves $B$ in polynomial time, say $O(p(n))$ for some polynomial $p$. Since $A \leq_P B$, there is an algorithm that transforms an instance of $A$ into an instance of $B$ in polynomial time, say $O(q(n))$ for some polynomial $q$. Then we have the following algorithm that solves $A$:
Suppose the size of $I$ is $n$. How big can $J$ be? Since the transformation algorithm runs in $O(q(n))$ time, in the worst case, $J$ can have size $O(q(n))$, since we need to write $J$. Then the running time for the entire algorithm is $O(p(q(n)))$, which is polynomial in $n$.
Now, suppose that $A$ cannot be solved in polynomial time. Assume for contradiction that $B$ can be solved in polynomial time. Then by our above argument, we have a polynomial time algorithm for $A$, which contradicts that $A$ cannot be solved in polynomial time. Therefore, $B$ cannot be solved in polynomial time.
Again, we've already seen an example in this in bipartite matching: we were able to show that because we had a way (specifically an algorithm) to transform an instance of bipartite matching, which is an undirected graph $G = (V,E)$, into an instance of maximum flow, which is a flow network $G' = (V',E',s,t,c)$, and we had a polynomial time algorithm for solving maximum flow, we could conclude that we had a polynomial time algorithm for solving bipartite matching.
That idea on its own—transforming a problem into a problem we already know how to solve—is already useful, but here, we note that (2) is the contrapositive of (1), and this is really the statement that we're interested in for this next part of the course. Suppose we have a problem that we are considering. How do we know if we can write an efficient algorithm that solves it? One way would be that it's possible and we find it and write it. But what if we can't? The next best thing may be to compare it against some other problem that we think is hard.
Before getting into what constitutes a hard problem, we'll first dive into how to perform these transformations, because that's most of what we'll be asking you to do in this part of the course.
We will begin with some fundamental graph problems.
Let $G = (V,E)$ be an undirected graph. We say a set of vertices $S \subseteq V$ is independent if no two vertices in $S$ are joined by an edge.
Here, we have a graph with an independent set highlighted in cyan. This is an independent set because no two vertices in the set are adjacent to each other.
Such sets are called independent because they're mutually independent of whatever relationship is defined by the graph. For instance, if you think of this as a social network, it's a group of people who don't share any friends in common.
One thing we might notice is that there's actually a much easier independent set than the one we exhibited. The set $\emptyset$ is an independent set, since no two vertices in the set are joined by an edge. So obviously, the challenge is we'd like to find as large an independent set as possible. This leads to the following question.
The independent set problem is: Given an undirected graph $G$ and integer $k \geq 0$, does $G$ contain an independent set of size at least $k$?
This might seem like a strange formulation for a problem. We are typically interested in optimization problems, which ask for a solution that maximizes or minimizes some particular property. So the natural question for something like independent set would be to find the independent set of maximum size.
Instead, we have what is called the decision problem variant of the optimization problem. The issue here is that the solution to an optimization problem is a solution, which complicates things. However, the answer to a decision problem is a Yes or No. This formulation of the problem is more convenient when discussing reductions, since it is more convenient to map Yes/No answers onto other Yes/No answers.
A question that this raises is whether the two problems are actually equivalent. If they're not, then this entire exercise is kind of pointless. Luckily, we can show that solving a decision problem means we can solve the optimization problem and vice-versa. One direction is obvious: solving the optimization problem automatically gives us an answer for the decision problem for any $k$.
The other direction is less obvious, but doable. If we have something like a graph, then we can employ binary search to search for the largest $k$ for which the answer is Yes.
Now, let's consider a similar problem.
Let $G = (V,E)$ be an undirected graph. We say a set $C \subseteq V$ is a vertex cover if every edge $e \in E$ is incident to at least one vertex in $C$.
Here, we have a vertex cover with vertices highlighted in yellow. These form a vertex cover because every edge is incident to at least one vertex in the cover.
Vertex cover is an example of a class of problem called covering problems, which involve trying to choose a set of elements that cover some relationships across the entire set. For graphs, those relationships are edges.
Just like independent sets, there is a very easy vertex cover we can choose to ensure that we cover every edge: the set $V$ itself. Since every edge is incident to a vertex in $V$, it's a vertex cover. So the challenge here will be to to find as small a vertex cover as possible. This leads to the following question.
The vertex cover problem is: Given an undirected graph $G$ and integer $k \geq 0$, does $G$ contain a vertex cover of size at most $k$?
So we want to relate these two problems somehow. One of the things you might notice from our two examples, which exhibit a maximum independent set and minimal vertex cover on the same graph, is that the independent set and vertex cover happen to be complements of each other. We will prove and make use of this observation.
Independent Set $\leq_P$ Vertex Cover.
Suppose we can solve Vertex Cover. We will show how to solve Independent Set by using an algorithm for Vertex Cover. Let $G = (V,E)$ be an undirected graph. We will show that a set $S \subseteq V$ is an independent set if and only if $V - S$ is a vertex cover.
Suppose $S$ is an independent set and consider an edge $(u,v) \in E$. Since $S$ is independent, we must have at least one of the following:
In any of these scenarios, $V-S$ covers $(u,v)$. Since $(u,v)$ was arbitrary, $V-S$ is a vertex cover.
Now, suppose that $V-S$ is a vertex cover and consider an edge $(u,v) \in E$. Since $V-S$ is a vertex cover, we must have at least one of the following:
In any of these scenarios both $u$ and $v$ will not be in $S$, so $S$ is an independent set.
Now, note that if $|S| = k$, then $|V-S| = n-k$. Therefore, we can solve Independent Set by running an algorithm on $G$ and asking whether $G$ has a vertex cover of size $n-k$.
One important note is that it is necessary to show that our transformation satisfies an if and only if statement. In essence, to show that $A \leq_P B$, what we're trying to do is map "Yes"es of $A$ to "Yes"es of $B$ and "No"s of $A$ to "No"s of $B$.
One of the things that we've seen and will continue to see is that there are some surprising connections between problems that seem very different. For instance, we will consider the following problem.
The set cover problem is: Given a universe $U$ of $n$ elements, a collection of subsets $\mathcal X = \{X_1, \dots, X_m\}$ of $U$, and an integer $k \geq 0$, does there exist a collection of at most $k$ subsets $X_i$, $1 \leq i \leq m$, whose union is equal to $U$?
Consider the universe $U = \{1,2,3,4,5,6,7,8,9\}$ and the sets
Clearly, the easy answer is that choosing every set is a set cover for $U$, so we really want the smallest set cover for $U$. Such a set cover is $X_1, X_4, X_5$.
This is a problem about sets, so at first glance this doesn't seem like it has anything to do with the graph problems that we've been looking at. But from its name, you can guess that set cover is a covering problem like vertex cover and we remember that graphs (like most things in mathematics) are made of sets, so maybe there is a connection after all.
Vertex Cover $\leq_P$ Set Cover.
We are given an instance of Vertex Cover $(G,k)$ with $G = (V,E)$ and $k \geq 0$. We will show how to solve Vertex Cover by constructing an instance of Set Cover $(U,\mathcal X,k)$.
Let our universe $U$ be the set of edges $E$. Then for each vertex $v \in V$, we define the subset \[X_v = \{e \in E \mid \exists u \in V, e = (u,v) \}.\] In other words, $X_v$ is the subset of edges that are incident to $v$.
Now, we want to show that $G$ has a vertex cover of size $k$ if and only if $U$ contains a set cover by sets in $\mathcal X$ of size $k$.
Suppose that $C \subseteq V$ is a vertex cover of size $k$ in $G$. Then we choose $\mathcal Y = \{X_v \mid v \in C\}$ as our set cover. Since $C$ is a vertex cover, every edge in $G$ is adjacent to at least one vertex in $C$. Therefore, every edge is a member of some set in $\mathcal Y$. And by definition, $|\mathcal Y| = k$.
Now, suppose that $\mathcal Y \subseteq S$ is a set cover of size $k$ for $U$. Then we take $C = \{v \mid X_v \in \mathcal Y\}$ and claim that $C$ is a vertex cover. To see this, we note that since $\mathcal Y$ is a set cover, every element of $U$ is in some set in $\mathcal Y$. Therefore, every edge is a member of some set in $\mathcal Y$.
Then, we can solve Vertex Cover by constructing for an instance $(G,k)$ an instance $(U,\mathcal X,k)$ and running an algorithm for Set Cover on $(U,\mathcal X,k)$.
In other words, we've shown that if we can solve this problem on sets, then we can solve a problem on graphs. But what if we wanted to solve Independent Set? It turns out that reduction is transitive.
If $A \leq_P B$ and $B \leq_P C$, then $A \leq_P C$.