SCOPE - Exploiting Structure to Cope with Hard Problems

-

Many problems that need to be solved in real-life computer science applications are very hard, in the sense that we do not have methods or hope to compute their optimal solutions efficiently. In this project we concentrate on input instances of these prob lems with particular structure, and exploit our knowledge on the structure to be able to give algorithms that are faster when the input has this structure. This not only allows us to handle these problems on structured input efficiently, but it also opens for the possibility of solving these problems within reasonable time and optimally on all types of input. The understanding for this comes from the tools that are in general applied to cope with hard problems. Two well-known methods in pursue of tractabi lity are reduction rules and branching rules. Reduction rules manage to get rid of the unimportant parts of the input efficiently. Branching rules manage to identify parts of the input on which we can do exhaustive search without spending too much time. A fter these rules are applied, we are often left with the remainder of the input which we need to deal with in some other way. In this case, if the remaining part has some particular structure and we know how to solve the problem efficiently on this type o f structure, then we are able to plug this knowledge in at this stage. This way we obtain algorithms that manage to solve the problem optimally on all inputs in running time that is reasonable for practical inputs. The focus of the project is thus to f ind efficient solution methods for hard problems on structured inputs. In particular we concentrate on problem areas that are related to computational biology, DNA mappings, phlogenetic trees, and linear algebra. We identify specific research challenges c oncerning graph algorithms for width parameters, linear layouts, clustering, sandwich problems, and perfect graphs. The solution of these challenges will immediately make important problems solvable in practice.