Stability in graphs: methodologies and related problems

In 1965, Edmonds published his celebrated solution to the maximum matching problem, which is a special case of the maximum independent (stable) set problem restricted to the class of line graphs. Two key tools in the solution of Edmonds are augmenting chains and cycle shrinking. Both tools can be extended to general graphs but neither of them has been studied or used on a systematic basis. The idea of the present project is to lay theoretical foundations for both techniques (augmenting graphs and graph transformations) in order to turn their isolated applications into a developed methodology and apply this methodology to obtain faster exponential time algorithms for the maximum independent set and related problems, such as satisfiability and constraint satisfaction.

We expect that the proposal will have impact of different types and that the impact will be felt by beneficiaries from various groups.

In terms of groups of beneficiaries:

1. The first and immediate beneficiaries of the project will be people working in Graph Theory, as most results will be obtained and described by means of graph theory.

2. The algorithmic community will benefit through a new methodology based on total struction, which has no analogues.

3. Our results will also bring new blood to the development of SAT and CSP solvers.

Since maximum independent set and closely related problems, such as maximum clique, find applications far beyond Discrete Mathematics and Theoretical Computer Science, in areas such as Patter Recognition, Data Mining, etc., we also believe that our results will be beneficial in those areas too.

In terms of types of the impact:

1. We will make a significant contribution to knowledge, including both scientific advances and technology, just by achieving the objectives stated in the case for support.

2. We will recruit two young researchers and will transfer our skills to the next generation of researchers ensuring the people pipeline.

3. We will make significant long run contributions to Society and Economy by implementing our theoretical findings in a new generation software for Automated Reasoning. In the long run, this will lead to a better quality of life and to wealth creation.