We’ve already looked at intractable problems with straightforward translations. In this post, we are going to look at more creative reductions for problems where we don’t have a simple, singular translation available. But first, onto the Daily Problem:
This article is part of the Data Structures and Algorithms Series following the course The Analysis of Algorithms. If you missed the previous article, check that out first as well as a copy of The Algorithm Design Manual.
Answers to the previous Daily Problem
Suppose we are given a subroutine which can solve the traveling salesman decision problem in, say, linear time. Give an efficient algorithm to find the actual TSP tour by making a polynomial number of calls to this subroutine.
First we need to find the length l of a shortest TSP tour. Then we just go over every edge on the graph and see if, when we remove that edge, our shortest TSP tour is still l. If it is, that edge wasn’t part of the path so we remove the edge completely. The end result is a graph of only edges that build the l length of that shortest path. We only made a linear number of calls for our TSP decider since we just went over a linear number of edges in the graph.
Two examples of harder reductions
Once again, a reduction is simply a way of turning one concept into another; reducing it into a simpler/different problem. For more difficult reductions, we don’t have the straightforward algorithms that we had from our previous post and will require a bit more creativity.
1. Integer Programming & 3-SAT
I have to be honest, the rules for integer programming seem oddly arbitrary and kind of contrived. Integer programming in the context of combinatorial optimization has to obey 4 rules:
- Variables are integers
- You’ve got some inequality constraints over those variables
- A maximization function over some (or all) of those variables
- An integer target you need to hit
Again, it’s best to use JavaScript to provide a concrete example:
const sampleIntegerProgramming = (a, b) => {
// constraint 1
if (a < 1) return false;
// constraint 2
if (b < 0) return false;
// constraint 3
if (a + b > 3) return false;
const maximizationFn = b * 2;
const target = 3;
return maximizationFn >= target;
}
sampleIntegerProgramming(0, 0); // false - invalid constraint 1
sampleIntegerProgramming(2, 2); // false - invalid constraint 3
sampleIntegerProgramming(1, 0); // false - maximization misses target
sampleIntegerProgramming(1, 2); // true - all rules satisfied
As you might expect, you can reach impossible situations. If you just change your target to a value of 5, there is no possible set of integer arguments that would return a value of true.
We can reduce 3-SAT into integer programming; given we already know 3-SAT is hard, and we want to prove integer programming is hard, our translation will start with the 3-SAT problem. There aren’t as many silly rules for 3-SAT, but we can translate it pretty clearly:
- Variables are integers, restricted to
0(false) and1(true). - Inequality constraints, based on rule 1, are that all variables (and their negations) are between
0and1. Further, to ensure truthiness for every expression, we need to make sure all variables are less than or equal to1when summed with its negation (which must be greater or equal to1). - The maximization function is inconsequential as we’ve already mapped out all of the rules for 3-SAT, so we can keep it simple and just map this function to the identity function of one of our variables.
- The target value also doesn’t matter so to make sure it never matters we set it to something universally achievable like
0.
With these four rules for IP described in the veil of 3-SAT, we’ve shown our creative translation. We know every 3-SAT can solve an IP because, under these 4 rules, every clause in 3-SAT must have an answer of 1 (true). The inequality constraints sum to ensuring we just have an answer greater than or equal to 1. With a target of 0 we satisfy our target always since no 3-SAT problem can offer a result of false (0).
Flipping it around to have any IP problem provide a solution to a 3-SAT problem, we can say that we know all integer variables can only be 1 and 0. Any 1 is a true in the 3-SAT problem. Any 0 is a false in the 3-SAT problem. These assignments simply need to satisfy all expressions in a 3-SAT problem to ensure its validity.
And just like that, we prove the reduction works both ways and shows that integer programming is a NP-hard problem just like 3-SAT.
2. Vertex Cover & 3-SAT
We saw the definition of vertex cover in the previous article and it, too, can be reduced via 3-SAT.
- The boolean variables in 3-SAT are now two vertices (one for your variable’s value, one for the negated value) in your vertex cover graph connected by an edge. We’ll need
nvertices to ensure all edges are covered since no two edges can share a vertex. - Each expression in 3-SAT now needs three vertices (one for each variable in a 3-SAT expression). Each of those vertices form a triangle since those variables are linked in a given expression. That gives us a number of triangles equal to the number of expressions in our 3-SAT problem. Two of the three vertices in a triangle are needed to make a vertex cover, so you’re looking at
2enumber of vertices whereeis the number of expressions in your 3-SAT problem. - Construct a graph with
2n + 3enumber of vertices, joining the graph made in step 1 and the graph made in step 2. What this graph looks like is a wall of variables connected to their negations at their top, and an edge connecting them to their equivalent placement in their 3-SAT triangles.
And with that, we translated 3-SAT into vertex cover. Think of this like a pie chart with a legend. Each triangle makes up the segments of the pie with a different color. Each color points to a value on the legend, saying what that color represents (either the variable or the negated variable).
To show this translation is correct, we show, just like the previous example, that one problem solves the other (and vice versa).
Every 3-SAT gives a vertex cover because when we have a set of truthful assignments for our expressions, we can find those variables in the “legend” within our vertex graph. Since those assigments are true, we know we are covering one of the triangles. All of the other cross edges are covered by virtue of the fact that our “pie graph” is a triangle. The triangle configuration ensures coverability in one main portion, and the truthiness of our variables ensures we connect the triangles to the legend portion from step 1.
Conversely, every vertex cover gives a 3-SAT because in a graph of size n + 2e (the necessary size of a vertex cover graph), we just need to account for all vertices. Per our earlier definition, we need n vertices to represent our legend of possible variables. These vertices can define our 3-SAT truth assignment. The remaining 2e vertices have to be spread across each variable and it’s negation. In other words, we need to ensure that for a given 3-SAT problem, either you’re connecting your cover to the variable used in the expression (e.g. v1) or its negation (e.g. !v2). If you have a vertex cover, you’ve got at least one cross edge covered per triangle (representing the 3-SAT expression). In other words, you’re satisfying all expressions with a connection, or an evalution of true in 3-SAT for that particular expression.
That’s a mouthful, but we can go either way which means we have a reduction from 3-SAT to vertex cover! And with that, our final daily problem:
Onto the next Daily Problem
Show that the following problem is NP-complete: for a dense subgraph
Gwith integerskandy, doesGcontain a subgraph with exactlykvertices and at leastyedges?
More problems to practice on
For harder, more creative reduction problems, check out Problem 9-13 from the homework set.
Get the FREE UI crash course
Sign up for our newsletter and receive a free UI crash course to help you build beautiful applications without needing a design background. Just enter your email below and you'll get a download link instantly.