Details of Grant 

EPSRC Reference:	EP/C518225/1
Title:	Decompositions and Algorithms
Principal Investigator:	Vuskovic, Professor K
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Sch of Computing
Organisation:	University of Leeds
Scheme:	Standard Research (Pre-FEC)
Starts:	01 May 2005	Ends:	31 August 2008	Value (£):	115,946
EPSRC Research Topic Classifications:	Fundamentals of Computing Logic & Combinatorics Mathematical Aspects of OR
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:
Summary on Grant Application Form
K. SummaryDescribe 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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.leeds.ac.uk