# EP/K016423/1 - Algorithms for Perfect Graph and Other Hereditary Graph Classes

Research Perspectives grant details from EPSRC portfolio

EPSRC Database

Source RCUK EPSRC Data

Research Perspectives grant details from EPSRC portfolio

Principal Investigator - Sch of Computing, University of Leeds

Scheme

Standard Research

Research Areas

Start Date

01/2013

End Date

12/2015

Value

£134,323

Similar Grants

Automatic generation of similar EPSRC grants

Similar Topics

Topic similar to the description of this grant

Grant Description

Summary and Description of the grant

Developing efficient algorithms for solving optimization problems is of great importance to the modern technological society. Many problems arising in diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc., when modeled by graphs reduce to problems such as finding the size of a largest clique (which is a set of nodes that are all pairwise adjacent), or stable set (which is a set of nodes none of which are pairwise adjacent), or the coloring problem (i.e. using the minimum number of colors to color the vertices of a graph so that no two adjacent vertices receive the same color). These fundamental optimization problems are unfortunately NP-hard to solve in general, which means that it is highly unlikely that there will ever be an efficient way to solve them by a computer (i.e. it is unlikely that polynomial time algorithms exist for these problems). They become polynomially solvable when restricted to special graph classes, but also remain difficult even when seemingly quite a lot of structure is imposed on an input graph. Understanding structural reasons that enable efficient algorithms for such optimization problems is the primary interest of this proposal.

In the past few decades a number of important results were obtained through the use of decomposition theory, where one gains an understanding of a complex structure by breaking it down into simpler parts. For example, the famous Strong Perfect Graph Conjecture (that characterizes perfect graphs, a class that emerged from the study of communication theory, by excluded induced subgraphs) was proved by a decomposition theorem. Also it is known how to use this decomposition theorem to construct a polynomial time recognition algorithm for perfect graphs. What is not known is how to make use of it for construction of related optimization problems. This project will focus on developing techniques for turning such decomposition theorems into efficient optimization algorithms. This is particularly difficult to do when dealing with complex hereditary graphs classes, such as perfect graphs, because very strong cutsets are needed for their decomposition and it is not clear how to use them in the desired algorithms.

EPSRC Grants On The Web Link

http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/K016423/1

Structured Data / Microdata

Grant Event Details:

Name: Algorithms for Perfect Graph and Other Hereditary Graph Classes - EP/K016423/1

Start Date: 2013-01-01T00:00:00+00:00

End Date: 2015-12-31T00:00:00+00:00

Organization: University of Leeds

Description: Developing efficient algorithms for solving optimization problems is of great importance to the modern technological society. Many problems arising in diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc., ...