|
| EPSRC Reference: |
EP/C518225/1 |
| Title: |
Decompositions and Algorithms |
| Principal Investigator: |
Dr K Vuskovic |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Sch of Computing |
| Organisation: |
University of Leeds |
| Scheme: |
Standard Research |
| Starts: |
01 May 2005 |
Ends: |
31 August 2008 |
Value (£): |
115,946
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Logic and Combinatorics |
| Mathematical Aspects of Operational Research |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
K. Summary
Describe the proposed research in a style that would be accessible to an interested 14 year old [up to 4000 chars]
Graph theory plays an important role in creating the modern technological society. Problems such as assigning frequencies to mobile telephones, can be modeled using graphs, and then the problem is reduced to coloring the vertices of the graph so that no two adjacent vertices receive the same color (of course we are interested in the minimum number of colors needed, and this is called the chromatic number of a graph). Many other applications in the real world reduce to the same coloring problem on graphs. Unfortunately, finding the chromatic number of a graph and some other optimization problems such as finding the size of a largest clique in a graph, are NP-complete in general. This means that it is highly unlikely that these problems can be solved efficiently on a computer (i.e. it is unlikely that polynomial time algorithms for these problems exist). In these situations we want to find classes of graphs for which these problems can be solved in polynomial time. One such class is the class of perfect graphs.
Perfect graphs were defined in 1961, and have since attracted an enormous amount of really exciting research that reached far beyond this particular area. Recently the two most famous problems in this area were solved: the Strong Perfect Graph Conjecture (that states that a graph G is perfect if and only if neither G nor its complement contains an odd hole) and a polynomial time recognition algorithm for perfect graphs was obtained. A number of important problems remain in this area. The known algorithms for solving optimization problems on perfect graphs in polynomial time are theoretical but not practical because they use the ellipsoid method. The key question that remains is whether these optimization problems for perfect graphs can be solved by polynomial time algorithms that are purely combinatorial, avoiding the numerical instability of the ellipsoid method. Perfect graphs are a subclass of odd-hole-free graphs. It is open whether odd-hole-free graphs can be recognized in polynomial time, and whether one can efficiently solve the same optimization problems for this larger class of graphs.
The project will focus on further development of decomposition techniques that can be applied to solving the above mentioned problems. The power of decomposition is that it allows us to understand complex structures by breaking them down into simpler ones. Once these simpler structures are understood, this knowledge is propagated back to the original structure by understanding how their composition behaves. The use of decomposition in combinatorial theory has been successfull in solving some of the difficult problems, such as the Strong Perfect Graph Conjecture, recognition of perfect graphs, regular matroids, max-flow min-cut matroids, balanced matrices and even-hole-free graphs. The decomposition techniques are quite general, so their further development is bound to have an important impact on the field.
|
| Final Report Summary |
Graph theory plays an important role in creating the modern technological society. Many important applications, such as assigning frequencies to mobile phones, reduce to coloring the vertices of a graph so that no two adjacent vertices receive the same color (the minimum number of colors needed is known as the chromatic number of a graph). Unfortunately, finding the chromatic number of a graph and some other optimization problems such as finding the size of a largest clique in a graph, are NP-complete in general. This means that it is highly unlikely that these problems can be solved efficiently on a computer (i.e. it is unlikely that polynomial time algorithms for these problems exist). In these situations we want to find classes of graphs for which these problems can be solved in polynomial time.
This research focused on developing techniques for analyzing graph classes characterized by excluded induced subgraphs in order to develop recognition and otimization algorithms. Many important graph classes are characterized in this way, such as perfect graphs. For difficult optimization or recognition problems to be solved in polynomial time for a given graph class it means that this class must have some strong structure. This research focused precisely on trying to understand what is this strong structure that allows polynomial time optimization and recognition algorithms. Some of the most important results obtained on this grant are as follows.
In recent years the decomposition method has been very successful in solving some of the most difficult open problems in graph theory, such as the resolution of the Strong Perfect Graph Conjecture and polynomial time recognition of perfect graphs. After this work was completed, several important related questions remained. By the Strong Perfect Graph Theorem, perfect graphs are precisely the graphs that do not contain an odd hole nor an odd antihole. It is now known that perfect graphs can be recognized in polynomial time, but what remains open is whether odd-hole-free graphs can be recognized in polynomial time. We show that odd-hole-free graphs of bounded clique size can be recognized in polynomial time. It has been known for a long time that finding the chromatic number (and other related optimization problems) can be solved for perfect graphs in polynomial time, but this result was obtained using the ellipsoid method and the question that remains is whether these optimization problems can be solved by polynomial time purely combinatorial algorithms, avoiding the numerical instability of the ellipsoid method. We developed a general technique for proving the existence of a vertex with particular neighborhood, that allowed us to develop a combinatorial algorithm for solving the maximum weighted clique problem on a subclass of perfect graphs that generalizes both claw-free graphs and 4-hole-free graphs. This general technique was also successfully applied on the class of even-hole-free graphs.
The decomposition theorems usualy describe the global structure of the graph class, whereas the above mentioned research focuses on the importance of local structure in obtaining polynomial time algorithms. We also show that even-hole-free graphs that do not contain a diamond can be colored in polynomial time, by first proving a very complicated decomposition theorem and then using it to obtain the existence of a vertex with a particular neighborhood (i.e. we used global structure to obtain local structure, which we then expolited for obtaining polynomial time coloring algorithm).
Another major result on this grant is the decomposition theorem for even-hole-free graphs that uses star cutsets and 2-joins. This result significantly strengthens the previously known decomposition theorem for even-hole-free graphs, and consequently allows for the fastest know algorithm for recognizing even-hole-free graphs. It is also analogous to the famous decomposition of perfect graphs.
|
| Further Information: |
|
| Organisation Website: |
http://www.leeds.ac.uk |
|
|