Prologue
I normally prefer to share posts of a more practical nature, but in celebration of a hard-fought semester fraught with theory, research, and not a whole lot of actual development in the curriculum, I've decided to share some of what I learned even if it isn't directly applicable to the kind of day-to-day development most of us face on the job.
One of my most vicious classes last semester was combinatorial algorithms, a course focusing on algorithm design and analysis with particular attention to time complexity. Needless to say, computers and programming didn't factor into the curriculum at all. This was strictly a math class. Our big assignment for the semester was to pick an existing problem in the math domain, describe it in detail, and analyze a variety of the known approaches to solving it.
I chose the independent set family of problems, and the professor - considered one of the most brutal on campus - wrote me to congratulate me on a flawless paper. So I figured it must not have been too shabby, and I'll pass it on to the masses! Now, let's talk about independent sets!
Introduction: What is an Independent Set?
If you already know about graphs, and what an independent set is, you can skip ahead, but a little bit of background knowledge is needed to understand what an independent set is. Fair warning, it would be quite helpful to know a little bit about graphs, time complexity, and dynamic programming (or at least recursion). But I'll do my best to make this digestible with a minimum of prerequisite knowledge.
The very least you need to know is that a graph is made of vertices and edges, so that the edges connect the vertices together, like connect-the-dots. You can have a graph with any number of vertices, connected to each other in any number of ways by any number of edges. We call the group of vertices together a set of vertices, and the group of edges is also a set. Any group of items that belongs to a set (but might not include all of the items in that set) is called a subset.
So, if we have a graph, let's call it G, composed of vertex set V and edge set E, an independent set within that graph is a subset of the vertices in G where none of the vertices in the subset are connected by any edge. In other words, an independent set of vertices in a graph is a subset of the graph's vertices with no two vertices adjacent.
Two important types of independent set we will talk about below include the maximal independent set and the maximum independent set (they are sometimes, but not always, different from each other). We will also discuss what a graph’s independence number is. For the most part, we're only concerned with maximum independent sets and independence numbers, but I want to talk about maximal independent sets because that will help us to understand just what a maximum independent set is.
A maximal independent set in G is a type of independent set. In a maximal independent set, if you add any vertex from the total vertex set V, that wasn't already in the subset, that would force an adjacency into the subset. Remember, if we have two adjacent nodes in our graph, it's not independent. So a maximal independent set is a subset of the vertices in G that can't have any more of G's vertices added without stopping the subset from being independent.
There are two things I find worth noting about maximal independent sets. First, a given graph might have any number of maximal independent sets. Second, each maximal independent set might have a different total cardinality (number of vertices in the subset). In other words, a single graph might contain multiple maximal independent sets, each of varying size. The largest possible one of these is called the maximum independent set. This is the largest independent set found in a given G.
Note also that a graph can have multiple maximum independent sets, but in this case, all of the maximum independent sets will have the same cardinality.
Finally, whether there is only one maximum independent set, or there are many, we refer to the cardinality of maximum independent sets as the independence number of the graph to which they belong.
We'll use these terms and concepts more below to discuss a variety of problems relating to independent sets, most importantly to my research, the maximum independent set problem and the independent set decision problem
Details: Problem Formulation and Motivation
As we noted above, the maximum independent set problem takes a graph as input, G = (V, E). The goal is to find a subset of V comprising one maximum independent set on G, which might just be one of several maximum independent sets in G. The solution can then be used to obtain the answer to the independence number problem, which takes the same input (a graph) but seeks, instead of a maximum independent set, the independence number of the graph (the number of vertices in the maximum independent set). All we have to do to get the independence number once we have the maximum independent set is return the cardinality of the maximum independent set, and we're done. Along the same lines, the solution to the maximum independent set problem also comes packaged with the solution to the independent set decision problem, which is looking for a simple Boolean value: true if the graph’s independence number is greater than or equal to some given number, k, and false otherwise.
In other words, we can formally define the independent set decision problem as taking a graph, G = (V, E) and an integer k, and returning a Boolean value, true if k is less than or equal to G’s independence number, or false if k is greater than that independence number. In the simplest terms, we have a number, and we want to know if there is an independent set in some graph that is as big as our number.
| Input: a graph G = (V, E), and an integer k |
|
Output: a Boolean true or false value |
Believe it or not, these versions of the same problem – maximum independent set, independence number problem, and independent set decision – each has a specific real world application. The maximum independent set and independence number problems in particular have a wide variety of practical uses. The maximum independent set, for instance, is a problem that materializes in visual pattern recognition, molecular biology, and certain scheduling applications; and the independence number problem has applications in molecular stability prediction and network configuration optimization.
Astute readers will notice that I've omitted the very specific subject of the independent set decision problem, which (to refresh our memories) seeks only a Boolean value and no other data. This member of the independent set family of problems is not considered to have any practical "real world" application. That said, it plays a crucial role in the realm of theoretical research. It is considered necessary in order to apply the theory of NP-completeness to problems related to independent sets. That's a topic for a whole other kind of blog post.
Though the topic of NP-Completeness can get pretty hairy, the dominating factor of the time complexity of solving the decision version of this problem is the same as for the independence number problem or the maximum independent set problem. As mentioned above, the decision version of the problem uses the same underlying algorithm as the independence number problem, and simply examines the resulting data to a different end. In short, to get the solution to the decision problem, we reduce the independence number solution to a Boolean value. The independence number problem itself is the same as the maximum independent set problem, with the output reduced to a single value representing the cardinality of a maximum independent set in G. But we're getting a bit beside the point here.
Since the domains of practical applications defer in large part to the maximum independent set and independence number versions of this problem, this is where the vast majority of interesting research on the topic of independent sets has been done. The complexity of the algorithms to solve all three problems is dominated overwhelmingly by the operations performed in the original maximum independent set problem. The transformations we have to make to produce solutions to the other versions of the problem are pretty trivial (counting cardinality, or comparing a given k value to the independence number to determine a Boolean value). For that reason, we'll focus on the research surrounding the maximum independent set problem.
The Brute Force Approach – Slow but Simple
Now let's talk about how we actually solve this problem. The brute force approach to the maximum independent set problem is very simple in principle. In short, all we need to do is iterate over all possible subsets in G, and then for each subset, check all vertices v in V for pair-wise adjacency. The time complexity of checking each possible subset is O(2n), yielding an exponential time complexity, and the checking of all vertices yields an additional (relatively insignificant) polynomial factor to the complexity, referred to in this case as poly(n), where n is, of course, the number of vertices in G. We consider the polynomial factor insignificant because the complexity of any polynomial factor will never dominate the exponential factor of O(2n), and so becomes irrelevant for large graphs.
In summary, for each vertex subset S in V, we check all vertices in S for adjacencies. If an adjacency exists, this subset can be thrown out because the adjacency violates the defintion of an independent set. As we iterate over subsets, we simply measure each and track which is the largest. For maximum independent set, we return the independent set that ends up providing the largest number of vertices over all iterations (this being the largest, read maximum independent set). This ends up taking a total of O(2npoly(n)) time. For the independence number problem, instead of returning the largest independent set, we return only the cardinality of the largest independent set, which we can trivially store while iterating over subsets. Finally, in the case of the independent set decision problem, we simply compare the independence number gained via the above brute force algorithm, trivially compare it against our given k, and return the appropriate Boolean value, yielding a worst case that is still O(2npoly(n)) time.
Serious Business: Strategy and Analysis of an Improved Algorithm
Before we get too excited, it's only fair to say right up front that we are not going to beat exponential time complexity with any known algorithm for solving this problem. That said, a fair amount of research has been done on it, yielding impressive improvements to the base of exponentiation. This, in turn has led to vastly improved run times in real world applications that rely on solutions to the independent set family of problems. (We're going to start getting very technical here.)
Following Jeff Erickson’s guide to the optimization of the independence number algorithm, we see that there are a series of steps that can be taken in turn to improve the performance of our algorithm. As a first step toward understanding the complicated means of optimization, Erickson provides a recursive formulation of an algorithm for obtaining the independence number on a graph, G (shown below). Next, he shows that the worst case scenario for that recursive algorithm can be split into subcases, some of which are redundant recursive calls that do not need to be performed in duplicity. Eliminating these duplicate cases, obviously, improves run time complexity. Finally, he shows that this improvement can be repeated on the resultant worst case, splitting that into further subcases, some of which are also redundant; and so on and so forth, continually improving the run time complexity in seemingly small, but ultimately meaningful, increments. To begin, observe Erickson’s most elementary version of the algorithm in its recursive form:
MaximumIndSetSize(G):
if G = { empty set }
return 0
else
v = any node in G
withv = 1 + MaximumIndSetSize( G \ N(v) )
withoutv = MaximumIndSetSize( G \ {v} )
return max { withv, withoutv }
To clarify the notation here, N(v) refers to the neighborhood of v, meaning the set that includes v and all of its adjacent neighbors, but no other vertices. The backslash symbol refers to set-wise exclusion or "subtraction." For example:
{ a, b, c } \ { b } yields { a, c }.
As you can see at a glance, the number of recursive calls at each iteration is doubled! This yields the same exponential growth of time complexity we saw in the brute force approach. What’s worse, we see that in the worst case, G \ N(v) = G \ {v}, meaning that v has no neighbors! This means that in both recursive calls at each iteration, our vertex subset is only being reduced by size 1. The result is the recurrence equation T(n) = 2T(n – 1) + poly(n), yielding a time complexity of O(2npoly(n)). T(x) here represents the time required to solve a problem of size x.
At this stage, though no clear improvement has yet been made, we already have the information we need to make our first improvement to the algorithm. As noted above, in the worst case, G \ N(v) = G \ {v}, meaning that v has no neighbors. However, if v has no neighbors, then it is guaranteed to be included in every maximal independent set, including maximum independent sets, because a node that never has neighbors is always independent! As a result, one of the recursive calls, the one assigning the value withoutv, becomes superfluous, because no maximum independent set can exclude v if it never has neighbors in any subset. At the same time (but on the other hand), if v does have at least one neighbor, then G \ N(v) will have at most (n – 2) vertices. That's quite a brain-full, so let me explain it another way, with concrete examples.
Let's say G has 10 nodes total. So n is 10. Then, if our random node v has at least 1 neighbor, then the neighborhood of v is size 2 or greater. Since N(v) is 2 or greater, then G \ N(v) is 10, minus some number 2 or greater. This line of reasoning yields a new recursive formula with a dramatically improved run time complexity:
T(n) ≤ O(poly(n)) + max{T(n - 1), [T(n - 1) + T(n - 2)]}
The run time complexity on this improved version of the recursive algorithm is reduced to T(n) ≤ O(1.61803398875n) after just one subcase division! That might not seem like much of an improvement, but in a little bit we're going to see some concrete examples of just how big an improvement this can make at execution time. In the meantime, following this line of logic and making further observations, we can immediately improve on our new worst case by splitting that into subcases – some of which are, again, redundant and superfluous.
Note that our new worst case is the case in which both T(n – 1) and T(n – 2) must be calculated. In other words, this is the case in which our recursive calls are doubled, and in which the graphs we pass along are of relatively large size (only 1 or 2 vertices smaller than the graph from which they were derived). In this specific case, v has exactly 1 neighbor; let's call this neighbor w. Specifically because v has exactly 1 neighbor, we will find that either v or w will appear in every maximal independent subset of our original G. Think about it: if w is in a maximal independent set, v simply can't be, because they're neighbors, and two neighbors can't both be in the same independent set. Conversely, if w is not in a maximal independent set, v will be, because its only neighbor is not in the set, which frees v up to join without fear of standing by an adjacent neighbor. Taking this line of reasoning yet another step further, we see that given a maximal independent set containing w, we can remove w and instead include v. Therefore, we can conclude that some maximal independent set will include vertex v (whether this maximal independent set ends up being maximum or not).
Note also that if we know there is a strict pair-wise relationship between v and w (due to the given fact that v has 1 adjacent neighbor), we never have to evaluate the recursive case in which the call MaximumIndSetSize(G \ {v}) needs to be made. Our case evaluating T(n – 1) + T(n – 2) becomes only T(n – 2). Furthermore, expanding on our idea from the last worst-case scenario subcase split, we will see that if the degree of v is 2 or more, then N(v) will contain at least 3 vertices, and therefore G \ N(v) will have at most (n – 3) vertices. In such a case, the max{...} function of our recursive algorithm is expanded:
T(n) ≤ O(poly(n)) + max{
T(n - 1),
T(n - 2),
T(n - 1) + T(n - 3)
}
This second improvement yields a time complexity of T(n) ≤ O(1.46557123188n), a smaller but still valuable improvement. On the other hand, note that the complexity of the algorithm is growing rapidly here. Not the time complexity, but the algorithmic complexity, as well as the difficulty we find in determining where to make future optimizations. At each step we take toward a faster algorithm, things are getting much more complicated. At this point, the complexity of the algorithm and the steps required to make further improvements go beyond the scope of what I can talk about in a blog post (even one as ridiculously long and complicated as this). However, Erickson does go on to show that further clever observations can be made continuously, yielding even better time complexities. Two further observations of worst-case splitting and problem structure yield time complexities T(n) ≤ O(1.44224957031n) and T(n) ≤ O(1.3802775691n), respectively. According to Erickson, the best published time complexities for this problem are solutions quoted by Fomin, who achieved T(n) ≤ O(1.2210n, and Bourgeois, who managed to achieve an impressive T(n) ≤ O(1.2125n).
Considering we're still ultimately stuck with exponential time, it may seem like a lot of work needs to be done for miniscule returns. After all, 1.221 and 1.2125 are almost the same number, right? On the other hand, certain practical applications demand tremendous effort, and therefore any ounce of efficiency that an improved algorithm can provide becomes valuable. Larson includes as an example in his writings a reference to the prediction of molecular stability in the tetrahedral C100 isomer. For this example, the time complexity T(n) of determining the independence number of this molecule is T(100). Therefore, working out the arithmetic, we see the run time for this example reduced as follows (ignoring poly(n):
With these concrete numbers to reference, we can see clearly that the jump from the brute force method to even a slightly optimized solution is more than worth the effort. The first jump alone results in an improvement to run time of many orders of magnitude! After that, we admittedly begin to see diminishing returns for the effort taken to develop improved algorithms. For instance, I personally doubt that the extra effort by Bourgeois to beat Fomin by a mere 0.0085 on the exponentiation base was of debatable value as anything more than a stepping stone. In my personal opinion, the return on invested effort put in to develop Robson’s final state-of-the-art solution (discussed below) was not worth it for such a small gain from Fomin's algorithm. At least, not in the case of the C100 stability prediction problem. That said, 100 may be considered a small quantity of vertices in some problem domains, such as large network configuration optimization or scheduling problems. In those cases, it may actually be worth it to go to the trouble of researching and developing the absolute best state-of-the-art in terms of fast, efficient algorithms.
Robson's Incredible State of the Art, Conclusions
Research has yielded relatively fast algorithms for solving the independent set family of problems. Some, notably by Bourgeois, are capable of a time complexity as low as a flabbergasting T(n) ≤ O(1.0854n) time complexity using strategies of case analysis and reduction rules. However, it's worth noting that algorithms that are as fast as these come with severe limitations. For example, the Bourgeois algorithm is limited to graphs with average vertex degree 3. That is a serious limitation! The fastest published algorithm for solving the independent set family of problems for generic graphs (with unbounded number of degrees), by Bourgeois, runs in only T(n) ≤ O(1.2125n).
The absolute state of the art for solving the independent set family of problems is actually a computer-generated algorithm. The algorithm is described in an unpublished technical report by Robson, and is claimed to boast a time complexity of only O(1.1889n). However, the trade-off at this level of acceleration is mind-boggling algorithmic complexity. Just the high level description of the algorithm, excluding the rest of the accompanying report, fills fully 15 pages, and thus excludes discussion of the algorithm in any depth from the scope of most academic papers, let along blogs. I'm not an expect on algorithmic analysis at quite that level, but I'd wager such an algorithm would even be excluded from use in applications at that point, due to its sheer complexity.
As algorithms grow in efficiency, but also in complexity, it gets tough to make universal recommendations on which to use – or, in the case of the algorithms described above, how deep through the iterations of optimization a project team should go to try and improve the performance of their algorithm. The context of the project would have to come into factor.
For projects dealing with small graphs, it wouldn't be worth the effort to interpret and implement something like Robson's solution. Something like the example described by Erickson and outlined above would probably be good enough. For projects dealing with graphs of moderate size and predictably small average vertex degrees throughout, but needing accelerated solutions, something like the algorithm developed by Bourgeois would provide a superior middle ground.
Thanks for reading!
- Steven Kitzes
