 |
| The Sea from Candolim beach, Goa |
 |
| Fig 1 |
I was also playing with a model checking tool called Alloy (http://alloy.mit.edu/alloy/). What exactly is Alloy ? Let me quote from the Alloy site...
"Alloy is a language for describing structures and a tool for exploring them. It has been used in a wide range of applications from finding holes in security mechanisms to designing telephone switching networks.
An Alloy model is a collection of constraints that describes (implicitly) a set of structures, for example: all the possible security configurations of a web application, or all the possible topologies of a switching network. Alloy’s tool, the Alloy Analyzer, is a solver that takes the constraints of a model and finds structures that satisfy them. It can be used both to explore the model by generating sample structures, and to check properties of the model by generating counterexamples. Structures are displayed graphically, and their appearance can be customized for the domain at hand.
...
The Alloy Analyzer works by reduction to SAT. "
(SAT means the "Boolean Satisfiability Problem", which, briefly, means determining whether or not there exist true/false assignments to boolean variables that satisfy given constraints or boolean formulas made from 'and' and 'or' boolean, binary operations between those variables. See http://en.wikipedia.org/wiki/Boolean_satisfiability_problem. For the purpose of this post, the implication of the last line of the quoted paragraph above, is that the model of any intractable problem, that we have built in the Alloy language, can be analyzed , with some limitations that will be clarified in later posts, by the Alloy analyzer after first converting (reducing) the model to boolean formulas and applying available analyses for SAT problems. To reinforce the words of caution, I am not saying that Alloy can solve a problem for any input.)
I had used Alloy in some work earlier, for modeling CAD to PLM data conversion situations, the purpose being to discover any inconsistencies and discrepancies that may arise because of the way we modeled. These gotchas sometimes ( or is that 'often' ?) escape us when we are trying to use only our grey cells to analyze and check complex models to see if they behave the way we expected or to see whether there are instances that behave the way we don't want them to.
Graph coloring
This time my requirement was slightly indulgent. During the course of some reading on Graph algorithms, I came across the line that 'The Graph coloring problem is NP-complete' and I was puzzled why. An oft-cited application of graph coloring is the problem of optimal register allocation for local variables and function arguments for a function call, during the code generation phase of compilation. The compiler ( its code generation/optimization phase) will first create a graph whose vertices correspond to the variables, and two vertices have an edge between them if their lifetimes overlap, which implies that the two variables can't be allocated the same register during code generation. It is important to know the minimum number of registers needed, because their total number is limited, and we would like as many of the variables to be accommodated in them, since access to registers is fastest for the CPU. First, what is the graph coloring problem, and specifically vertex coloring ?
This is what Wikipedia has to say.
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring.
 |
| Fig 2 |
Graph coloring and the classes NP, NP-hard and NP-complete
One flavor of the problem is to find the least positive integer k, representing the number of colors, that can vertex-color a graph (such that no two adjacent vertices share the same color). This is an optimization problem and this problem is said to be NP-hard. We define this term in the process of defining another class of problems, called the class of NP-complete problems. In lay terms, the last term, NP-complete refers to a class of problems and means two things :-1) that any problem of this class belongs to the class of NP (non-deterministic, polynomial complexity) problems.
This in turn means that the problem has a known solution that will, in the worst case, take a number of steps (to completion) that is an exponential function of the problem size ( size being in this case the number of vertices of the graph, for example) on a deterministic RAM (Random access machine - pretty much means the kind of machines we use) and involves evaluating an exponentially large number of branches of execution. But the same problem can finish in polynomial time on a fictitious non-deterministic machine which can multi-task and work several branches of execution concurrently to get the solution. 'Exponential' means 'impractical to solve' on any Computer (however powerful) based on the RAM concept. In short, exponential time means 'BAD'.
2) that any problem of this class belongs to the class NP-hard.
This means that any problem in NP can be reduced 'easily' (i.e. in polynomial time) to this problem.Without further delving into what this exactly means, we shall be content with what this implies - that if someone is clever enough to find a solution for even one problem in this class (NP-hard), in polynomial time ( which means the algorithm becomes closer to being easily or practically implemented on computers; in short, it's a 'GOOD' algorithm), then all the other (yes, every other) NP problem can also be solved in 'GOOD' time too.Since the consequent of the earlier 'if' sentence is believed to be false by most experts, the antecedent ( that we'll find a polynomial time algorithm for an NP-complete problem some day) is also very likely to be false.
In other words, an NP-complete problem is an NP problem that is also an NP-hard problem.
In fact, even the seemingly simpler decision (yes/no) problem of checking whether k colors (k>2) are enough to vertex-color a graph, is claimed to be NP-complete.
Proving that Graph coloring is in NP
Well, at least proving that the decision problem is in NP is easy. To do this, we need to demonstrate that there is an algorithm that solves it taking exponential time on a deterministic RAM, but polynomial time on a non-deterministic RAM. Let's devise such an algorithm as follows (we are talking about undirected graphs here, which means that if vertex a is connected to vertex b, it implicitly means that vertex b is also connected to vertex a). Picture that we have k bins into which we want to distribute the n vertices of the graph. The distribution is such that all edges of the graph are only between 2 vertices in different bins. Going from an arbitrarily chosen first vertex to the nth, we can choose a bin in k ways for the first vertex, in k ways for the second and so on. So, this way we actually evaluate k^n (k to the n) vertex to bin assignments in the worst case. Evaluation of a candidate solution involves checking if any vertex's color assignment violates the edge constraint mentioned earlier. If it does, then the solution is rejected. If there is no violation for any vertex, then this is an acceptable solution and we can stop. In the worst case we may need to evaluate all possible solutions (k^n) before we can pronounce a 'no'. This no-brainer approach is called a 'brute-force' algorithm and its time complexity is proportional to k^n. This algorithm is said to be of order O(k^n), i.e. exponential complexity. Moreover, if we had a hypothetical machine that could work by branching out at each decision point of choosing a bin for a vertex, and all the branches could concurrently execute, then such a non-deterministic machine could find an answer (yes/no) in polynomial time, this time being the time taken by a single branch, which is O(n). By that token, this problem belongs to the complexity class NP.
Note that if k were 1, the coloring succeeds only if the graph is an n-vertex graph with n components (i.e. the graph has no edge at all). So the algorithm to see if the graph is 1-colorable is trivial - you just check if there is no edge at all. If k=2 it means we need to check if the graph has a 2-coloring. The 2-coloring succeeds only if the graph is bipartite i.e. its vertices can be divided (partitioned) into two disjoint sets (bins) such that any edge of the graph is only between a vertex of one set and that of the other set ( and not between two vertices of the same set).
Now, the 2-coloring problem ( or equivalently, the problem of determining whether a graph is bipartite) can easily be solved in polynomial time by making a breadth-first search on the graph (BFS), which divides the vertices into different levels that represent the edge distance from the starting vertex chosen for the search, and checking whether there is any edge between vertices at the same level. If there is an edge between two vertices at the same level during a BFS on the graph, then we can say that the graph is not bipartite and, equivalently, cannot be 2-colored. The 1-coloring and 2-coloring problems are said to belong to time complexity class P (for polynomial complexity). This is because the method used, BFS, has a time complexity of order O(m+n), m being the number of edges, and m+n is, in the worst case, a polynomial function in n ( the maximum possible value of m is order O(n^2), so m+n is at most order O(n^2)).
For BFS level assignment, you select a starting vertex arbitrarily, assign it level 0, then assign all vertices adjacent to it , a level 1, and all vertices adjacent to the level 1 vertices, a level 2, and so on, till all unassigned vertices are assigned a level. It is a feature of the BFS algorithm, that the level of any vertex is either exactly one less, or one more, or the same value as any vertex adjacent to it. If and only if a graph is bipartite, can we assign some color A to the even level vertices and color B to the odd level vertices and have a valid 2-coloring.
Why can we or can't we extend this algorithm to see if a graph is 3-colorable or higher number-colorable ? Suppose that during BFS coloring, if we find two connected vertices at the same level, we simply choose another color. For example, in the above Fig 2 showing BFS-based coloring, we see this situation occurring for vertex 3 and then vertex 4, both at level 1, hence requiring vertex 3 to be colored Blue instead of Green, and then vertex 4 being colored Black.
Is the BFS-based approach optimal ?
So we get a nagging doubt here whether this BFS-based coloring process might result in a situation where we might wastefully need say, an extra color in later steps, because of the order in which we chose the starting and other nodes for assigning colors. Putting it differently, if we needed to use say, 4 colors using a BFS-based coloring approach, we wonder whether some other order would in fact have given us a better coloring e.g. a 2- or 3-coloring. On the other hand, may be some other policy for assigning a color to a vertex could have given a better solution i.e. a 2- or 3-coloring for example. In short, if, following the above BFS-based coloring algorithm, we did need a 4th color, then how can we be sure that there is no 2- or 3-coloring for this problem following some other algorithm, and that we indeed require at least 4 colors for vertex-coloring the graph irrespective of how we went about it ?
We need to be able to prove that our algorithm ( the BFS-based one described above was just an example, probably a very simple-minded one) always gives the best solution for any graph; or we need to produce a graph as a counter-example to show that our algorithm is not good enough because there is a coloring for the graph that uses fewer colors. Although not impossible, it is non-trivial to prove either without some help. Here is where Alloy comes in. Let's look at that in my next post
No comments:
Post a Comment